Why Are Big Data Matrices Approximately Low Rank?
From MaRDI portal
Publication:5025778
DOI10.1137/18M1183480MaRDI QIDQ5025778
Alex Townsend, Madeleine Udell
Publication date: 3 February 2022
Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.07474
Computational aspects of data analysis and big data (68T09) Numerical methods for low-rank matrix approximation; matrix compression (65F55)
Related Items
On Robustness of Principal Component Regression ⋮ A Schatten-\(q\) low-rank matrix perturbation analysis via perturbation projection error bound ⋮ Two sample tests for high-dimensional autocovariances ⋮ WARPd: A Linearly Convergent First-Order Primal-Dual Algorithm for Inverse Problems with Approximate Sharpness Conditions ⋮ CDPA: common and distinctive pattern analysis between high-dimensional datasets ⋮ Double-Matched Matrix Decomposition for Multi-View Data ⋮ FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank–Wolfe Algorithms and Conditional Gradients ⋮ Iterative Collaborative Filtering for Sparse Matrix Estimation ⋮ On the best approximation algorithm by low-rank matrices in Chebyshev's norm ⋮ Approximation Bounds for Sparse Programs ⋮ Inertial alternating direction method of multipliers for non-convex non-smooth optimization ⋮ A survey on deep matrix factorizations ⋮ Beyond linear subspace clustering: a comparative study of nonlinear manifold clustering algorithms ⋮ Approximate completely positive semidefinite factorizations and their ranks ⋮ Pass-efficient randomized LU algorithms for computing low-rank matrix approximation ⋮ On the optimal rank-1 approximation of matrices in the Chebyshev norm ⋮ A fast diagonal distance metric learning approach for large-scale datasets ⋮ Randomized Low-Rank Approximation for Symmetric Indefinite Matrices ⋮ Arithmetic circuits, structured matrices and (not so) deep learning ⋮ Optimal Reaction Coordinates: Variational Characterization and Sparse Computation ⋮ Network Effects in Default Clustering for Large Systems ⋮ Unnamed Item ⋮ Fast randomized numerical rank estimation for numerically low-rank matrices ⋮ Polynomial whitening for high-dimensional data ⋮ On the distance to low-rank matrices in the maximum norm ⋮ Revisiting the low-rank eigenvalue problem ⋮ FANOK: Knockoffs in Linear Time ⋮ An efficient numerical method for condition number constrained covariance matrix approximation ⋮ Accurate and fast matrix factorization for low-rank learning. ⋮ On the Simplicity and Conditioning of Low Rank Semidefinite Programs ⋮ A randomized exponential canonical correlation analysis method for data analysis and dimensionality reduction ⋮ Intrinsic Complexity and Scaling Laws: From Random Fields to Random Vectors ⋮ Sparse Principal Component Analysis via Variable Projection ⋮ New applications of matrix methods ⋮ Active matrix factorization for surveys ⋮ Imputation of Mixed Data With Multilevel Singular Value Decomposition ⋮ Low phase-rank approximation ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization ⋮ An \(O(N)\) algorithm for computing expectation of \(N\)-dimensional truncated multi-variate normal distribution. II: computing moments and sparse grid acceleration ⋮ Perturbations of CUR Decompositions ⋮ ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching
Uses Software
Cites Work
- Unnamed Item
- A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis
- A tail inequality for quadratic forms of subgaussian random vectors
- Limits of dense graph sequences
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- Representations for partially exchangeable arrays of random variables
- On the singular values of matrices with high displacement rank
- Low-rank matrix approximation in the infinity norm
- Matrix estimation by universal singular value thresholding
- Generalized Low Rank Models
- Stochastic blockmodels with a growing number of classes
- A Remark on Stirling's Formula
- Extensions of Lipschitz mappings into a Hilbert space
- On variants of the Johnson–Lindenstrauss lemma
- Perturbed Identity Matrices Have High Rank: Proof and Applications
- Eigenvalues and Condition Numbers of Random Matrices
- On the Singular Values of Matrices with Displacement Structure
- Practical Sketching Algorithms for Low-Rank Matrix Approximation
- High-Dimensional Probability
- The Blessings of Multiple Causes
- Relative Error Tensor Low Rank Approximation
- The approximate rank of a matrix and its algorithmic applications
