Adaptive greedy approximations
From MaRDI portal
Let \({\mathcal H}\) be a Hilbert space. A dictionary \({\mathcal D}\) for \({\mathcal H}\) is a family of unit vectors in \({\mathcal H}\) such that finite linear combinations of \(g_{\gamma }\in {\mathcal D}\) are dense in \({\mathcal H}\). The problem of approximations over a dictionary is studied from different points. \(NP\)-Completeness of the problem is proved under some restriction on dictionary size in a finite-dimensional space \({\mathcal H}\). Suboptimal greedy algorithms of nonorthogonal and orthogonal matching pursuits \textit{S. Mallat} and \textit{Z. Zhang} [IEEE Trans. Signal Process. 41, No. 12, 3397-3415 (1993; Zbl 0842.94004)]; \textit{Y. C. Pati, R. Rezaiifar} and \textit{P. S. Krishnaprasad} [Proc. 27th Annual Asilomar Conf. Signals, Systems, and Computers, 40-44 (IEEE Computer Society Press) (1993)] are reviewed. Group-invariant dictionaries are investigated for the sake of wavelet decomposition. Furthermore, the renormalized matching pursuit map is proved to be a chaotic map for a particular dictionary in a low-dimensional space. Numerical results suggest ergodicity of that map for higher-dimensional matching pursuits, too. Their invariant measures are characterized using dictionary group invariances and by constructing a stochastic differential equation model for the distribution of asymptotic approximation errors for a dictionary consisting of a Dirac and a Fourier basis.
Recommendations
Cites work
- Compression of Wavelet Decompositions
- Ergodic theory. Introductory lectures
- scientific article; zbMATH DE number 3121911 (Why is no real title available?)
- scientific article; zbMATH DE number 3898923 (Why is no real title available?)
- scientific article; zbMATH DE number 3718210 (Why is no real title available?)
- scientific article; zbMATH DE number 44378 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 884923 (Why is no real title available?)
- scientific article; zbMATH DE number 3383043 (Why is no real title available?)
- Image compression through wavelet transform coding
- Introduction to algorithms.
- Matching pursuits with time-frequency dictionaries
- On a conjecture of Huber concerning the convergence of projection pursuit regression
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Orthogonal least squares methods and their application to non-linear system identification
- Probabilistic Properties of Deterministic Systems
- Signal representation using adaptive normalized Gaussian functions
Cited in
(only showing first 100 items - show all)- Average performance of the approximation in a dictionary using an \(\ell _0\) objective
- Greedy algorithms and M-term approximation with regard to redundant dictionaries
- Approximate wavelets and the approximation of pseudodifferential operators
- Nonlinear approximation in finite-dimensional spaces
- Efficient uncertainty quantification of stochastic CFD problems using sparse polynomial chaos and compressed sensing
- On the uniqueness of the sparse signals reconstruction based on the missing samples variation analysis
- Backtracking-based simultaneous orthogonal matching pursuit for sparse unmixing of hyperspectral data
- Error in the reconstruction of nonsparse images
- Cardinal B-spline dictionaries on a compact interval
- Capped \(\ell_p\) approximations for the composite \(\ell_0\) regularization problem
- Sparse representation-based patient-specific diagnosis and treatment for esophageal squamous cell carcinoma
- Approximately normalized iterative hard thresholding for nonlinear compressive sensing
- \(\ell_1\)- and \(\ell_2\)-norm joint regularization based sparse signal reconstruction scheme
- On a gradient-based algorithm for sparse signal reconstruction in the signal/measurements domain
- Structured overcomplete sparsifying transform learning with convergence guarantees and applications
- Greedy randomized adaptive search procedures
- Alpha-expansions: A class of frame decompositions
- Some remarks on greedy algorithms
- On the statistics of matching pursuit angles
- A cubic spline penalty for sparse approximation under tight frame balanced model
- An automatic and parameter-free information-based method for sparse representation in wavelet bases
- Mathematical theory of signal analysis vs. complex analysis method of harmonic analysis
- Locality-constrained sparse representation for hyperspectral image classification
- Super-resolution for doubly-dispersive channel estimation
- Sequences of \(m\)-term deviations in Hilbert space
- A solution for the greedy approximation of a step function with a waveform dictionary
- Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints
- On the coincidence of pure greedy and best \(m\)-term approximations
- Duality gap estimates for a class of greedy optimization algorithms in Banach spaces
- Positive-instantaneous frequency and approximation
- Multi-level multi-fidelity sparse polynomial chaos expansion based on Gaussian process regression
- Generalizing CoSaMP to signals from a union of low dimensional linear subspaces
- Iterative hard thresholding for compressed data separation
- Optimal observations-based retrieval of topography in 2D shallow water equations using PC-EnKF
- Sparse recovery with coherent tight frames via analysis Dantzig selector and analysis LASSO
- Sparse signals recovery from noisy measurements by orthogonal matching pursuit
- Regularized coplanar discriminant analysis for dimensionality reduction
- An active set Barzilar-Borwein algorithm for \(l_0\) regularized optimization
- An efficient multifidelity \(\ell_1\)-minimization method for sparse polynomial chaos
- Duality gap estimates for weak Chebyshev greedy algorithms in Banach spaces
- Alternating direction method of multipliers for solving dictionary learning models
- Greedy signal space methods for incoherence and beyond
- Global sensitivity analysis based on high-dimensional sparse surrogate construction
- Time-frequency atom decomposition with quantum-inspired evolutionary algorithms
- Reconstruction of sparse signals in impulsive disturbance environments
- A simple homotopy proximal mapping algorithm for compressive sensing
- Adaptive Fourier series---a variation of greedy algorithm
- Greedy-like algorithms for the cosparse analysis model
- A note on the hardness of sparse approximation
- Beyond sparsity: recovering structured representations by \({\ell}^1\) minimization and greedy algorithms
- Approximation and learning by greedy algorithms
- Adaptive frame methods for nonlinear variational problems
- On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them
- Simultaneous approximation by greedy algorithms
- Orthogonal one step greedy procedure for heteroscedastic linear models
- Nomonotone spectral gradient method for sparse recovery
- A membrane algorithm with quantum-inspired subalgorithms and its application to image processing
- 3D face recognition with sparse spherical representations
- Fast stepwise regression based on multidimensional indexes
- On sparse recovery algorithms in unions of orthonormal bases
- Analysis of target data-dependent greedy kernel algorithms: convergence rates for \(f\)-, \(f \cdot P\)- and \(f/P\)-greedy
- Statistical arbitrage in the US equities market
- Sparse reconstruction of Hardy signal and applications to time-frequency distribution
- Sparse representation of signals in Hardy space
- Learning an adaptive dictionary using a projected gradient method and its application on image de-noising
- On optimal solutions of the constrained \({\ell}_{0}\) regularization and its penalty problem
- On linguistic variables and sparse representations
- A review on restoration of seismic wavefields based on regularization and compressive sensing
- Aveiro method in reproducing kernel Hilbert spaces under complete dictionary
- Average Performance of the Sparsest Approximation Using a General Dictionary
- Compressive sensing with cross-validation and stop-sampling for sparse polynomial chaos expansions
- A continuous exact _0 penalty (CEL0) for least squares regularized problem
- Bag of pursuits and neural gas for improved sparse coding
- Sparse approximation based on a random overcomplete basis
- Sparse approximation is provably hard under coherent dictionaries
- Low-rank and sparse dictionary learning
- Sparsity based methods for overparameterized variational problems
- Efficient blind compressed sensing using sparsifying transforms with convergence guarantees and application to magnetic resonance imaging
- Delay-coordinates embeddings as a data mining tool for denoising speech signals
- Cascade systems de-noising and greedy calibrated approximation
- On the exponential convergence of matching pursuits in quasi-incoherent dictionaries
- Regularization techniques and suboptimal solutions to optimization problems in learning from data
- Greedy approximation
- Sparse Legendre expansions via _1-minimization
- Micro-macro models for viscoelastic fluids: modelling, mathematics and numerics
- A novel sparsity reconstruction method from Poisson data for 3D bioluminescence tomography
- Sparse reconstruction for bioluminescence tomography based on the semigreedy method
- Optimizing image quality
- Can dictionary-based computational models outperform the best linear ones?
- Disparity and optical flow partitioning using extended Potts priors
- Gradient-based method with active set strategy for \(\ell _1\) optimization
- Sparse approximation by greedy algorithms
- Concentration of the Frobenius norm of generalized matrix inverses
- Optimal policies for observing time series and related restless bandit problems
- Approximation hardness for a class of sparse optimization problems
- On the Convergence of a Greedy Algorithm for the Solution of the Problem for the Construction of Monotone Regression
- Approximation of monogenic functions by higher order Szegő kernels on the unit ball and half space
- REMARKS ON ADAPTIVE FOURIER DECOMPOSITION
- Approximate sparse linear regression
- Incomplete variables truncated conjugate gradient method for signal reconstruction in compressed sensing
This page was built for publication: Adaptive greedy approximations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5961558)
