Source-linked AI summary
Some theoretical and practical results on noisy signals recovery
M. Makurin, Yu. Malykhin, K. Ryutin, V. Temlyakov
TL;DR
The paper studies approximate recovery of noisy sparse signals and the related Lebesgue-type inequalities for greedy algorithms. It proves results under RIP-type and coherence conditions, including OMP recovery guarantees for coherent dictionaries. The results address redundant systems and include an application to sparse-channel recovery with an oversampled Fourier dictionary.
Problem
The paper addresses approximate recovery of noisy signals sparse with respect to a dictionary, a problem linked to establishing Lebesgue-type inequalities for the recovery algorithms.
Source: §1 · p. 3, §4 · p. 19Method
The paper derives Lebesgue-type inequalities and OMP recovery guarantees under RIP-type or coherence conditions on dictionaries.
Source: §1 · pp. 5–7Results
Under the stated conditions, OMP selects only true dictionary elements and recovers all elements whose coefficients exceed a noise-dependent threshold.
Source: §1 · p. 8Takeaways & Limitations
The approach treats redundant systems and is applied to sparse-channel recovery with an oversampled Fourier dictionary.
Source: §1 · p. 7The stated results assume dictionary conditions, including a Riesz-dictionary RIP-type property and uniform boundedness for Theorem 1.1.
Source: §1 · pp. 5–6
Abstract
from arXiv · showhide
We discuss some theoretical results and their applications to specific practical problems from wireless communications. We assume that we know the noisy version of the signal, which is sparse with respect to a given system of elements (dictionary), at a finite number of points and we want to approximately recover it. This problem of recovery of a noisy signal is closely related to the problem of establishing the Lebesgue-type inequalities for the corresponding algorithms and it motivates us to prove such inequalities. Under certain conditions on a dictionary (RIP-type condition, coherence condition) we obtain different kinds of the Lebesgue-type inequalities for the OMP and its version WOMP algorithms. The most important feature of our new theoretical result is the assumption that the dictionary has the RIP-type property instead of the assumption that it is the Riesz basis, which was used in the previous results. Our approach allows us to treat redundant (overcomplete) systems, which is important in applications. We consider the setting of sparse recovery for highly-coherent dictionaries that appear in OFDM setting for wireless communication. Our main example is the oversampled Fourier dictionary and the recovery of the frequency response of a sparse channel. We develop a general approach to such problems and we prove that under certain conditions the OMP algorithm recovers all dictionary elements with large coefficients, and estimate its accuracy (in NMSE metric) in terms of signal-to-noise ratio.
1 Introduction
The introduction frames noisy sparse-signal recovery as a problem linked to Lebesgue-type inequalities for greedy algorithms. It presents results for redundant dictionaries and coherent wireless-channel settings, including conditions for recovery by OMP and WOMP.
1 Introduction
- The paper motivates its results with sparse signals represented by dictionary elements and distinguishes exact sparsity from approximation-based sparsity assumptions.It also lists compressibility and fast coefficient decay as signal assumptions.Source: §1 · pp. 3–4
- Theorem 1.1 gives WOMP Lebesgue-type inequalities under RIP-type dictionary conditions, extending the setting beyond Riesz bases to redundant systems.The theorem's assumptions include a uniformly bounded system in R(s, R1, R2); the authors identify treatment of redundant systems as its key new feature.Source: §1 · pp. 6–7
- The introduction connects noisy recovery to Lebesgue-type inequalities, with approximation errors and best v-term errors measured in the specified norms.The discussion relates these inequalities to strict sparsity and the noise assumptions.Source: §1 · pp. 3, 7
- Under a small M +(D1, D), OMP recovers only true dictionary elements and selects every element whose coefficient exceeds the noise-dependent threshold.The stated conditions include µ + 2µ+ < 1 and a noise condition; the threshold is ˆβ = 2θ/(1 − µ − 2µ+).Source: §1 · p. 8
- The coherent-dictionary result is designed for oversampled Fourier dictionaries and is applied to sparse-channel recovery in wireless communications.The paper identifies the oversampled Fourier dictionary as a typical example with coherence close to 1.Source: §1 · pp. 3, 8
- For exponentially decaying coefficients |ak| ≤ q^k, Theorem 5.1 bounds σm(f, D) by Cq^m(1 − q)^−1/2 and establishes the best possible dependence on q.The stated setting is a Banach space with a regular modulus of smoothness and a dictionary D.Source: §1 · p. 8
2 Definitions of greedy algorithms
The section defines greedy procedures that build approximations by selecting dictionary elements and updating residuals or projections. WOMP relaxes the element-selection requirement, while OMP is its fully greedy case.
2 Definitions of greedy algorithms
- PGA selects a dictionary element maximizing the absolute inner product with the current input at each iteration.The approximation is formed by projecting onto the span of selected elements, and the residual is updated iteratively.Source: §2 · p. 9
- The sequence of PGA approximations need not be unique.The selected maximizer may not be unique, so different valid choices can produce different approximation sequences.Source: §2 · p. 9
- WOMP accepts an element whose inner product meets a fraction t of the supremum, rather than requiring the optimal element.The weaker criterion avoids requiring that a maximizing element exists; the results apply to any permitted selection.Source: §2 · pp. 9–10
- OMP is WOMP with weakness parameter t_k = 1 at every iteration.The paper focuses on constant weakness parameters t in (0, 1].Source: §2 · pp. 9–10
3 Performance of the WOMP for Riesz dictionaries
The section connects greedy approximation guarantees to noisy-signal recovery, then develops WOMP recovery bounds under dictionary and sampling assumptions. It also gives a finite-dimensional OMP result for sparse signals observed at noisy coordinates.
3 Performance of the WOMP for Riesz dictionaries
- A WOMP Lebesgue-type inequality converts approximation quality into an error guarantee for noisy observations after m iterations.The section identifies this as the direct connection between noisy-data recovery and Lebesgue-type inequalities.Source: §3 · p. 10
3.1 Sampling recovery. Proof of Theorem 1.1
- RIP-type assumptions on uniformly bounded systems yield WOMP Lebesgue-type inequalities that extend beyond Riesz bases to redundant dictionaries.The theorem requires parameters controlling the RIP-type condition and, for sampling recovery, universal discretization.Source: §3.1 · p. 12
- Universal discretization is the key condition in the sampling result; random sampling gives it with high probability under the stated boundedness and RIP-type assumptions.For fixed K, the stated sample bound is m ≫ s(log N)(log s)^2 · (log s + log log N); a tighter bound is noted under an additional Riesz-basis assumption.Source: §3.1 · pp. 12, 15
3.2 Finite-dimensional case and noisy values
- The finite-dimensional observation model is y = f*[I_m] + w, with the goal of recovering the clean sparse signal f* from those noisy coordinate values.Repeated sampled indices are handled by averaging their corresponding observations.Source: §3.2 · pp. 16, 18
- In the finite-dimensional setting, OMP applied to noisy sampled coordinates gives a sparse-signal approximation after cv steps under the stated dictionary and sampling conditions.The theorem gives a high-probability error inequality; the proof also bounds the discrepancy between the constructed full vector and the clean signal by the noise magnitude.Source: §3.2 · pp. 17–18
4 Recovery with coherent dictionaries
The section develops recovery guarantees for coherent dictionaries, motivated by oversampled Fourier dictionaries in sparse wireless-channel recovery. Its results show when OMP recovers large-coefficient elements and when a PGA-based procedure selects them under stated assumptions.
4 Recovery with coherent dictionaries
- The section motivates coherent-dictionary analysis because practical dictionaries can have large RIP constants and coherence near 1, with oversampled Fourier dictionaries as an example.The oversampled Fourier setting motivates the sparse-channel application.Source: §4 · p. 19
4.1 Some known results for OMP with coherent dictionaries
- Earlier OMP results for coherent dictionaries give support-recovery guarantees under stated dictionary, sparsity, and noise conditions.The cited results also address coefficient approximation error.Source: §4.1 · pp. 19–20
4.2 Recovery guarantees for coherent dictionaries
- While an untouched large coefficient remains, the stopping criterion is unmet and OMP selects only true elements; if all coefficients are large, it stops after K steps.The all-large-coefficients case is stated as a corollary.Source: §4.2 · pp. 21–22
4.3 Sparse channel recovery problem in wireless communication
- Oversampling yields a coherent Fourier dictionary—M(D(F)) ≈ 0.9 for ρ = 4—so the section applies its coherent-dictionary recovery analysis to channel estimation.The unknown channel frequency response is represented sparsely using an oversampled Fourier dictionary.Source: §4.3 · pp. 22–23
- Under the stated conditions, OMP recovers all dictionary elements whose coefficients exceed the threshold, and a random-channel result bounds NMSE with probability at least 1 − p.The NMSE guarantee applies when the stated condition holds for a random Ψ and a random channel.Source: §4.3 · pp. 23–24
4.4 A special setting
- Under Theorem 4.1’s inequalities, the PGA selects g1, …, gK during its first K iterations for signals in E(K, L, q, a, b).The proposed combination then projects onto their span before applying OMP.Source: §4.4 · p. 26
5 Recovery in Banach spaces. Discussion
This section extends greedy-recovery discussion to Banach spaces, including noisy-data settings and coherent dictionaries. It also presents approximation bounds for fast-decaying coefficients and recovery results for quasi-orthogonal greedy algorithms.
5 Recovery in Banach spaces. Discussion
- For a system S that is not a dictionary for X, convergence results apply only to signals in the closed span XS; some proofs also extend to normalized systems.The section also introduces a coherence parameter for dictionaries in uniformly smooth Banach spaces.Source: §5 · p. 28
5.1 Fast decaying coefficients
- For spaces with quadratic modulus of smoothness, Theorem 5.1 bounds best m-term approximation for expansions with geometrically decaying coefficients, and the stated upper bound is sharp.The coefficient condition is |ak| ≤ q^k for q ∈ (0, 1).Source: §5.1 · p. 29
5.2 Sparsity assumption A3
- In the noisy-data setting, Theorem 5.2 covers WBGA(τ), including known WCGA and WGAFR results; the section also states an OMP version for Hilbert spaces.The discussion frames noisy data deterministically and relates f to a clean signal f* through condition (5.2).Source: §5.2 · pp. 30–31
5.3 Performance of the WQOGA
- For coherent dictionaries, WQOGA has an exact-recovery result for sparse signals under a coherence-dependent sparsity condition.The result states recovery after S iterations.Source: §5.3 · p. 32
- The section gives QOGA Lebesgue-type inequalities for coherent dictionaries; it reports sharpness for the Hilbert-space bound while noting that one Banach-space corollary’s sharpness is unknown.The cited discussion also says the factor (1 + m^1/2) cannot be replaced by a more slowly growing factor.Source: §5.3 · pp. 32–33