arXiv:1803.00773v2 [] 7 Mar 2018

Optimality of 1-norm regularization among
weighted 1-norms for sparse recovery: a case study
on how to find optimal regularizations
Yann Traonmilina and Samuel Vaiterb
a
CNRS, Institut de Mathématiques de Bordeaux, 33400 Talence, France; b CNRS, Institut de
Mathématiques de Bourgogne, 9 avenue Alain Savary, 21000, Dijon

E-mail: a yann.traonmilin@math.u-bordeaux.fr,

b

samuel.vaiter@u-bourgogne.fr

Abstract. The 1-norm was proven to be a good convex regularizer for the recovery of sparse
vectors from under-determined linear measurements. It has been shown that with an appropriate
measurement operator, a number of measurements of the order of the sparsity of the signal (up
to log factors) is sufficient for stable and robust recovery. More recently, it has been shown that
such recovery results can be generalized to more general low-dimensional model sets and (convex)
regularizers. These results lead to the following question: to recover a given low-dimensional
model set from linear measurements, what is the “best” convex regularizer? To approach this
problem, we propose a general framework to define several notions of “best regularizer” with
respect to a low-dimensional model. We show in the minimal case of sparse recovery in dimension
3 that the 1-norm is optimal for these notions. However, generalization of such results to the
n-dimensional case seems out of reach. To tackle this problem, we propose looser notions of best
regularizer and show that the 1-norm is optimal among weighted 1-norms for sparse recovery
within this framework.

1. Introduction
We consider the observation model in a Hilbert space H (with associated norm k · kH ):
y = M x0

(1)

where M is an under-determined linear operator, y is a m-dimensional vector and x0 is the
unknown. We suppose that x0 belongs to a low-dimensional model Σ (a union of subspaces).
We consider the following minimization program.
x∗ ∈ arg min R(x)
M x=y

(2)

where R is a regularization function. A huge body of work gives practical regularizers ensuring
that x∗ = x0 for several low-dimensional models (in particular sparse and low rank models, see
[7] for a most complete review of these results). In this work, we aim at finding the “best”
regularizer for exact recovery of x0 ∈ Σ. Ideally we would like to set R = ιΣ (the characteristic
function of Σ) but it is not practical in many cases (sparse and low rank recovery) as it is
generally not convex, and even NP-hard to compute as a combinatorial problem. Consequently,

we restrict the search for the best regularizer to a class of interesting regularizers C. In our
examples, the set C is a subset of the set of convex functions. Other interesting classes might
be considered, such as partly smooth functions [12].
1.1. Best regularizer with respect to a low dimensional model
Defining what is the ”best” regularizer in C for recovery is not immediate. Ideally, to fit to
the inverse problem, we must define a compliance measure that depends on both the kind of
unknown and measurement operator we consider. If we have some knowledge that M ∈ M
where M is a set of linear operators, we want to define a compliance measure AΣ,M (R) that
tells us if a regularizer is good in these situations, and maximize it. Such maximization might
yield a function R∗ that depends on M (e.g., in [10], when looking for tight continuous relaxation
of the ℓ0 penalty a dependency on M appear). We aim for a more universal notion of optimal
regularizer that does not depend on M . Hence, we look for a compliance measure AΣ (R) and
its maximization
R∗ ∈ arg max AΣ (R).
(3)
R∈C

In the sparse recovery example studied in this article, the existence of a maximum of AΣ (R) is
verified. However, we could ask ourselves what conditions on AΣ (R) and C are necessary and
sufficient for the existence of a maximum, which is out of the scope of this article.
1.2. Compliance measures
When studying recovery with a regularization function R, two types of guarantees are generally
used: uniform and non-uniform. To describe these recovery guarantees, we use the following
definition of descent vectors.
Definition 1.1 (Descent vectors). For any x ∈ H, the collection of descent vectors of R at x is
TR (x) := {z ∈ H : R(x + z) ≤ R(x)} .

(4)

S
We write TR (Σ) := x∈Σ TR (x). Recovery is characterized by descent vectors (recall that x∗
is the result of minimization (2)):

• Uniform recovery: Let M a linear operator. Then “for all x0 ∈ Σ, x∗ = x0 ” is equivalent
to TR (Σ) ∩ ker M = {0}.
• Non-uniform recovery: Let M a linear operator and x0 ∈ Σ. Then x∗ = x0 is equivalent to
TR (x0 ) ∩ ker M = {0}.

