NDLI: Input Sparsity and Hardness for Robust Subspace Approximation

Content Provider	IEEE Xplore Digital Library
Author	Clarkson, K.L. Woodruff, D.P.
Copyright Year	2015
Description	Author affiliation: IBM Res. - Almaden, San Jose, CA, USA (Clarkson, K.L.; Woodruff, D.P.)
Abstract	In the subspace approximation problem, we seek a k-dimensional subspace F of $R^{d}$ that minimizes the sum of p-th powers of Euclidean distances to a given set of n points $a_{1},⋯,$ $a_{n}$ ∈ $R^{d},$ for p ≥ 1. More generally than minimizing $Σ_{i}$ $dist(a_{i}$ $F)^{p},$ we may wish to minimize $Σ_{i}$ $M(dist(a_{i},$ F)) for some loss function M(), for example, M-Estimators, which include the Huber and Tukey loss functions. Such subspaces provide alternatives to the singular value decomposition (SVD), which is the p = 2 case, finding such an F that minimizes the sum of squares of distances. For p E [1, 2), and for typical M-Estimators, the minimizing F gives a solution that is more robust to outliers than that provided by the SVD. We give several algorithmic results for these robust subspace approximation problems. We state our results as follows, thinking of the n points as forming an n × d matrix A, and letting nnz(A) denote the number of non-zero entries of A. Our results hold for p ∈ [1, 2). We use poly(n) to denote $n^{O(1)}$ as n → ∞. 1) For minimizing $Σ_{i}$ $dist(a_{i},$ $F)^{p},$ we give an algorithm running in O(nnz(A) + (n + d)poly(k/ε) + exp(poly(k/ε))) 2) We show that the problem of minimizing $Σ_{i}$ $dist(a_{i},$ $F)^{p}$ is NP-hard, even to output a (1 + 1/poly(d))-approximation. This extends work of Deshpande et al. (SODA, 2011) which could only show NP-hardness or UGC-hardness for p > 2; their proofs critically rely on p > 2. Our work resolves an open question of [Kannan Vempala, NOW, 2009]. Thus, there cannot be an algorithm running in time polynomial in k and 1/ε unless P = NP. Together with prior work, this implies that the problem is NP-hard for all p ≠ 2. 3) For loss functions for a wide class of M-Estimators, we give a problem-size reduction: for a parameter K = (log n)O(log k), our reduction takes O(nnz(A) logn + (n + d)poly(K/ε)) time to reduce the problem to a constrained version involving matrices whose dimensions are $poly(Kε^{-1}$ log n). We also give bicriteria solutions. 4) Our techniques lead to the first O(mmz(A) + poly(d/ε)) time algorithms for (1 + ε)-approximate regression for a wide class of convex M-Estimators. This improves prior results [1], which were (1 + ε)-approximation for Huber regression only, and O(1)-approximation for a general class of M-Estimators.
Starting Page	310
Ending Page	329
File Size	408554
Page Count	20
File Format	PDF
ISBN	9781467381918
ISSN	02725428
DOI	10.1109/FOCS.2015.27
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-10-17
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation methods Approximation algorithms Robustness Polynomials Principal component analysis Time complexity Singular value decomposition sketching low rank approximation numerical linear algebra regression robust statistics sampling
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in