Optimal column-based low-rank matrix reconstruction

MaRDI QIDQ5743470zbMATH OpenFDO

Authors Ali Kemal Sinop, Venkatesan Guruswami

Publication date 10 May 2019

Full work available at URL https://arxiv.org/abs/1104.1732, https://dl.acm.org/citation.cfm?id=2095211

Mathematics Subject Classification ID

Matrix completion problems (15A83) Randomized algorithms (68W20) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Abstract: We prove that for any real-valued matrix $Xin{R}^{mimesn}$, and positive integers $rgek$, there is a subset of $r$ columns of $X$ such that projecting $X$ onto their span gives a $sqrtfracr+1r-k+1$-approximation to best rank-$k$ approximation of $X$ in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in $O(rn{m}^{omega}logm)$ arithmetic operations where $omega$ is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in $O(rn{m}^2)$ arithmetic operations.

Recommendations

• Near-optimal column-based matrix reconstruction
• Fast monte-carlo algorithms for finding low-rank approximations
• Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD
• An improved approximation algorithm for the column subset selection problem
• Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

Cites work

• Adaptive Sampling and Fast Low-Rank Matrix Approximation
• CUR matrix decompositions for improved data analysis
• Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD
• Fast monte-carlo algorithms for finding low-rank approximations
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• Inequalities: theory of majorization and its applications
• Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
• Matrix approximation and projective clustering via volume sampling
• Near Optimal Column-Based Matrix Reconstruction

Cited in

(25)

• Fast randomized matrix and tensor interpolative decomposition using countsketch
• On the accuracy of cross and column low-rank maxvol approximations in average
• Regularized greedy column subset selection
• Provable accelerated gradient method for nonconvex low rank optimization
• Randomized algorithms of maximum likelihood estimation with spatial autoregressive models for large-scale networks
• Column subset selection problem is UG-hard
• Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD
• Reverse iterative volume sampling for linear regression
• Local reconstruction of low-rank matrices and subspaces
• Literature survey on low rank approximation of matrices
• An improved approximation algorithm for the column subset selection problem
• Non-negative sparse regression and column subset selection with \(L_1\) error
• Low rank approximation in the presence of outliers
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• scientific article; zbMATH DE number 7307477 (Why is no real title available?)
• Near-optimal column-based matrix reconstruction
• One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering
• Lower bounds for column matrix approximations
• Block discrete empirical interpolation methods
• Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
• Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
• Computing Strong Rank-Revealing Factorizations for Matrices with Orthonormal Rows
• A sharp bound for sampling widths in the uniform norm: kernel D-optimal designs and oversampling
• Guessing efficiently for constrained subspace approximation
• Column subset selection via sparse approximation of SVD

This page was built for publication: Optimal column-based low-rank matrix reconstruction

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