Matrix recipes for hard thresholding methods
From MaRDI portal
Abstract: In this paper, we present and analyze a new set of low-rank recovery algorithms for linear inverse problems within the class of hard thresholding methods. We provide strategies on how to set up these algorithms via basic ingredients for different configurations to achieve complexity vs. accuracy tradeoffs. Moreover, we study acceleration schemes via memory-based techniques and randomized, -approximate matrix projections to decrease the computational costs in the recovery process. For most of the configurations, we present theoretical analysis that guarantees convergence under mild problem conditions. Simulation results demonstrate notable performance improvements as compared to state-of-the-art algorithms both in terms of reconstruction accuracy and computational complexity.
This paper deals with a new set of low-rank recovery algorithms for linear inverse problems within the class of hard thresholding methods. The authors present new strategies and review existing ones for hard thresholding methods to recover low-rank matrices from dimensionality reducing, linear projections. The discussion revolves around four basic building blocks that exploit the problem structure to reduce computational complexity without sacrificing stability. The complexity analysis of the proposed algorithms is provided. Two acceleration schemes are considered. The authors improve the convergence speed by exploiting randomized low rank projections and provide empirical support for their claims through experimental results on synthetic and real data.
Recommendations
- Iterative hard thresholding for low-rank recovery from rank-one projections
- A singular value \(p\)-shrinkage thresholding algorithm for low rank matrix recovery
- A Singular Value Thresholding Algorithm for Matrix Completion
- Proximal iteratively reweighted algorithm for low-rank matrix recovery
- Normalized iterative hard thresholding for matrix completion
Cites work
- A linearly convergent algorithm for solving a class of nonconvex/affine feasibility problems
- A Singular Value Thresholding Algorithm for Matrix Completion
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- ADMiRA: Atomic Decomposition for Minimum Rank Approximation
- Clustering large graphs via the singular value decomposition
- Compressed sensing and best \(k\)-term approximation
- Convergence of fixed-point continuation algorithms for matrix rank minimization
- CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
- Exact matrix completion via convex optimization
- Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Greed is Good: Algorithmic Results for Sparse Approximation
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Hard thresholding pursuit: an algorithm for compressive sensing
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 1206370 (Why is no real title available?)
- Interior-point method for nuclear norm approximation with application to system identification
- Introductory lectures on convex optimization. A basic course.
- Iterative hard thresholding for compressed sensing
- Learning non-parametric basis independent models from point queries via low-rank methods
- Matrix approximation and projective clustering via volume sampling
- Matrix Completion From a Few Entries
- Matrix recipes for hard thresholding methods
- Noiselets
- Normalized iterative hard thresholding for matrix completion
- Parallel stochastic gradient algorithms for large-scale matrix completion
- Robust principal component analysis?
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
- Solving quadratic equations via phaselift when there are about as many equations as unknowns
- Sparse Approximate Solutions to Linear Systems
- Subspace Pursuit for Compressive Sensing Signal Reconstruction
Cited in
(38)- Painless breakups -- efficient demixing of low rank matrices
- The two-stage iteration algorithms based on the shortest distance for low-rank matrix completion
- Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm
- A new method based on the manifold-alternative approximating for low-rank matrix completion
- A semi-smoothing augmented Lagrange multiplier algorithm for low-rank Toeplitz matrix completion
- Guarantees of Riemannian optimization for low rank matrix completion
- Parametrized quasi-soft thresholding operator for compressed sensing and matrix completion
- Matrix recipes for hard thresholding methods
- Homotopy method for matrix rank minimization based on the matrix hard thresholding method
- A non-Euclidean gradient descent method with sketching for unconstrained matrix minimization
- Iterative hard thresholding for low-rank recovery from rank-one projections
- A simple homotopy proximal mapping algorithm for compressive sensing
- Greedy-like algorithms for the cosparse analysis model
- Compressed sensing of low-rank plus sparse matrices
- Guarantees of Riemannian optimization for low rank matrix recovery
- Minimum n-rank approximation via iterative hard thresholding
- Matrix pseudoinverse hard thresholding pursuit and sparse recovery problem
- Structured sparsity: discrete and convex approaches
- Low rank matrix recovery from rank one measurements
- Harmonic mean iteratively reweighted least squares for low-rank matrix recovery
- CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
- Structured random measurements in signal processing
- Rank $2r$ Iterative Least Squares: Efficient Recovery of Ill-Conditioned Low Rank Matrices from Few Entries
- Matrix rigidity and the ill-posedness of robust PCA and matrix completion
- Low rank matrix recovery with adversarial sparse noise
- GNMR: a provable one-line algorithm for low rank matrix recovery
- Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent
- Optimal $k$-Thresholding Algorithms for Sparse Optimization Problems
- Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably
- Matrix completion via minimizing an approximate rank
- Low-rank tensor recovery using sequentially optimal modal projections in iterative hard thresholding (SeMPIHT)
- Fast gradient method for low-rank matrix estimation
- Heavy-ball-based optimal thresholding algorithms for sparse linear inverse problems
- Heavy-ball-based hard thresholding algorithms for sparse signal recovery
- A preconditioned Riemannian gradient descent algorithm for low-rank matrix recovery
- Dynamic thresholding algorithm with memory for linear inverse problems
- GPU accelerated greedy algorithms for compressed sensing
- Low rank matrix completion by alternating steepest descent methods
This page was built for publication: Matrix recipes for hard thresholding methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2251217)
