Near-optimal column-based matrix reconstruction

DOI10.1137/12086755XzbMATH Open1298.65079MaRDI QIDQ5494935FDOQ5494935

Authors: Christos Boutsidis, Malik Magdon-Ismail, Petros Drineas 

Publication date: 30 July 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• Optimal column-based low-rank matrix reconstruction
• Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD
• An improved approximation algorithm for the column subset selection problem
• Local reconstruction of low-rank matrices and subspaces
• Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods

zbMATH Keywords

singular value decompositionrandomized algorithmsspectral normlow-rank approximationsmatrix reconstructionFrobenius norms

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Pseudo-random numbers; Monte Carlo methods (11K45)

Cited In (25)

• Stochastic linear regularization methods: random discrepancy principle and applications
• Structural Convergence Results for Approximation of Dominant Subspaces from Block Krylov Spaces
• Lower bounds for column matrix approximations
• Admissible subspaces and the subspace iteration method
• New applications of matrix methods
• Allocation Strategies for High Fidelity Models in the Multifidelity Regime
• Title not available (Why is that?)
• Low rank approximation of binary matrices: column subset selection and generalizations
• Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
• Optimal column-based low-rank matrix reconstruction
• Fast randomized matrix and tensor interpolative decomposition using countsketch
• Robust CUR Decomposition: Theory and Imaging Applications
• Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
• Local reconstruction of low-rank matrices and subspaces
• Low-rank approximation algorithms for matrix completion with random sampling
• Regularized greedy column subset selection
• Online randomized interpolative decomposition with \textit{a posteriori} error estimator for temporal PDE data reduction
• Deterministic Sparse Column Based Matrix Reconstruction via Greedy Approximation of SVD
• Greedy minimization of weakly supermodular set functions
• A separation theorem for joint sensor and actuator scheduling with guaranteed performance bounds
• A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems
• Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy
• Proximal algorithms and temporal difference methods for solving fixed point problems
• Singular values of dual quaternion matrices and their low-rank approximations
• Optimal Quadrature-Sparsification for Integral Operator Approximation

This page was built for publication: Near-optimal column-based matrix reconstruction

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