Proof.

Theorem 5.1 proves that the constants A_Λ and B_Λ are lower and upper bounds of the eigenvalues of the Gram matrix Let v ≠ 0 be an eigenvector satisfying G_Λv = λv. Let Since ,

It results that

which proves (12.120).

The Riesz bound ratio A_Λ/B_Λ is close to 1 if δ_Λ is small and thus if the vectors in Λ have a small correlation. The upper bound (12.120) proves that sufficiently small sets are Riesz bases with A_Λ > 0. To increase the maximum size of these sets, one should construct dictionaries that are as incoherent as possible. The upper bounds (12.120) are simple but relatively crude, because they only depend on inner products of pairs of vectors, whereas the Riesz stability of depends on the distribution of this whole group of vectors on the unit sphere of C^N. Section 13.4 proves that much better bounds can be calculated over dictionaries of random vectors.

The mutual coherence of an orthonormal basis D is 0, and one can verify (Exercise 12.5) that if we add a vector g, then . However, this level of incoherence can be reached with larger dictionaries. Let us consider the dictionary of P = 2N vectors, which is a union of a Dirac basis and a discrete Fourier basis:

(12.121)

Its mutual coherence is μ(D) = N^−1/2. The right upper bound of (12.120) thus proves that any family of Dirac and Fourier vectors defines a basis with a Riesz bound ratio A_Λ/B_Λ ≥ 1/3. One can construct larger frames D of P = N² vectors, called Grassmannian frames, that have a coherence in [448].

Dictionaries often do not have a very small coherence, so the inequality applies to relatively small sets Λ. For example, in the Gabor dictionary D_j,δ defined in (12.77), the mutual coherence μ(D) is maximized by two neighboring Gabor atoms, and the inner product formula (12.81) proves that for δ = 2. The mutual coherence upper bound is therefore useless in this case, but the first upper bound of (12.120) can be used with (12.81) to verify that Gabor atoms that are sufficiently far in time and frequency generate a Riesz basis.

Proof.

Let us first prove that sup_h∈vΛ C(h, Λ^c) ≤ ERC(Λ). Let be the pseudo inverse of φ_Λ with φ_Λf[p] = f, φ_p) for p ∈ Λ. Theorem 5.6 proves that is an orthogonal projector in V_Λ, so if h ∈ V_Λ and q ∈ Λ^c,

(12.126)

Theorem 5.5 proves that the dual-frame operator satisfies and thus that for p ∈ Λ. It results that

(12.127)

and (12.126) implies that

which proves that ERC(Λ) ≥ suph∈V_Λ C(h, Λ^c).

We now prove the reverse inequality. Let q₀ ∈ Λ^c be the index such that

Introducing

(12.128)

leads to

Since , it results that C(h, Λ^c) ≥ ERC(Λ) and thus sup_h∈vΛ C(h, Λ^c) ≥ ERC(Λ), which finishes the proof of (12.124).

Suppose now that f = R⁰f ∈ V_Λ and ERC(Λ) > 1. We prove by induction that a matching pursuit selects only vectors in {φ_p}_p∈Λ. Suppose that the first m < M matching pursuit vectors are in {φ_p}_p∈Λ and thus that R^mf ∈ V_Λ. If R^mf ≠ 0, then (12.125) implies that C(R^mf, Λ^c) < 1 and thus that the next vector is selected in Λ. Since dim (V_Λ) ≤ |Λ|, an orthogonal pursuit converges in less than |Λ| iterations.

This theorem proves that if a signal can be exactly decomposed over {φ_p}_p∈Λ, then ERC(Λ) < 1 guarantees that a matching pursuit reconstructs f with vectors in {φ_p}_p∈Λ. A nonorthogonal pursuit may, however, require more than |Λ| iterations to select all vectors in this family.

If ERC(Λ) > 1, then there exists f ∈ V_Λ such that C(f, Λ^c) > 1. As a result, there exists a vector φ_q with q ∈ Λ^c, which correlates f better than any other vectors in Λ, and that will be selected by the first iteration of a matching pursuit. This vector may be removed, however, from the approximation support at the end of the decomposition. Indeed, if the remaining iterations select all vectors {φ_p}_p∈Λ, then an orthogonal matching pursuit decomposition or a backprojection will associate a coefficient 0 to φ_q because f = P_VΛf. In particular, we may have ERC(Λ) > 1 but with , in which case an orthogonal pursuit recovers exactly the support of any f ∈ V_Λ with iterations.

