Low rank approximation with entrywise _1-norm error

DOI10.1145/3055399.3055431MaRDI QIDQ4978015zbMATH OpenOpenAlexWikidataFDO

Authors Zhao Song, David P. Woodruff, Peilin Zhong

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.00898

zbMATH Keywords

entry-wise \(\ell_1\) normlow rank approximationnumerical linear algebrarobust algorithmssketching

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: We study the $el{l}_1$-low rank approximation problem, where for a given $nimesd$ matrix $A$ and approximation factor $alphageq1$, the goal is to output a rank-$k$ matrix $widehatA$ for which ${\displaystyle }$|A-widehat{A}|_1 leq alpha cdot min_{ extrm{rank-}k extrm{ matrices}~A'}|A-A'|_1,${\displaystyle }$ where for an $nimesd$ matrix $C$, we let $|C{|}_1=su{m}_{i=1}^{n}su{m}_{j=1}^d|C_{i,j}|$. This error measure is known to be more robust than the Frobenius norm in the presence of outliers and is indicated in models where Gaussian assumptions on the noise may not apply. The problem was shown to be NP-hard by Gillis and Vavasis and a number of heuristics have been proposed. It was asked in multiple places if there are any approximation algorithms. We give the first provable approximation algorithms for $el{l}_1$-low rank approximation, showing that it is possible to achieve approximation factor $alpha=(logd)cdotmathrmpoly(k)$ in $mathrmnnz(A)+(n+d)mathrmpoly(k)$ time, where $mathrmnnz(A)$ denotes the number of non-zero entries of $A$. If $k$ is constant, we further improve the approximation ratio to $O(1)$ with a $mathrmpoly(nd)$-time algorithm. Under the Exponential Time Hypothesis, we show there is no $mathrmpoly(nd)$-time algorithm achieving a $(1+frac1lo{g}^{1+gamma}(nd))$-approximation, for $gamma>0$ an arbitrarily small constant, even when $k=1$. We give a number of additional results for $el{l}_1$-low rank approximation: nearly tight upper and lower bounds for column subset selection, CUR decompositions, extensions to low rank approximation with respect to $el{l}_p$-norms for $1leqp<2$ and earthmover distance, low-communication distributed protocols and low-memory streaming algorithms, algorithms with limited randomness, and bicriteria algorithms. We also give a preliminary empirical evaluation.

Recommendations

• A PTAS for ℓ_p-Low Rank Approximation
• Low rank approximation in the presence of outliers
• Robust low-rank data matrix approximations
• Low-rank matrix approximation in the infinity norm
• On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation

Cited in

(17)

• Low-rank matrix approximation in the infinity norm
• Robust low-rank data matrix approximations
• Low-complexity l₀-norm penalized shrinkage linear and widely linear affine projection algorithms
• Non-negative sparse regression and column subset selection with \(L_1\) error
• Learning discrete distributions from untrusted batches
• Low rank approximation in the presence of outliers
• Tensor rank is hard to approximate
• ISLET: fast and optimal low-rank tensor regression via importance sketching
• Entrywise Estimation of Singular Vectors of Low-Rank Matrices With Heteroskedasticity and Dependence
• Non-convex matrix completion and related problems via strong duality
• On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
• A PTAS for ℓ_p-Low Rank Approximation
• Low-Rank Binary Matrix Approximation in Column-Sum Norm.
• Low-rank approximation with 1/𝜖 ^1/3 matrix-vector products
• New subset selection algorithms for low rank approximation: offline and online
• Training multi-layer over-parametrized neural network in subquadratic time
• Simple heuristics yield provable algorithms for masked low-rank approximation

This page was built for publication: Low rank approximation with entrywise \(\ell_1\)-norm error

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978015)