We say that an
n×Nn×Nn times N matrix
ΦΦΦ has the restricted isometry property (RIP) for
kkk if for each
T⊆{1,…,N}T⊆{1,…,N}T subseteq { lbrace {1 , dotslow , N} rbrace} such that
#T≤k#T≤kitalic "#" T <= k ,
ΦTΦTΦ_T (the matrix formed by choosing the columns of
ΦΦΦ whose indices are in
TTT ) has the property
Table 1
|
(
1
−
δ
k
)
∥
x
T
∥
ℓ
2
≤
∥
Φ
T
(
x
)
∥
ℓ
2
≤
(
1
+
δ
k
)
∥
x
T
∥
ℓ
2
(
1
−
δ
k
)
∥
x
T
∥
ℓ
2
≤
∥
Φ
T
(
x
)
∥
ℓ
2
≤
(
1
+
δ
k
)
∥
x
T
∥
ℓ
2
|
(RIP) |
where
0<δk<10<δk<10 <δ_k <1 . This useful definition is by Candes and Tao. The idea is that the embedding of a
kkk -dimensional space in
MMM -dimensional space almost preserves norm – like an isometry. Another way of looking at it is to consider the matrix
ΦTtΦTΦTtΦTΦ_T^t Φ_T , of size
k×kk×kk times k . This matrix is symmetric, positive definite, and it’s eigen-values are between
1−δk1−δk1 - δ_k and
1+δk1+δk1 +δ_k .
I prefer the following modified condition (dubbed the MIRP), which is more convenient for mathematical analysis:
Table 2
|
(
c
1
)
−
1
∥
x
T
∥
ℓ
2
≤
∥
Φ
T
(
x
)
∥
ℓ
2
≤
c
1
∥
x
T
∥
ℓ
2
(
c
1
)
−
1
∥
x
T
∥
ℓ
2
≤
∥
Φ
T
(
x
)
∥
ℓ
2
≤
c
1
∥
x
T
∥
ℓ
2
|
(MRIP) |
We can now state the following theorem.
If
ΦΦΦ satisfies MRIP for
2k2k2 k then
∃Δ∃Δ exists Δ s.t.
(Φ,Δ)(Φ,Δ) \( {Φ , Δ} \) is instance optimal for
ℓ1Nℓ1Nℓ_1^N for
KKK .
This shows that whenever we have a matrix
ΦΦΦ satisfying the MRIP for
2k2k2 k then it will perform well on encoding vectors (at least in the sense of
ℓ1Nℓ1Nℓ_1^N accuracy). The question is how can we construct measurement matrices with this property? We can construct
ΦΦΦ using Gaussian entries and then normalizing the columns.
∃∃ exists constant
c>0c>0c >0 s.t. if
k≤cnlog(N∕n)k≤cnlog(N∕n)k <= c n over {l { \( {N ∕ n} \)}} then with high probability
ΦΦΦ satisfies RIP and MRIP for
kkk .
Given
NNN and
nnn , the range of
kkk in the above results reflects how accurately we can recover data. There is another constant
c′c′c^′ that serves as a converse bound for Theorem 3. This converse can be derived using Gluskin widths.
The following generic problem is of great interest: Consider the class of matrices
ℳ
=
{
Φ
M
×
N
,
Φ
has some prescribed property(eg. Toeplitz, circulant, etc.)
}
ℳ
=
{
Φ
M
×
N
,
Φ
has some prescribed property(eg. Toeplitz, circulant, etc.)
}
. What is the largest
kkk for which such a matrix can have the MRIP.
