Last time we proved that for each
k
≤
c
0
n
log
N
/
n
k
≤
c
0
n
log
N
/
n
,
there exists an n×Nn×N matrix ΦΦ
and a decoder ΔΔ such that
- (a) -
∥x-ΔΦ(x)∥ ℓ 1 ≤c 0 σ k (x) ℓ 1 ∥x-ΔΦ(x)∥ ℓ 1 ≤c 0 σ k (x) ℓ 1
- (b) - ∥x-ΔΦ(x)∥ ℓ 2 ≤c 0 σ k (x) ℓ 1 k∥x-ΔΦ(x)∥ ℓ 2 ≤c 0 σ k (x) ℓ 1 k
Recall that we can find such a
ΦΦ by setting the entries
[Φ] j,k =φ j,k (ω)[Φ] j,k =φ j,k (ω) to be realizations of
independent and identically distributed Gaussian random variables.
Our decoding “algorithm” is:
Δ
(
y
)
:
=
arg
min
x
∈
F
(
y
)
σ
k
(
x
)
ℓ
1
Δ
(
y
)
:
=
arg
min
x
∈
F
(
y
)
σ
k
(
x
)
ℓ
1
(1)
where
F(y):={x:Φ(x)=y}F(y):={x:Φ(x)=y}. In general, this
algorithm is not implementable. This deficiency, however, is
easily repaired. Specifically, define
Δ 1 (y):=argmin x∈F(y)
∥
x
∥
ℓ
1
.Δ 1 (y):=argmin x∈F(y)
∥
x
∥
ℓ
1
.(2)
Then (a) and (b) hold for
Δ 1 Δ 1 in place of
ΔΔ. This
decoding algorithm is equivalent to solving a linear programming
problem, thus it is tractable and can be solved using techniques
such as the interior point method or the simplex method. In
general, these algorithms have computational complexity
O(N 3 )O(N 3 ).
For very large signals this can become prohibitive, and hence
there has been a considerable amount of research in faster
decoders (such as decoding using greedy algorithms).
The construction of a ΦΦ from realizations of Gaussian random
variables is guaranteed to work with high probability.
However, we would like to know, given a particular instance of
ΦΦ, do (a) and (b) still hold. Unfortunately, this is
impossible to check (since, to show that ΦΦ satisfies the MRIP
for kk, we need to consider all possible submatrices of
ΦΦ). Furthermore, we would like to build ΦΦ that can be
implemented in circuits. We also might want fast decoders ΔΔ
for these ΦΦ. Thus we also may need to be more restrictive in
building ΦΦ. Two possible approaches that move in this
direction are as follows:
- Find ΦΦ that we can build such that we can prove
instance optimality in ℓ 1 ℓ 1 for a smaller range of kk,
i.e.,
∥x-ΔΦ(x)∥ ℓ 1 ≤c 0 σ k (x) ℓ 1 ∥x-ΔΦ(x)∥ ℓ 1 ≤c 0 σ k (x) ℓ 1 (3)
for
k<Kk<K. If we are willing to sacrifice and let KK be
smaller than before, for example, K≈nK≈n, then we
might be able to prove that Φ T t Φ T Φ T t Φ T is diagonally
dominant for all TT such that ♯T=2k♯T=2k, which would ensure
that ΦΦ satisfies the MRIP.
-
Consider Φ(ω)Φ(ω) where ωω is a random
seed that generates a ΦΦ. It is possible to show that give
xx, with high probability, Φ(ω)(x)=yΦ(ω)(x)=y encodes xx in
an ℓ 2 ℓ 2 -instance optimal fashion:
∥x-x ¯∥ ℓ 2 ≤2σ k (x) ℓ 2 ∥x-x ¯∥ ℓ 2 ≤2σ k (x) ℓ 2 (4)
for
k≤c 0 n (logN/n) 5/2 k≤c 0 n (logN/n) 5/2 . Thus, by generating
many such matrices we can recover any xx with high
probability.
Another practical problem is that of
encoding the measurements yy. In a real system these measurements
must be quantized. This problem was addressed by Candes, Romberg,
and Tao in their paper Stable Signal Recovery from Incomplete
and Inaccurate Measurements. They prove that if yy is quantized
to y ¯y ¯, and if x∈U(ℓ p )x∈U(ℓ p ) for p≤1p≤1, then
we get optimal performance in terms the number of bits required
for a given accuracy. Notice that their result applies only to
the case where p≤1p≤1. One might expect that this argument
could be extended to pp between 1 and 2, but a warning is in
order at this stage:
Fix 1<p≤21<p≤2. Then there exist ΦΦ and ΔΔ
satisfying
∥x-ΔΦ(x)∥ ℓ p ≤C 0 σ k (x) ℓ p ∥x-ΔΦ(x)∥ ℓ p ≤C 0 σ k (x) ℓ p (5)
if
k≤c 0 N 2-2/p 1-2/p n logN/n p 2-p .k≤c 0 N 2-2/p 1-2/p n logN/n p 2-p .(6)
Furthermore, this range of k is the best possible (save for the
loglog term).
Examples:
- p=1p=1, we get our original results
- p=2p=2, we do not
get instance optimal for k=1k=1 unless n≈Nn≈N
- p=3 2p=3 2, we only get instance optimal if k≤c 0 N -2 n logN/n 3 k≤c 0 N -2 n logN/n 3
