Optimal CUR Matrix Decompositions
From MaRDI portal
Publication:2968164
DOI10.1137/140977898zbMath1359.65059arXiv1405.7910OpenAlexW2592541154MaRDI QIDQ2968164
Christos Boutsidis, David P. Woodruff
Publication date: 10 March 2017
Published in: SIAM Journal on Computing, Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1405.7910
singular value decompositionSVDnumerical linear algebrarandomized algorithmslow-rank approximationsadaptive samplingspectral sparsificationlow rank matrix decompositionCUR decompositioncolumn subset selectionleverage scoresCURinput-sparsity-time
Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Complexity and performance of numerical algorithms (65Y20)
Related Items
Efficient algorithms for CUR and interpolative matrix decompositions, A Generalized CUR Decomposition for Matrix Pairs, Perturbations of the \textsc{Tcur} decomposition for tensor valued data in the Tucker format, An efficient algorithm for computing the approximate t-URV and its applications, Tensor CUR Decomposition under T-Product and Its Perturbation, Pseudo-skeleton approximations with better accuracy estimates, Unnamed Item, Subspaces Analysis for Random Projection UTV Framework, Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions, A literature survey of matrix methods for data science, Randomized algorithms in numerical linear algebra, Adaptive sparse interpolation for accelerating nonlinear stochastic reduced-order modeling with time-dependent bases, Unnamed Item, Lower bounds for column matrix approximations, Non-Negative Sparse Regression and Column Subset Selection with L1 Error, Near-optimal discrete optimization for experimental design: a regret minimization approach, Sparse convex hull coverage, A continuous analogue of the tensor-train decomposition, Unnamed Item, Fast randomized matrix and tensor interpolative decomposition using countsketch, Geometric component analysis and its applications to data analysis, New applications of matrix methods, On the accuracy of cross and column low-rank maxvol approximations in average, A DEIM Induced CUR Factorization, HOID: Higher Order Interpolatory Decomposition for Tensors Based on Tucker Representation, Tensor trains approximation estimates in the Chebyshev norm, Tensor-based computation of metastable and coherent sets, Unnamed Item, Perturbations of CUR Decompositions, Robust CUR Decomposition: Theory and Imaging Applications, Manifold Based Data Refinement for Biological Analysis, Hybrid CUR-type decomposition of tensors in the Tucker format, ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
- CUR matrix decompositions for improved data analysis
- Mosaic-skeleton approximations
- Universal classes of hash functions
- Pseudo-skeleton approximations by matrices of maximal volume
- A theory of pseudoskeleton approximations
- Improved bound for rank revealing LU factorizations
- Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
- Incomplete cross approximation in the mosaic-skeleton method
- On the existence and computation of rank-revealing LU factorizations
- Strong rank revealing Cholesky factorization
- Four algorithms for the the efficient computation of truncated pivoted QR approximations to a sparse matrix
- Strong rank revealing LU factorizations
- Efficient algorithms for privately releasing marginals via convex relaxations
- On generalized matrix approximation problem in the spectral norm
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Randomized Extended Kaczmarz for Solving Least Squares
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Computational Advertising: Techniques for Targeting Relevant Ads
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- A fast randomized algorithm for overdetermined linear least-squares regression
- Low-Rank Approximation and Regression in Input Sparsity Time
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Sampling from large matrices
- Matrix approximation and projective clustering via volume sampling
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Relative-Error $CUR$ Matrix Decompositions
- Collusion-secure fingerprinting for digital data
- Numerical linear algebra in the streaming model
- Twice-ramanujan sparsifiers
- On the complexity of differentially private data release
- Generalized Rank-Constrained Matrix Approximations
- Advances in Cryptology – CRYPTO 2004
- Relative Errors for Deterministic Low-Rank Matrix Approximations
- Fast monte-carlo algorithms for finding low-rank approximations
- Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods
- Algorithm 844
- Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition
- Near-Optimal Column-Based Matrix Reconstruction
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Optimal Column-Based Low-Rank Matrix Reconstruction
- Theory of Cryptography