Hence, a regularization function R is ”good“ if TR (Σ) leaves a lot of space for ker M to not
intersect it (trivially). In dimension n, if there is no orientation prior on the kernel of M , the
amount of space left can be quantified by the ”volume“ of TR (Σ) ∩ S(1) where S(1) is the unit
sphere with respect to k · kH . Hence a compliance measure for uniform recovery can be defined
as
vol (TR (Σ) ∩ S(1))
.
(5)
AU
Σ (R) := 1 −
vol(S(1))
More precisely, here, the volume vol(E) of a set E is the measure of E with respect to the uniform
measure on the sphere S(1) (i.e. the n−1-dimensional Haussdorf measure of TR (Σ)∩S(1)). When
maximizing this compliance measure with convex regularizers (proper, coercive and continuous),
it has been shown that we can limit ourselves to atomic norms with atoms included in the model
[11, Lemma 2.1]. When looking at non-uniform recovery for random Gaussian measurements, the
R (x0 )∩S(1))
quantity vol(Tvol(S(1))
represents the probability that a randomly oriented kernel of dimension

1 intersects (non trivially) TR (x0 ). The highest probability of intersection with respect to x0
quantifies the lack of compliance of R, hence we can define:
vol (TR (x) ∩ S(1))
vol(S(1))
x∈Σ

U
AN
Σ (R) := 1 − sup

(6)

Note that this can be linked with the Gaussian width and statistical dimension theory of sparse
recovery [5, 1].
Remark 1.1. In infinite dimension, the sphere S(1) is of infinite volume making the measures
above uninteresting. However, [11] and [9] show that we can often come back to a lowdimensional recovery problem in an intermediate finite (potentially high dimensional) subspace of
H. Adapting the definition of S(1) to this subspace allows to extend these compliance measures.
Another possibility for the n-dimensional case, which we develop in this article, is to use
recovery results based on the restricted isometry property (RIP). They have been shown to be
adequate for multiple models [11], to be tight in some sense [6] for sparse and low rank recovery,
to be necessary in some sense [3] and to be well adapted to the study of random operators [9].
In particular, it has been shown that if M has a RIP with constant δ < δΣ (R) on the secant
set Σ − Σ, with δΣ (R) being fully determined by Σ and R [11], then stable recovery is possible.
Hence, by taking
ARIP
Σ (R) := δΣ (R),

(7)

the larger ARIP
is, the less stringent are RIP recovery conditions for recovery of elements of Σ
Σ
with R. We develop these ideas more precisely in Section 3 and perform the maximization with
such measure in the sparse recovery case.
1.3. Optimality results
Within this framework we show the following results:
(i) In Section 2, when H = R3 , Σ = Σ1 the set of 1-sparse vectors and C is the set of (symmetric)
NU
atomic norms with atoms included in the model. Both AU
Σ (R) and AΣ (R) are maximized
1
by multiples of the ℓ -norm (Theorem 2.1). In this case, it is possible to exactly compute
and maximize the compliance measure. While this study gives a good geometrical insight of
the quantities at hand, extending these exact calculations to the general k-sparse recovery
in dimension n seems out of reach.
(ii) In Section 3, we describe precisely how compliance measures based on RIP recovery can
be defined. We then study two of these measures (based on state of the art recovery
guarantees) for H = Rn , Σ = Σk the set of k-sparse vectors (vectors with at most k non
zero coordinates) and C the set of weighted ℓ1 -norms. We show that both of these measures
are maximized by multiples of the ℓ1 -norm (Theorem 3.1 and Theorem 3.2).
2. The case of 1-sparse vectors in 3D
We investigate in detail the case of 3-dimensional vectors which are 1 sparse, i.e., the simplest
interesting case (uniform recovery of 1-sparse vectors in 2 dimensions is impossible). Here, we
have Σ = Σ1 and H = R3 . We restrict our attention to weighted ℓ1 -norms, i.e., atomic norms
of the form C = {k · kw : kzkw = w1 |z1 | + w2 |z2 | + w3 |z3 |} = {k · kA : A = {±wi−1 ei }i=1,3 , wi >
0, max |wi | = 1} (where k · kA is the atomic norm generated by atoms A ). To maximize AU
Σ
U
(respectively AN
Σ ), we have to compute the surface of the intersections of 3 descent cones with
the unit sphere S(1), (respectively the surface of the biggest possible intersection of a descent
cone with S(1)).

e1
µ1 e1
α13

α12
α11
α22

α31
µ3 e3
e3

α33

α21
α23 µ2 e2

e2

α32

Figure 1. Left: a representation of the surface of interest. Right: parameterization of the
angles of a tetrahedron.
As shown in Figure 1, with symmetries, we need to compute the intersection of 3 descent
cones of a weighted ℓ1 -norm at 1-sparse vectors. This is the object of Lemma 2.1. Note that
in the case of asymmetrical atoms, we would then need to calculate 6 × 4 intersections of the
sphere with a tetrahedron. To ease the notations, we introduce the following quantities which
represent the cosine of the angles of a tetrahedron of interest. For i 6= j, set µi = wi−1 ,βij (µ) =
− 1

Q
2
and βii = i6=j βij .
cos(αij ) = 1 + (µj /µi )2
Lemma 2.1. Let i ∈ {1, 2, 3}, x ∈ Rei a 1-sparse vector and µ1 , µ2 , µ3 > 0 three positive real
numbers. Then,



1
−1
(8)
vol Tk·kw (x) ∩ S(1) = 4 tan
1 + ci (µ)
where
X
Y
ci (µ) = 1 +
βij (µ) +
βij (µ).
(9)
j6=i

j6=i

With this Lemma 2.1, we can prove that the ℓ1 -norm is the best regularizer for 1-sparse
signals both for uniform and non-uniform recovery among all weighted ℓ1 -norms.

Theorem 2.1. Let Σ = Σ1 the set of 1-sparse vectors in R3 and C = {k · kw : kzkw =
w1 |z1 | + w2 |z2 | + w3 |z3 |, max |wi | = 1, wi > 0}. The ℓ1 -norm is the best regularizer among
the class C for Σ, both for the uniform and non-uniform case,
NU
arg max AU
Σ (R) = arg max AΣ (R) = k · k1
R∈C

R∈C

We expect a similar result if C is generalized to asymmetrical atomic norms. To extend these
exact calculations to the n-dimensional case, we would need to be able to compare intersections
of spheres and descent cones of R without an analytic formula, which appears to be a very
difficult task.
3. Compliance measures based on the RIP
We start by recalling definitions and results about RIP recovery guarantees.
Definition 3.1 (RIP constant). In a Hilbert space H, let Σ a union of subspaces. Let M a
linear map, the RIP constant of M is defined as
δ(M ) =

inf

x∈Σ−Σ

kM xk2H
−1 ,
kxk2H

where Σ − Σ (differences of elements of Σ) is called the secant set.

(10)

suf f
suf f
In [11], an explicit constant δΣ
(R) is given, such that δ(M ) < δΣ
(R) guarantees exact
recovery of elements of Σ by minimization (2). This constant is only sufficient (and sharp in
some sense for sparse and low rank recovery). An ideal RIP based compliance measure would
sharp
be to use a sharp RIP constant δΣ
(R) (which is not explicit, it is an open question to derive
closed form formulations of this constant for sparsity and other low-dimensional models) defined
as:
sharp
δΣ
(R) :=
inf
δ(M ).
(11)
M :ker M ∩TR (Σ)6={0}

It is the best RIP constant of measurement operators where uniform recovery fail. The lack of
sharp
(R) limits the possibilities of exact optimization with respect to R.
analytic expression of δΣ
We propose to look at two compliance measures:
• Measures based on necessary RIP conditions [6] which yields sharp recovery constants for
particular set of operators, e.g.
nec
δΣ
(R) :=

inf

z∈TR (Σ)\{0}

δ(I − Πz ).

(12)

where Πz is the orthogonal projection onto the one-dimensional subspace span(z) (other
intermediate necessary RIP constants can be defined). Another open question is to
nec (R) = δ sharp (R) generally or for some particular models.
determine whether δΣ
Σ
suf f
(R) from [11]).
• Measures based on sufficient RIP constants for recovery (e.g. δΣ

Note that we have the relation

suf f
sharp
nec
δΣ
(R) ≤ δΣ
(R) ≤ δΣ
(R).

(13)

To summarize, in the following, instead of considering the most natural RIP based compliance
sharp
measure (based on δΣ
(R) ), we use the best known bounds of this measure.
3.1. Compliance measures based on necessary RIP conditions
In this case, instead of working with actual RIP constants, it is easier to use (equivalently) the
restricted conditioning.
Definition 3.2 (Restricted conditioning).
γ(M ) :=

supx∈(Σ−Σ)∩S(1) kM xk2H
inf x∈(Σ−Σ)∩S(1) kM xk2H

.

(14)

The RIP constant δ(M ) is increasing with respect to γ(M ). In the following, we consider the
compliance measure
ARIP,nec
(R) := γΣ (R) =
Σ

inf

z∈TR (Σ)\{0}

γ(I − Πz ).

(15)

When maximizing ARIP,nec
(R), we look at optimal regularizers for recovery with tight frames
Σ
with a kernel of dimension 1.
From here, we specialize to Σ = Σk and H = Rn . Hence Σ − Σ = Σ2k with k ≥ 1 and n ≥ 3
(for n < 3 uniform recovery with convex regularizer is not possible for non-invertible M ). To
show optimality of the ℓ1 -norm, we use the following characterization of ARIP,nec
(R).
Σ
Lemma 3.1. Let Σ = Σk and H = Rn . Then
(R) =
ARIP,nec
Σ

1
1 − inf z∈TR (Σ)\{0} supx∈(Σ−Σ)∩S(1)

hx,zi2
kzk2H

.

(16)

We consider the set C = {R : R(x) =

P

wi |xi | = kxkw , max |wi | = 1, w ∈ (R∗+ )n }. Note that

kzT2c k2Σ
= arg inf BΣ (R)
R∈C z∈TR (Σ)\{0} kzT2 k2
R∈C
2

arg sup ARIP,nec
(R) = arg inf
Σ
R∈C

sup

(17)

where T2 is a notation for the support of 2k biggest coordinates in z, i.e. for all i ∈ T2 , j ∈ T2c ,
we have |zi | ≥ |zj |.
Studying the quantity BΣ (R) :=

kzT c k2Σ

sup

2

z∈TR (Σ)\{0}

kzT2 k22

for R ∈ C permits to conclude.

Theorem 3.1. Let Σ = Σk , H = Rn and C = {R : R(x) =
(R∗+ )n }. Suppose n ≥ 2k, then

P

wi |xi | = kxkw , max |wi | = 1, w ∈

k · k1 = arg sup ARIP,nec
(R).
Σ

(18)

R∈C

In the next section, we will see that the optimization of the sufficient RIP constant leads to
very similar expressions.
3.2. Compliance measures based on sufficient RIP conditions
In [11], it was shown for Σ a union of subspaces and an arbitrary regularizer R, that an explicit
suf f
RIP constant δΣ
From here we set Σ := Σk ,
P (R) is sufficient to guarantee reconstruction.
C = {R : R(x) =
wi |xi | = kxkw , max |wi | = 1, w ∈ (R∗+ )n }.

suf f
Proposition 3.1. Let Σ = Σk the set of k-sparse vectors. Consider the constant δΣ
(R) from
[11][Eq. (5)], we have:
suf f
δΣ
(R) = s

1
sup
z∈TR (Σ)\{0}

kzT c k2Σ
kzT k22

(19)

+1

where T denotes the support of the k biggest coordinates of z and k · kΣ is the atomic norm
generated by Σ ∩ S(1) (the convex gauge induced by the convex envelope of Σ ∩ S(1)).
In the following, we use

f
suf f
ARIP,suf
(R) := δΣ
(R).
Σ

(20)

suf f
It must be noted that characterization of Proposition 3.1 was used as a lower bound on δΣ
suf f
in [11] (hence this part of the proof of the control of δΣ
in [11] is exact).
Similarly to the necessary case, from Proposition 3.1, we have

kzT c k2Σ
= arg inf DΣ (R)
R∈C z∈TR (Σ)\{0} kzT k2
R∈C
2

f
arg sup ARIP,suf
(R) = arg inf
Σ
R∈C

sup

where T denotes the support of the k biggest coordinates of z and DΣ (R) :=

(21)
sup

z∈TR (Σ)\{0}

kzT c k2Σ
.
kzT k22

Remark the similarity between the fundamental quantity to optimize for the necessary case and
the sufficient case BΣ (R) and DΣ (R). Studying the quantity DΣ (R) for R ∈ C leads to the
result.
P
Theorem 3.2. Let Σ = Σk , H = Rn and C = {R : R(x) =
wi |xi | = kxkw , max |wi | = 1, w ∈
∗
n
(R+ ) }. Suppose n ≥ 2k, then
f
k · k1 = arg sup ARIP,suf
(R).
Σ
R∈C

(22)

4. Discussion and future work
We have shown that (not surprisingly) the ℓ1 -norm is optimal among weighted ℓ1 -norms for
sparse recovery for several notions of compliance. This result had to be expected due to
symmetries of the problem. However, the important point is that we could explicitly quantify
the notion of good regularizer. This is promising for the search of optimal regularizers for more
complicated low-dimensional models such as sparse and low rank models or hierarchical sparse
models. For the case of sparsity, we expect to be able to generalize the optimality of the ℓ1 -norm
to the more general case of atomic norms with atoms included in the model. We also expect
similar result for low-rank recovery and the nuclear norm as technical tools are very similar.
It must be noted that for RIP compliance measures, we did not use a constructive proof
(we exhibited the maximum of the compliance measure). A constructive proof, i.e. an exact
calculation and optimization of the quantities BΣ (R) and DΣ (R) would be more satisfying as it
would not require the knowledge of the optimum, which is our ultimate objective.
We used compliance measures based on (uniform) RIP recovery guarantees to give results for
the general sparse recovery case, it would be interesting to do such analysis using (non-uniform)
recovery guarantees based on the statistical dimension or Gaussian width of the descent cones
[5, 1]. One would need to precisely lower and upper bound these quantities (similarly to our
approach with the RIP) to get satisfying results.
Finally, while these compliance measures are designed to make sense with respect to known
results in the area of sparse recovery, one might design other compliance measures tailored for
particular needs, in this search for optimal regularizers.
Acknowledgements
This work was partly supported by the CNRS PEPS JC 2018 (project on efficient
regularizations). The authors would like to thank Rémi Gribonval for his insights in this problem.
References
[1] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp. Living on the edge: phase transitions in convex
programs with random data. Information and Inference, 3(3):224–294, 2014.
[2] A. Argyriou, R. Foygel, and N. Srebro. Sparse Prediction with the k-Support Norm. Advances in Neural
Information Processing Systems, 25:1457–1465, 2012.
[3] A. Bourrier, M. Davies, T. Peleg, P. Perez, and R. Gribonval. Fundamental performance limits for
ideal decoders in high-dimensional linear inverse problems. Information Theory, IEEE Transactions on,
60(12):7928–7946, 2014.
[4] T. Cai and A. Zhang. Sparse representation of a polytope and recovery of sparse signals and low-rank
matrices. Information Theory, IEEE Transactions on, 60(1):122–132, 2014.
[5] V. Chandrasekaran, B. Recht, P. Parrilo, and A. Willsky. The convex geometry of linear inverse problems.
Foundations of Computational Mathematics, 12(6):805–849, 2012.
[6] M. E. Davies and R. Gribonval. Restricted isometry constants where ℓp sparse recovery can fail for 0 < p ≤ 1.
Information Theory, IEEE Transactions on, 55(5):2203–2214, 2009.
[7] S. Foucart and H. Rauhut. A mathematical introduction to compressive sensing. Springer, 2013.
[8] A. V. Oosterom and J. Strackee. The solid angle of a plane triangle. IEEE Transactions on Biomedical
Engineering, BME-30(2):125–126, 1983.
[9] G. Puy, M. E. Davies, and R. Gribonval. Recipes for stable linear embeddings from hilbert spaces to Rm .
arXiv preprint arXiv:1509.06947, 2015.
[10] E. Soubies, L. Blanc-Féraud, and G. Aubert. A continuous exact ℓ0 penalty (cel0) for least squares regularized
problem. SIAM Journal on Imaging Sciences, 8(3):1607–1639, 2015.
[11] Y. Traonmilin and R. Gribonval. Stable recovery of low-dimensional cones in Hilbert spaces: One RIP to
rule them all. Applied And Computational Harmonic Analysis, In Press, 2016.
[12] S. Vaiter, M. Golbabaee, J. Fadili, and G. Peyré. Model selection with low complexity priors. Information
and Inference: A Journal of the IMA, 4(3):230–287, 2015.

5. Annex
This section describes the tools and proofs used to obtain our results.
5.1. Proofs for Section 2
Proof of Lemma 2.1. We start our proof by observing that the descent cone at x is given by the
conic envelope of the rays defined by vector of the form ±µj ej − µi ei , i.e.,
Tk·kw (x) = cone {±µj ej − µi ei }j6=i .

(23)

Using the symmetry of this set, we can split it as four tetrahedra of equal size, depending on
the sign in front of the vector ej ,
[
cone {(sj µj ej − µi ei )j6=i , −µi ei } .
(24)
Tk·kw (x) =
s∈{−1,1}2

We have reduced the problem to computing the area of the intersection between a tetrahedron
and the unit sphere. To ease the notation, let i = 1, and we consider the cone
T = cone {µ2 e2 − µ1 e1 , µ3 e3 − µ1 e1 , −µ1 e1 } ,

(25)

as depicted in Figure 1. Following [8, Equation (8)], we have that


1
1
vol(T ∩ S(1)) =
tan
,
P3
2
1 + j=1 cos αi,j

(26)

Using the definition of βij , we have that cos αij = βij . Indeed, using standard relation in a
triangle, one has
µ1
µ1
= β12 , cos α13 = p 2
= β13
cos α12 = p 2
2
µ1 + µ2
µ1 + µ23
and, using Al-Kashi relation,

cos α11 = q

µ21
 = β12 β13 = β11 .
 2
2
2
2
µ1 + µ2 µ1 + µ3

Proof of Theorem 2.1. Assume w.l.o.g that 1 = w1 ≥ w2 ≥ w3 > 0, i.e., 1 = µ1 ≤ µ2 ≤ µ3 .
Non-uniform case. Using Lemma 2.1, we compute the quantity
sup vol (TR (x) ∩ S(1)) =
x∈Σ

sup vol (TR (ei ) ∩ S(1))

(27)

i∈{1,2,3}

=

sup 4 tan
i∈{1,2,3}

−1



1
1 + ci (µ)



.

(28)

Now,
U
arg max AN
Σ (R)
R∈C



vol (TR (x) ∩ S(1))
= arg max 1 − sup
R∈C
vol(S(1))
x∈Σ

by definition (6)

= arg min sup vol (TR (x) ∩ S(1))
R∈C x∈Σ

= arg
= arg

min

max 4 tan

1=µ1 ≤µ2 ≤µ3 i∈{1,2,3}

−1



1
1=µ1 ≤µ2 ≤µ3 i∈{1,2,3} 1 + ci (µ)
min

max

1
1 + ci (µ)



Using (28)
tan−1 is increasing

Hence,

U
arg max AN
Σ (R) = arg
R∈C

min

min ci (µ).

1=µ1 ≤µ2 ≤µ3 i∈{1,2,3}

Observe that under the constraint 1 = µ1 ≤ µ2 ≤ µ3 , the minimum of ci (µ) is achieved at i = 3.
Indeed, we have µ22 ≥ µ12 , µ23 ≥ µ12 , thus β12 ≥ β21 ≥ β31 and β13 ≥ β23 ≥ β32 . Since every term
2
3
is positive, we also have that β12 β13 ≥ β21 β23 ≥ β31 β32 . Thus, c1 (µ) ≥ c2 (µ) ≥ c3 (µ). Hence,
we solve the problem



−1/2 

−1/2
1 −1/2
µ2
1
µ2
1+ 1+ 2
+ 1 + 22
+
1+ 2
,
1 + 22
1=µ1 ≤µ2 ≤µ3
µ3
µ3
µ3
µ3
min

which is achieved for µ1 = µ2 = µ3 = 1.
Uniform case. The computation is similar, replacing the minimum with the sum of ci (µ) for
i ∈ {1, 2, 3}.
vol (TR (Σ) ∩ S(1)) =

3
X

vol (TR (ei ) ∩ S(1))

i=1
3
X

tan

=4

i=1

−1



1
1 + ci (µ)

no intersection between the cones


using Lemma 2.1.

Again, using the fact than tan−1 and c1 (µ) ≥ c2 (µ) ≥ c3 (µ), we have that
3

min

1=µ1 ≤µ2 ≤µ3

tan

−1



1
1 + c1 (µ)



≤

min

1=µ1 ≤µ2 ≤µ3

3
X

tan

−1

i=1



1
1 + ci (µ)



≤

3
X
i=1

tan

−1



1
1 + ci (1, 1, 1)

Since, the left term is minimized by µ = (1, 1, 1) as proved in the non-uniform case and that
3
X
i=1

tan

−1



1
1 + ci (1, 1, 1)



= 3 tan

−1



1
1 + c1 (1, 1, 1)



,

we have that the minimum is achieved at µ1 = µ2 = µ3 = 1. Moreover, since µ1 7→ c1 (1, µ1 , µ2 )
and µ2 7→ c1 (1, µ1 , µ2 ) are strictly increasing, this minimum is unique.
5.2. Proofs for Section 3.1
5.2.1. Link between RIP constants and restricted conditioning. Suppose M has RIP with
constants 0 ≤ δ1 < 1, δ2 > −δ1 on Σ − Σ, i.e.
(1 − δ1 )kxk2H ≤ kM xk22 ≤ (1 + δ2 )kxk2H .
For any λ > 0 we have
λ2 (1 − δ1 )kxk2H ≤ kλM xk22 ≤ λ2 (1 + δ2 )kxk2H
We look for λ, δ′ such that λM has symmetric RIP δ′ :
λ2 (1 − δ1 ) = 1 − δ′

λ2 (1 + δ2 ) = 1 + δ′

(29)



It implies
(1 − δ′ )
(1 + δ2 ) = 1 + δ′
1 − δ1
(1 + δ2 )
1 + δ2
)=
−1
δ′ (1 +
1 − δ1
1 − δ1
δ2 + δ1
2 + δ2 − δ1
=
δ′
1 − δ1
1 − δ1
δ2 + δ1
δ′ =
2 + δ2 − δ1

(30)

We can always rescale M such that M has RIP δ′ .
taking δ1 (M ) = 1 −
inf x∈(Σ−Σ)∩S(1) kM xk2H and δ2 (M ) = supx∈(Σ−Σ)∩S(1) kM xk2H − 1 We have δ′ =
supx∈(Σ−Σ)∩S(1) kM xk2H −inf x∈(Σ−Σ)∩S(1) kM xk2H
supx∈(Σ−Σ)∩S(1) kM xk2H +inf x∈(Σ−Σ)∩S(1) kM xk2H

=

γ(M )−1
γ(M )+1 .

5.2.2. Proofs
Proof of Lemma 3.1. Let z ∈ H. Let M = I − Πz where Πz is the orthogonal projection onto
the one-dimensional subspace span(z).
Let x ∈ Σ − Σ, we always have kM xk2 ≤ kxkH and
kM xk22 = kx − Πz xk2H = kxk2H − 2hx, Πz xi + kΠz xk2H = kxk2H −
Thus

hx, zi2
.
kzk2H

hx, vi2
kM xk22
=
1
−
kxk2H
kxk2H kvk2H

and

γ(M ) =

(31)

supx∈(Σ−Σ)∩S(1) kM xk2H
inf x∈(Σ−Σ)∩S(1) kM xk2H

2

=

1 + supx∈(Σ−Σ)∩S(1) − hx,zi
kzk2

=

1 − inf x∈(Σ−Σ)∩S(1)

H

1+

1−

2
inf x∈(Σ−Σ)∩S(1) − hx,zi
kzk2H

.

(32)

hx,zi2
kzk2H
2
supx∈(Σ−Σ)∩S(1) hx,zi
kzk2H

For all z ∈ H, there is x ∈ Σ − Σ = Σ2k such that hx, zi = 0, hence inf x∈(Σ−Σ)∩S(1)

hx,zi2
kzk2H

=0

(just take x ⊥ zT where T is the support of the greatest 2k coordinates of z) . This gives the
desired result.
The following Lemma shows that we can simplify the calculation of BΣ (R)
Lemma 5.1. Let Σ = Σk the set of k-sparse vectors. Let R = k · kw ∈ C,
BΣ (R) :=

kzT2c k22
kzT2c k22
=
sup
2
2.
z6=0:kzH0 kw ≥kzH c kw kzT2 k2
z∈TR (Σ)\{0} kzT2 k2
sup

(33)

0

where H0 is the support of the k biggest weights: i.e. for all i ∈ H0 , j ∈
/ H0 , we have wi ≥ wj .

Proof. We have
BΣ (R) =

sup

sup

H:|H|≤k z6=0:kzH kw ≥kzH c kw

kzT2c k22
.
kzT2 k22

(34)

Let z such that kzH kw ≥ kzH c kw , there is z ′ a permutation of z (adequately transfer the values
′ k ≥ kz k ≥ kz c k ≥ kz ′ k .
of H to H0 and the values on H c to H0c ) such that kzH
H w
H w
Hc w
0 w
We remark that the expression
This shows that
proof.

kzT c k22
2

0

does not depend on the order of the coordinates of z.

kzT2 k22
kzT c k22
supH:kzH kw ≥kzH c kw kz 2 k2
T
2 2

≤ supH0 :kzH

kzT c k22
2
2
c kw kz
k
≥kz
w
H
0
T2 k2
0

Lemma 5.2. Let Σ = Σk the set of k-sparse vectors.
kwH0 k1 < kwH0c k1 . We have
BΣ (R) =

which concludes the

Let R = k · kw ∈ C such that

kzT2c k22
kzT2c k22
=
sup
2
2
z6=0:kzH0 kw =kzH c kw kzT2 k2
z∈TR (Σ)\{0} kzT2 k2

(35)

sup

0

where H0 is the support of the k biggest weights.
Proof. We use Lemma 5.1. Let z such that kzH0 kw − kzH0c kw = β > 0. This implies that z is
not a constant vector otherwise the hypothesis on weights would be violated. If there is i0 ∈ T2c
such that |zi0 | < mini∈T2 |zj | = α we set z ′ such that |zi′0 | = min(α, |zi0 | + |β|) otherwise there
is i0 ∈ T2 such that |zi0 | > mini∈T2 |zj | = α, we set z ′ such that |zi′ | = max(α, |zi0 | − β) and
|zi′ | = |zi | for i 6= i0 . In both case, we have
kzT2′c k22
kzT2c k22
≤
.
kzT2 k22
kzT2′ k22

(36)

′ k = kz ′ k or kz ′ k − kz ′ k > β ′ , in this last case we strictly reduced
We either have kzH
H0 w
H0c w
H0c w
0 w
the size of the support of zi such that zi 6= mini∈T2 |zj |. Induction on the size of this support leads

′ k = kz ′ k and
to the conclusion that there is always a z ′ such that kzH
Hc w
0 w
0

kzT c k22
2

kzT2 k22

≤

kzT ′c k22
2

kzT ′ k22

.

2

This Lemma allows to bound BΣ (R) when R is not to far from the ℓ1 -norm
Lemma 5.3. Let Σ = Σk the set of k-sparse vectors. Let R = k · kw ∈ C. Let H0 a support of
k biggest weights in w, let L ≥ 1 an integer and H1 a support of k + L smallest weights in w.
Suppose kwH0 k1 < kwH1 k1 , then
BL (R) :=

kzT2c k22
2 ≥
z6=0:kzH0 kw =kzH c kw ,|supp(z)|=2k+L kzT2 k2
sup
0

L
k
kwH1 k21
kwH0 k21

.

(37)

+1

Proof. Let z such that for j ∈ H0 , |zj | = α, for j ∈ H1 , |zj | = β and zj = 0 otherwise. Set

0 6= β =

kwH1 k1
kwH0 k1 α.

Hence, kzH0 kw = kzH1 kw and, using the hypothesis, β ≥ α. This gives
kzT2c k22
L
Lα2
= kw k2
=
2
2
2
kβ + kα
kzT2 k2
k kwH1 k12 + k
H0 1

which is the desired result.

(38)

We can conclude with the proof of the theorem.
Proof of Theorem 3.1. Let CL = {k · kw ∈ C : kwH0 k1 < kwH1 k1 } (we define H0 as the support
of k biggest weights in w, and H1 as the support of the k + L smallest weights). We have
kwH1 k1
L+k
kwH0 k1 ≤ k . Hence, for R ∈ CL , with Lemma 5.3, the value BL (R) is lower bounded (and
reached) by the case k · k1 :
BL (R) ≥

L
k
kwH1 k21
kwH0 k21

+1

L
k

≥ BL (k · k1 ) =

where the value of BL (k · k1 ) was obtained by calculating

L
k

,
2
+1 +1

kzT c k22
2

kzT2 k22

(39)

for the optimal z given by [6] (z

flat on H0 and flat on H1 ). The maximum value of BL (k · k1 ) (with
√ respect to L) is reached for
L/k maximizing f (u) = u2 /((u+1)2 +1) (which is maximized at 2pover R, see
√ Lemma
√5.4). We
verify that it matches the necessary RIP condition √12 from [6] (f ( (2)) = 2 2/(2 + 2) which
√
√ √
gives γΣ (k · k1 ) = (4 + 3 2)/ 2 = √2+1
). Note that the inequality (39) is strict if R 6= k · k1 .
2−1
′
If R ∈ CL the complementary in C of CL , take z such that zi = α for i ∈ H0 ∪ H1 , zi = 0
otherwise. We have kzH0 kw ≥ kzH1 kw and
BL (R) ≥

L
k

L
>
2k

L
k

Hence , we just showed that for any R ∈ C,

= BL (k · k1 )
2
+1 +1

(40)

BΣ (R) = sup BL (R) ≥ sup BL (k · k1 ) = BΣ (k · k1 )
L

(41)

L

with equality only when R = k · k1 . Taking the inf with respect to R ∈ C of both sides of this
inequality yields the result.
√
u
Lemma 5.4. The function f (u) = (u+1)
2 and decreasing for
2 +1 is increasing for 0 ≤ u ≤
√
2 ≤ u ≤ +∞
√
Proof. For u ≥ 0, f ′ (u) = 0 is equivalent to (u + 1)2 + 1 − 2u(u + 1) = 0 which yields u = 2.
Using the fact that f (0) = 0 and limu→∞ f (u) = 0 gives the result.
5.3. Proofs for Section 3.2
We refer the reader to [11][Section 2.2] and [2] for properties of the atomic norm k · kΣ
suf f
Proof of 3.1. The constant δΣ
(R) [11][Eq. (5)] has the following expression:
suf f
δΣ
(R) =

inf

sup

z∈TR (Σ)\{0}x∈Σ

We show that for any z,
sup
x∈Σ kxk
H

q

−Rehx, zi

kxkH

q

−Rehx, zi

(42)

kx + zk2Σ − kxk2H − 2Rehx, zi

kx + zk2Σ − kxk2H − 2Rehx, zi

=s

1
sup
z∈TR (Σ)\{0}

kzT c k2Σ
kzT k22

.
+1

(43)

Taking x = −zT , immediately shows that
sup
x∈Σ kxk
H

q

−Rehx, zi

kx + zk2Σ − kxk2H − 2Rehx, zi

≥s

1
sup
z∈TR (Σ)\{0}

kzT c k2Σ
kzT k22

.
(44)

+1

P
P
Let x such P
that supp(x) = H. Let ui ∈ Σ, λi ≥ 0 such that i λi = 1, i λi ui = x + z and
kx + zk2Σ = λi kui k2 (from [11][Fact 2.1] kv|Σ is the infimum of this expression over the convex
decompositions λi , ui of v). Using the fact that kvkΣ = kvk22 for v ∈ Σ, we have
X
X
kzH c k2Σ + kxH + zH k22 = kzH c k2Σ + kxH + zH k2Σ ≤
λi kui,H c k22 + k
λi ui,H k2
i

≤

=

X
i

X
i

λi kui,H c k22

+

X
i

i

λi kui,H k2

(45)

λi kui k22 = kx + zk2Σ .

We have
kzH c k2Σ + kxH + zH k22 ≤ kx + zk2Σ

kzH c k2Σ + kzH k22 ≤ kx + zk2Σ − kxH + zH k22 + kzH k22

(46)

kzH c k2Σ + kzH k22 ≤ kx + zk2Σ − kxH k22 − 2RehxH , zH i

kzH c k2Σ + kzH k22 ≤ kx + zk2Σ − kxH k22 − 2RehxH , zi
Using Cauchy-Schwartz inequality, we get

kxH k22



RehxH , zi2 kzH c k2Σ + kzH k22 ≤ kxH k22 kzH k22 kx + zk2Σ − kxH k22 − 2RehxH , zi

RehxH , zi2
kzH k22
=

≤
kzH c k2Σ + kzH k22
kx + zk2Σ − kxH k22 − 2RehxH , zi

1

kzH c k2Σ
kzH k22

+1

≤

1

kzT c k2Σ
kzT k22

+1
(47)

which shows that

sup
x∈Σ kxk
H

q

Lemma 5.5. We have

−Rehx, zi

kx + zk2Σ − kxk2H − 2Rehx, zi

≤s

1
sup
z∈TR (Σ)\{0}

λ2 = D1 := sup kzk2Σ s.t. kzk1 = λ.

kzT c k2Σ
kzT k22

.
+1

(48)

(49)

The sup is reached for any z ∗ such that |supp(z ∗ )| = 1.

Proof. Let an admissible z ∗ such that |supp(z ∗ )| = 1. We have kz ∗ k2Σ = kz ∗ k22 = λ2 and
kz ∗ k1 = λ hence D1 ≥ λ2 . Moreover, for any z satisfying kzk1 = λ, kzk2Σ ≤ kzk21 = λ2 .

To replicate the proof used in the necessary case, we show a monotony property of k · kΣ .

Lemma 5.6. let v, v ′ such that vj0 6= 0 and |vj0 | ≥ |vj′ 0 |, then kvkΣ ≤ kv ′ kΣ .
P
P
P
Proof. Let λi , ui such that ui ∈ Σ, λi such that i λi = 1, i λi ui = v and kvk2Σ =
λi kui k2 .
Let H = supp(v) \ j0 We have
X
λi kui,j0 k2 ≥
λi kui,H k2 + |vj0 |2
X
X
≥
λi kui,H k2 + |vj′ 0 |2 =
λi ku′i k2 ≥ kv ′ k2Σ

kvk2Σ =

X

λi kui,H k2 +

X

(50)

√
where we took u′i,H = ui,H and u′i,j0 = vj′ 0 / λi .

Lemma 5.7. Let Σ = Σk the set of k-sparse vectors. Let R = k · kw ∈ C. We have
D ′ (R) :=

sup
z∈TR (Σ)\{0}

kzT c k2Σ
kzT c k2Σ
=
sup
2 .
kzT k22
z6=0:kzH0 kw ≥kzH c kw kzT k2

(51)

0

where H0 is the support of the k biggest weights: for all i ∈ H0 , j ∈
/ H0 wi ≥ wj .
Proof. Using the fact that kzkΣ is invariant by permutation of coordinates z, the proof of
Lemma 5.1 is valid in this case.
Lemma 5.8. Let Σ = Σk the set of k-sparse vectors. Let R = k · kw ∈ C such that for all
kwH0 k1 < kwH0c k1 . We have
DΣ (R) =

sup
z∈TR (Σ)\{0}

kzT c k2Σ
kzT c k2Σ
=
sup
2 .
kzT k22
z6=0:kzH0 kw =kzH c kw kzT k2

(52)

0

where H0 is the support of the k biggest weights.
Proof. Using Lemma 5.6 the proof of Lemma 5.2 holds in this case.
We calculate tools to obtain DΣ (k · k1 ) the case of the ℓ1 -norm.
Lemma 5.9.


kzT c k2Σ
L
DL (k · k1 ) :=
sup
2 = min 1, k
z6=0:kzH0 k1 =kzH c k1 ,|supp(z)|=k+L kzT k2

(53)

0

Proof. It was already proven in [11][Theorem 4.1]that
kzT c k2Σ
2 ≤1
z6=0:kzH0 k1 =kzH c k1 ,|supp(z)|=2k+L kzT k2
sup

(54)

0

If L ≥ k, Take z such that zH0 = (β, .., β) and zH0c ∩supp(z) = (α, .., α) with β = Lk α ≥ α, we
have T = H0 .
From [2][Proposition 2.1], kzT c k2Σ = k1 (kzH0c ∩supp(z)k1 )2 = L2 α2 /k. Moreover kzT k22 = kβ 2 =
L2 α2 /k, thus
kzT c k2Σ
= 1.
(55)
kzT k22

If L < k, we have kzT c k2Σ = kzT c k22 and
kzT c k2Σ
≤ L/k.
kzT k22

(56)

taking z = (1, 1, 1..1, 0, 0, 0) shows that this bound is reached.
WE bound DΣ (R) for norms not too far from the ℓ1 -norm.
Lemma 5.10. Let R = k · kw ∈ C. Let H0 the support of k biggest weights in w, let L ≥ 1 an
integer and H1 a support of L smallest weights in w. Suppose kwH0 k1 < kwH1 k1
Then, for L ≥ k
DL (R) =

1 2
kzT c k2Σ
kL
.
≥
2
kw k2
z6=0:kzH0 kw =kzH c kw ,|supp(z)|=k+L kzT k2
k kwH1 k12
0

sup

(57)

H0 1

For L ≤ k
DL (R) =

kzT c k2Σ
L
2 ≥ k.
kz
k
T 2
z6=0:kzH0 kw =kzH c kw ,|supp(z)|=k+L
sup

(58)

0

Proof. Let z such that for j ∈ H0 , |zj | = α, for j ∈ H1 , |zj | = β and zj = 0 otherwise. Set

0 6= β =
gives

kwH1 k1
kwH0 k1 α.

Hence, kzH0 kw = kzH1 kw and, using the hypothesis, β ≥ α. For L ≥ k, this
kyk2Σ α2
kzT c k2Σ
kyk2Σ
=
=
kw k2
kβ 2
kzT k22
k kwH1 k21

(59)

H0 1

where yi = 1 for i ∈ H1 and yi = 0 otherwise. From [2][Proposition 2.1] kyk2Σ = k1 L2
1 2
kzT c k2Σ
kL
=
.
kw k2
kzT k22
k kwH1 k12

(60)

H0 1

For L ≤ K, take z = (1, 1, 1..1, 0, 0, 0), using the hypothesis on H1 and H0 , we have
kzH0 kw ≥ kzH1 kw and
kzT c k2Σ
L
(61)
= .
2
k
kzT k2
Proof of Theorem 3.2. For L > k, let CL = {k · kw ∈ C : kwH0 k1 < kwH1 k1 } (we define H0 as
the support of k biggest weights in w, and H1 as the support of the L smallest weights). We
kwH1 k1
L
have kwH
k ≤ k . Hence, for R ∈ CL , with Lemma 5.10, the value DL (R) is lower bounded (and
0 1
reached) by the case k · k1 (Lemma 5.9):


L
DL (R) ≥ min 1,
= DL (k · k1 )
(62)
k
We verify that it matches the sufficient RIP condition of

√1
2

for ℓ1 recovery from [4, 11].

If R ∈ CL′ the complementary in C of CL , take z such that zi = α for i ∈ H0 ∪ H1 , zi = 0
otherwise. We have kzH0 kw ≥ kzH1 k and


L
L
DL (R) ≥ ≥ min 1,
= DL (k · k1 )
(63)
k
k
Hence , we just showed that for any R ∈ C,
DΣ (R) = sup DL (R) ≥ 1 = sup DL (k · k1 ) = DΣ (k · k1 )
L

(64)

L

with equality only when R = k · k1 . Taking the inf with respect to R ∈ C of both sides of this
inequality yields the result.