Theorem 12.12 gives an upper bound proved by Tropp [461], which relates ERC(Λ) to the support size |Λ|. A tighter bound proved by Gribonval and Nielsen [281] and Dossal [231] depends on inner products of dictionary vectors in ã relative to vectors in the complement Λ^c.

Theorem 12.12: Tropp, Gribonval, Nielsen, Dossal. For any ,

(12.129)

Proof.

It is shown in (12.127) that . We verify that

(12.130)

and thus that we can also write . Introducing the operator norm associated to the 1¹ norm

for a matrix A = (a_i,j)_i,j, leads to

(12.131)

The second term is the numerator of (12.129),

(12.132)

The Gram matrix is rewritten as , and a Neumann expansion of G⁻¹ gives

(12.133)

with

(12.134)

Inserting this result in (12.133) and inserting (12.132) and (12.133) in (12.131) prove the first inequality of (12.129).

The second inequality is derived from the fact that for any p ≠ q.

This theorem gives upper bounds of ERC(Λ) that can easily be computed. It proves that ERC(Λ) < 1 if the vectors {φ_p}_p∈Λ are not too correlated between themselves and with the vectors in the complement Λ^c. In a Gabor dictionary defined in (12.77), the upper bound (12.129) with the Gabor inner product formula (12.81) proves that ERC(Λ) < 1 for families of sufficiently separated time-frequency Gabor atoms indexed by Λ. Theorem 12.11 proves that any combination of such Gabor atoms is recovered by a matching pursuit. Suppose that the Gabor atoms are defined with a Gaussian window that has a variance in time and frequency that is and , respectively. Their Heisenberg box has a size σ_t × σ_ω. If |Λ| = 2, then one can verify that ERC(Λ) > 1 if the Heisenberg boxes of these two atoms intersect. If the time distance of the two Gabor atoms is larger than 1.5 σ_t, or if the frequency distance is larger than 1.5 σ_ω, then ERC(Λ) < 1.

The second upper bound in (12.129) proves that ERC(Λ) < 1 for any sufficiently small set Λ

(12.135)

Very sparse approximation sets are thus more easily recovered. The Dirac and Fourier dictionary (12.121) has a low mutual coherence . Condition (12.135) together with Theorem 12.11 proves that any combination of |Λ| ≤ N^1/2/2 Fourier and Dirac vectors are recovered by a matching pursuit. The upper bound (12.135) is, however, quite brutal, and in a Gabor dictionary where and δ ≥ 2, it applies only to |Λ| = 1, which is useless.

Proof.

The residual at step m < |Λ| is denoted where is the orthogonal projection of f on the space generated by the dictionary vectors selected by the first m iterations. The theorem is proved by induction by showing that either satisfies (12.136) or , which means that the first m vectors selected by the orthogonal pursuit are indexed in Λ. If (12.136) is satisfied for some , since ‖R^Mf‖ ≤ ‖R^mf‖, it results that satisfies (12.136). If this is not the case, then the induction proof will show that the M = |Λ| selected vectors are in {φ_p}_p∈Λ. Since an orthogonal pursuit selects linearly independent vectors, it implies that satisfies (12.136).

The induction step is proved by supposing that , and verifying that either C(R^mf, Λ^c) < 1, in which case the next selected vector is indexed in Λ, or that (12.136) is satisfied. We write Since f − f_Λ is orthogonal to V_Λ and for p ∈ Λ, we have , so

(12.137)

with

Since , Theorem 12.11 proves that . Since and , we get

(12.138)

Since , inserting these inequalities in (12.137) gives

If C(R^mf, Λ^c) ≥ 1 then

Since f − f_Λ is orthogonal to this condition is equivalent to

which proves that (12.136) is satisfied, and thus finishes the induction proof.

The proof shows that an orthogonal matching pursuit selects the few first vectors in Λ. These are the “coherent signal structures” having a strong correlation with the dictionary vectors, observed in the numerical experiments in Section 12.3. At some point, the remaining vectors in ã may not be sufficiently well correlated with f relative to other dictionary vectors; Theorem 12.13 computes the approximation error at this stage. This result is thus conservative since it does not take into account the approximation improvement obtained by the other vectors. Gribonval and Vandergheynst proved [283] that a nonorthogonal matching pursuit satisfies a similar theorem, but with more than M = |Λ| iterations. Orthogonal and nonorthogonal matching pursuits select the same “coherent structures.” Theorem 12.14 derives an approximation result that depends on only the number of M-term approximations and on the dictionary mutual coherence.

Proof.

Let Λ be the approximation support of the best M-term dictionary approximation f_M with |Λ| = M. If , then (12.129) proves that (1 – ERC(Λ))⁻¹ < 2. Theorem 12.10 shows that if , then A_Λ ≥ 2/3. Theorem 12.13 derives in (12.136) that satisfies (12.139).

