Sparse approximation based on a random overcomplete basis
From MaRDI portal
Abstract: We discuss a strategy of sparse approximation that is based on the use of an overcomplete basis, and evaluate its performance when a random matrix is used as this basis. A small combination of basis vectors is chosen from a given overcomplete basis, according to a given compression rate, such that they compactly represent the target data with as small a distortion as possible. As a selection method, we study the - and -based methods, which employ the exhaustive search and -norm regularization techniques, respectively. The performance is assessed in terms of the trade-off relation between the representation distortion and the compression rate. First, we evaluate the performance analytically in the case that the methods are carried out ideally, using methods of statistical mechanics. Our result clarifies the fact that the -based method greatly outperforms the -based one. Second, we examine the practical performances of two well-known algorithms, orthogonal matching pursuit and approximate message passing, when they are used to execute the - and -based methods, respectively. Our examination shows that orthogonal matching pursuit achieves a much better performance than the exact execution of the -based method, as well as approximate message passing. However, regarding the -based method, there is still room to design more effective greedy algorithms than orthogonal matching pursuit. Finally, we evaluate the performances of the algorithms when they are applied to image data compression.
Recommendations
- Sparse representations and approximation theory
- Sparse approximation by greedy algorithms
- Sparse Approximation and Recovery by Greedy Algorithms
- Sparse recovery by reduced variance stochastic approximation
- Computing sparse approximations deterministically
- Spectral sparsification via random spanners
- Sparse Approximation via Penalty Decomposition Methods
- Sparsity based methods for overparameterized variational problems
- Sparse Approximate Solutions to Linear Systems
Cites work
- scientific article; zbMATH DE number 5485514 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- A mathematical introduction to compressive sensing
- Adaptive greedy approximations
- Blind Compressed Sensing
- Compressed sensing
- Compressed sensing and best \(k\)-term approximation
- Decoding by Linear Programming
- Greed is Good: Algorithmic Results for Sparse Approximation
- Greedy algorithms and M-term approximation with regard to redundant dictionaries
- Introduction to the replica theory of disordered statistical systems
- Low rank approximation. Algorithms, implementation, applications
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Nonlinear methods of approximation
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sparse Approximate Solutions to Linear Systems
- Stable recovery of sparse overcomplete representations in the presence of noise
- Statistical Physics of Spin Glasses and Information Processing
- The best m-term approximation and greedy algorithms
- Weak greedy algorithms
Cited in
(4)- Evaluation of generalized degrees of freedom for sparse estimation by replica method
- Average performance of the approximation in a dictionary using an \(\ell _0\) objective
- Sparse approximation using new greedy-like bases in superreflexive spaces
- Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
This page was built for publication: Sparse approximation based on a random overcomplete basis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3302727)
