IEEE Circuits and Systems Magazine - Q1 2020 - 43

B. Explaining CS With Mutual Coherence
Figure 2 helps understanding how CS works by applying
it to the particular case n = d = 3, m = 2 and l = 1.
As a general property, any B decomposes its n-dimensional domain into two orthogonal subspaces: its
(n - m)- dimensional kernel ker B (the green line on the
left of Figure 2) and the m-dimensional image subspace
imB < (the green plane on both sides of Figure 2). Since
vectors in ker B disappear in the mapping, multiplication by B amounts to projection onto imB < . Vice versa,
once we are given a measurement vector y l, the equation y l = Bp defines the affine (n - m)- dimensional subspace spanned by the sum B + y l + e (where $ + indicates
pseudo-inversion) for any e ! ker B and represented,
FIRST QUARTER 2020

imB

⊥

Going back to the noisy case h 2 0, not to be
fooled by disturbances, one should require that for
any two l-sparse vectors pl ! pm , the two vectors Bpl
and Bpm are sufficiently far apart, i.e., that B (pl - pm )
is not too small.
Since if pl and pm are l-sparse, then pl - pm is up to
2l-sparse, and we need B to behave in a proper way
when applied to 2l-sparse vectors.
This is formalized by the definition of the RIP that requires B to be almost an isometry (i.e., a transformation
that preserves length) when it is applied to 2l-sparse
vectors. RIP is quantified by a Restricted Isometry Constant (RIC) d 2l that is 0 when B is a true isometry and
increases as B departs from that condition.
These ideas have been able to originate the most
widely known guarantees on the possibility of reconstructing x from y by means of (1) [3]. By largely simplifying the sophisticated machinery needed to prove this
result, one knows that if d 2l # 2 - 1 the reconstruction
error is bounded from above and thus cannot completely disrupt the signal. In the noiseless case h = 0 the
reconstruction can be perfect, and the guarantees substantially depend on the same assumption on d 2l .
F u r t h e r m o r e , one can also prove that, if m =
O (l log (n/l)) and one chooses A as a m # n random
matrix whose entries A j, k are independent and identically distributed (i.i.d.), for example, as normals (i.e.,
A j, k + N (0, 1)), then the probability of producing a matrix B that satisfies the RIP property is extremely high
independently of the choice of the dictionary D.
These good news imply a very simple design flow that
is completely agnostic of the features of the signal to acquire with the exception of its sparsity l, and basically
employs i.i.d. random matrices with the proper size.
Yet, since such a design flow is based on guarantees
and thus on worst-case derivations, in practice the performance of this kind of CS systems on typical signals is
much better than what is ensured by theory.

B +y ′

ξ′

y ′ = Bξ
kerB
ξ″

y′ → ξ′

y ″ = Bξ

B +y ″

y″ → ξ″

Figure 2. The mutual-coherence point of view on CS.

for example, by the yellow straight line in Figure 2.
Since l = 1, among all the points of such subspace, the
one corresponding to the signal is that sitting on a coordinate axis, i.e. the pl represented by a yellow dot
in Figure 2.
The same happens for the other measurement vector
y m, that defines the orange affine subspace B + y m + e of
Figure 2 which contains only one point sitting on a coordinate axis, i.e., the orange dot representing pm.
Clearly, this going from y to p is possible since the
projections of the coordinate axis on the green plane
are distinct, as shown on the right of Figure 2 that represents the co-domain of B.
In more general terms, since y = Bp, such projections are the columns of B. Since we are dealing with n
vectors in an m 1 n-dimensional space, they cannot be
orthogonal. Yet, we may ask them to be "as orthogonal
as possible". This is where mutual coherence [14] comes
into play. It is defined considering the columns vectors
B $ , 0, f, B $ ,n - 1 and setting
n ^ B h = max
j!k

B <$ , j B ·, k
B$ ,j 2 B $ ,k

(2)

Mutual coherence is the cosine of the smallest angle between any two vectors B $ ,j and is bounded by
n min # n (B) # 1 with n min = (d - m) / (d - 1) m [15]. In
our toy case, the perfectly symmetric disposition of
the 3 projections in the 2-dimensional plane, implies
n (B) = 1/2 2 that matches the lower bound for d = n = 3
and m = 2 thus making B a very good matrix for CS.
The most well-known result linking mutual coherence with the possibility of reconstructing x from y is
that, in the noiseless case, BP recovers the correct original signal providing that n (B) # 1/ (2l - 1) [16].
In general, to cope with possible disturbances that offset the measurement vectors from its ideal position, one
2

that corresponds to angles of 2/3r between each pair of vectors in
Figure 2
IEEE CIRCUITS AND SYSTEMS MAGAZINE

IEEE Circuits and Systems Magazine - Q1 2020

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2020