In the dictionary (12.121) of Fourier and Dirac vectors where , this theorem proves that M orthogonal matching pursuit iterations are nearly optimal if M ≤ N^1/2/3. This result is attractive because it is simple, but in practice the condition is very restrictive because the dictionary coherence is often not so small. As previously explained, the mutual coherence of a Gabor dictionary is typically above 1/2, and this theorem thus does not apply.

Proof.

The proof begins by computing a solution with support that is in Λ, and then proves that it is unique. We denote by a_Λ a vector defined over the index set Λ. To compute a solution with a support in Λ, we consider a solution of the following problem:

(12.144)

Let be defined by for p ∈ Λ and for p ∈ Λ^c. It has a support . We prove that is also the solution of the 1¹ Lagrangian minimization (12.140) if (12.142) is satisfied.

Let h be defined by

(12.145)

The optimality condition (12.141) applied to the minimization (12.144) implies that

To prove that is the solution of (12.140), we must verify that |h[q]| ≤ 1 for q∈Λ^c. Equation (12.145) shows that the coefficients h_Λ of h inside Λ satisfy

Since A_Λ > 0, the vectors indexed by Λ are linearly independent and

(12.146)

and (12.145) implies that

(12.147)

The expression (12.147) of h_Λc shows that

(12.148)

(12.149)

We saw in (12.130) that . Since , we get

(12.150)

But T > ‖f − f_Λ‖(1 – ERC(Λ))⁻¹, so ‖hΛc‖_∞ < 1, which proves that is indeed a solution with .

To prove that is the unique solution of (12.140), suppose that is another solution. Then, necessarily, because otherwise the coefficients would have a strictly smaller Lagrangian. This proves that

and thus that is also supported inside Λ. Since and is invertible, , which proves that the solution of (12.140) is unique.

Let us now prove the approximation result (12.143). The optimality conditions (12.141) prove that

For any p∈Λ 〈φ_p, f〉 = 〈φ_p, f_Λ〉, so

Since , it results that , and since ‖φ_Λh‖² ≥ A_Λ‖h‖², we get

(12.151)

Since T = λ ‖f − f_Λ‖(1 – ERC(Λ))⁻¹, it results that

(12.152)

Moreover, f − f_Λ is orthogonal to , so

Inserting (12.152) proves (12.143).

This theorem proves that if T is sufficiently large, then the 1¹ Lagrangian pursuit selects only vectors in Λ. At one point it stops selecting vectors in Λ but the error has already reached the upper bound (12.143). If f = f_Λ and ERC(Λ) < 1, then (12.143) proves that a basis pursuit recovers all the atoms in Λ and thus reconstructs f. It is, therefore, an Exact Recovery Criterion for a basis pursuit.

An exact recovery is obtained by letting T go to zero in a Lagrangian pursuit, which is equivalent to solve a basis pursuit

(12.153)

Suppose that f_M = f_Λ is the best M-term approximation of f from M ≤ 1/3μ(D) dictionary vectors. Similar to Theorem 12.14, Theorem 12.15 implies that the 1¹ pursuit approximation computed with T = ‖f − f_M‖/2 satisfies

(12.154)

Indeed, as in the proof of Theorem 12.14, we verify that (ERC(Λ) – 1)⁻¹ < 2 and A_Λ ≥ 2/3.

Although ERC(Λ) > 1, the support Λ of f∈V_Λ may still be recovered by a basis pursuit. Figure 12.20 gives an example with two Gabor atoms with Heisenberg boxes, which overlap and that are recovered by a basis pursuit despite the fact that ERC(Λ) > 1. For an 1¹ Lagrangian pursuit, the condition ERC(Λ) < 1 can be refined with a more precise sufficient criterion introduced by Fuchs [266]. It depends on the sign of the coefficients a[p] supported in Λ, which recover f = φ^*a. In (12.150) as well as in all subsequent derivations and thus in the statement of Theorem 12.15, can be replaced by

(12.155)

In particular, if F(f, Λ) < 1, then the support Λ of f is recovered by a basis pursuit. Moreover, Dossal [231] showed that if there exists with such that , with arbitrary signs for a[p] when , then f is also recovered by a basis pursuit. By using this criteria, one can verify that if |Λ| is small, even though Λ may include very correlated vectors such as Gabor atoms of close time and frequency, we are more likely to recover Λ with a basis pursuit then with an orthogonal matching pursuit, but this recovery can be unstable.