We begin with a property of the null space
NNN which is at the heart of proving results on instance-optimality.
We say that
NNN has the Null Space Property if for all
η∈Nη∈Nη in N and all
TTT with
#T≤k#T≤kitalic "#" T <= k we have
∥
η
∥
X
≤
c
1
∥
η
T
C
∥
X
∥
η
∥
X
≤
c
1
∥
η
T
C
∥
X
Intuitively, NSP implies that for any vector in the nullspace the energy will not be concentrated in a small number of entries.
The following are equivalent formulations for NSP
XXX for
kkk :
-
∥η∥X≤c1σk(η)∥η∥X≤c1σk(η)
-
∥
η
T
∥
X
≤
c
1
′
∥
η
T
C
∥
X
∥
η
T
∥
X
≤
c
1
′
∥
η
T
C
∥
X
where
η
=
η
T
+
η
T
C
η
=
η
T
+
η
T
C
.
Note also that the triangle inequality can be used as follows
∥
η
∥
X
=
∥
η
T
+
η
T
C
∥
X
≤
∥
η
T
∥
X
+
∥
η
T
C
∥
X
∥
η
∥
X
=
∥
η
T
+
η
T
C
∥
X
≤
∥
η
T
∥
X
+
∥
η
T
C
∥
X
which shows that (b) is equivalent to NSP.
- If
(Φ,Δ)(Φ,Δ) \( {Φ , Δ} \) is instance optimal on
XXX for the value
kkk , then
ΦΦΦ satisfies the NSP for
2k2k2 k on
XXX with an equivalent constant.
- If
ΦΦΦ has the NSP for
XXX and
2k2k2 k then
∃Δ∃Δ exists Δ s.t.
ΦΦΦ has the instance optimal property for
kkk .
We will prove a slightly weaker version of this to save time. We first prove that instance optimality for
kkk implies NSP
XXX for
kkk (hence this is slightly weaker than advertised) . Let
η∈Nη∈Nη in N and set
z=Δ(0)z=Δ(0)z =Δ { \( 0 \)} then
∥
η
−
z
∥
≤
c
0
σ
k
(
η
)
∥
η
+
z
∥
≤
c
0
σ
k
(
η
)
∥
η
∥
≤
max
{
∥
η
−
z
∥
,
∥
η
+
z
∥
}
≤
c
0
σ
k
(
η
)
instance optimal property
−
z
∈
N
triangle inequality
∥
η
−
z
∥
≤
c
0
σ
k
(
η
)
∥
η
+
z
∥
≤
c
0
σ
k
(
η
)
∥
η
∥
≤
max
{
∥
η
−
z
∥
,
∥
η
+
z
∥
}
≤
c
0
σ
k
(
η
)
instance optimal property
−
z
∈
N
triangle inequality
(1)We now prove 2. Suppose
ΦΦΦ has the NSP for
2k2k2 k . Given
yyy ,
ℱℱℱ(y)={x:Φ(x)=y}(y)={x:Φ(x)=y}{ \( y \)} ={ lbrace {x : Φ { \( x \)} = y} rbrace}. Let us define the decoder
ΔΔΔ by
Δ
(
y
)
:
=
arg
min
{
σ
K
(
x
)
X
:
x
∈
ℱ
(
y
)
}
Δ
(
y
)
:
=
arg
min
{
σ
K
(
x
)
X
:
x
∈
ℱ
(
y
)
}
, then
∥
x
−
Δ
(
Φ
(
x
)
)
∥
X
=
∥
x
−
x
′
∥
X
≤
c
1
σ
2
K
(
x
−
x
′
)
≤
c
1
(
σ
K
(
x
)
−
σ
K
(
x
′
)
)
specific 2K term approximation
≤
2
c
1
σ
K
(
x
)
∥
x
−
Δ
(
Φ
(
x
)
)
∥
X
=
∥
x
−
x
′
∥
X
≤
c
1
σ
2
K
(
x
−
x
′
)
≤
c
1
(
σ
K
(
x
)
−
σ
K
(
x
′
)
)
specific 2K term approximation
≤
2
c
1
σ
K
(
x
)
QED.
Note that the instance optimal property automatically gives reproduction of
KKK -sparse signals.
At this stage the challenge is to create
ΦΦΦ with this instance optimal property. For this we shall use the restricted isometry property as introduced earlier and which we now recall.
