Now we consider another way (actually two related ways) to measure optimality of an encoder/decoder pair.
- Instance optimality. Suppose we are in
ℝNℝNℝ^N with an
n×Nn×Nn times N measurement matrix
ΦΦΦ and a decoder
ΔΔΔ . Recall that
σ
k
(
x
)
X
:
=
inf
z
:
#
z
≤
k
∥
x
−
z
∥
X
.
σ
k
(
x
)
X
:
=
inf
z
:
#
z
≤
k
∥
x
−
z
∥
X
.
(1)
∥
x
−
Δ
Φ
(
x
)
∥
X
≤
C
0
σ
k
(
x
)
X
∥
x
−
Δ
Φ
(
x
)
∥
X
≤
C
0
σ
k
(
x
)
X
(2) - Mixed-norm instance optimality (MNIO). Let
q<pq<pq <p . The encoder/decoder pair
Φ,ΔΦ,ΔΦ ,Δ is MNIO for
p,q,kp,q,kp ,q ,k , and
C0C0C_0 if
∥
x
−
Δ
Φ
(
x
)
∥
ℓ
p
N
≤
C
0
σ
k
(
x
)
ℓ
q
N
k
1
∕
q
−
1
∕
p
.
∥
x
−
Δ
Φ
(
x
)
∥
ℓ
p
N
≤
C
0
σ
k
(
x
)
ℓ
q
N
k
1
∕
q
−
1
∕
p
.
(3)
∥
x
−
Δ
Φ
(
x
)
∥
ℓ
2
N
≤
C
0
σ
k
(
x
)
ℓ
1
N
.
∥
x
−
Δ
Φ
(
x
)
∥
ℓ
2
N
≤
C
0
σ
k
(
x
)
ℓ
1
N
.
(4)
∥
x
−
Δ
Φ
(
x
)
∥
ℓ
2
N
≤
C
0
σ
k
(
x
)
ℓ
1
N
k
.
∥
x
−
Δ
Φ
(
x
)
∥
ℓ
2
N
≤
C
0
σ
k
(
x
)
ℓ
1
N
k
.
(5)
Let’s focus on instance optimality. It would be interesting to know whether a given
ΦΦΦ satisfies this property. To answer this question, we state an equivalent condition to instance optimality.
Consider the statements
- Φ,ΔΦ,ΔΦ ,Δ is instance optimal of order
kkk on
XXX .
- ΦΦΦ has the following nullspace property (NSP):
∥
η
∥
X
≤
C
1
∥
η
T
c
∥
X
∀
η
∈
N
(
Φ
)
,
#
T
≤
k
.
∥
η
∥
X
≤
C
1
∥
η
T
c
∥
X
∀
η
∈
N
(
Φ
)
,
#
T
≤
k
.
-
∥
η
∥
X
≤
C
1
σ
k
(
η
)
X
∀
η
∈
N
(
Φ
)
.
∥
η
∥
X
≤
C
1
σ
k
(
η
)
X
∀
η
∈
N
(
Φ
)
.
-
∥
η
T
∥
X
≤
C
1
′
∥
η
T
c
∥
X
∀
η
∈
N
(
Φ
)
,
#
T
≤
k
.
∥
η
T
∥
X
≤
C
1
′
∥
η
T
c
∥
X
∀
η
∈
N
(
Φ
)
,
#
T
≤
k
.
Then (b) and (c) are equivalent with the same constant; (d) is equvalent to (b) and (c) but with a different constant. Also (a) with a value
kkk implies (b) with the same
kkk , and (b) with a value
2k2k2 k implies (a) with a value
kkk .
