Low-rank matrix approximation in the infinity norm
The authors investigate the \(\ell_\infty\) LRA problem: ``given a matrix \(M\) and a factorization rank \(r\), find a matrix \(X\) whose rank is at most \(r\) and that minimizes \(\max_{i,j}|M_{ij} - X_{ij}|\). They are mostly concerned with the case \(r = 1\). Their main results are: 1) if the sign pattern of \(X\) is known, then the decision version of rank-one \(\ell_\infty\) LRA can be solved in polynomial time by finding a solution to a system of linear inequalities; 2) the rank-one \(\ell_\infty\) LRA is NP-complete. The authors also propose a simple heuristic algorithm.
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- Checking robust nonsingularity is NP-hard
- Coordinate descent algorithms
- Generalized low rank models
- scientific article; zbMATH DE number 467196 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Independent component analysis, a new concept?
- Learning the parts of objects by non-negative matrix factorization
- Low rank approximation with entrywise \(\ell_1\)-norm error
- Low-rank matrix approximation with weights or missing data is NP-hard
- Lower Rank Approximation of Matrices by Least Squares with Any Choice of Weights
- On low rank matrix approximations with applications to synthesis problem in compressed sensing
- On Tensors, Sparsity, and Nonnegative Factorizations
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Quasioptimality of skeleton approximation of a matrix in the Chebyshev norm
- Reducibility among combinatorial problems
- The maximal-volume concept in approximation by low-rank matrices
- Towards a Genuinely Polynomial Algorithm for Linear Programming
- Interval matrices: realization of ranks by rational matrices
- On the rank-one approximation of positive matrices using tropical optimization methods
- Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
- Low rank approximation with entrywise \(\ell_1\)-norm error
- Why Are Big Data Matrices Approximately Low Rank?
- Generalization of real interval matrices to other fields
- Low-rank approximation with 1/𝜖 1/3 matrix-vector products
- On the optimal rank-1 approximation of matrices in the Chebyshev norm
- Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
- On the distance to low-rank matrices in the maximum norm
- Optimal approximation of a large matrix by a sum of projected linear mappings on prescribed subspaces
- Refining uniform approximation algorithm for low-rank Chebyshev embeddings
- Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensors
- When big data actually are low-rank, or entrywise approximation of certain function-generated matrices
- Entrywise tensor-train approximation of large tensors via random embeddings
- Testing covariance separability for continuous functional data
- Analysis of the alternating minimization method for low-rank canonical polyadic decomposition in the Chebyshev norm
This page was built for publication: Low-rank matrix approximation in the infinity norm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2273885)
