# JOINT SCREENING TESTS FOR LASSO

###### Abstract

This paper focusses on “safe” screening techniques for the LASSO problem.
Motivated by the need for low-complexity algorithms, we propose a new
approach, dubbed “joint screening test”, allowing to screen a set of atoms by
carrying out one single test. The approach is particularized to two different
sets of atoms, respectively expressed as sphere and dome regions. After
presenting the mathematical derivations of the tests, we elaborate on their
relative effectiveness and discuss the practical use of such procedures.

Index Terms—  $\ell_{1}$-norm minimization, LASSO, screening techniques.

##  1 Introduction

In the last decade, sparse representations have proven to be powerful tools
for solving many problems in signal processing, machine learning, etc. Many
central methodologies to find a good sparse representation of an observation
vector ${{\mathbf{y}}}\in{{\mathbb{R}}}^{m}$ in some dictionary
${{\mathbf{A}}}=\left[{{{\mathbf{a}}}_{1}\ldots{{\mathbf{a}}}_{n}}\right]\in{\mathbb{R}}^{{m}\times{n}}$
revolve around the resolution of the so-called (nonnegative) LASSO
problem:111The standard LASSO can be written as a particular case of (1), see
[1].

$\displaystyle{\mathbf{x}}^{\star}_{\lambda}\in\operatornamewithlimits{arg\,min}_{{\mathbf{x}}\geq{\mathbf{0}}}\,P_{\lambda}({{\mathbf{y}}},{\mathbf{x}}),$
(1)

where
$P_{\lambda}({{\mathbf{y}}},{{\mathbf{x}}})=\frac{1}{2}\left\|{{{\mathbf{y}}}-{{\mathbf{A}}}{\mathbf{x}}}\right\|_{2}^{2}+\lambda\left\|{{\mathbf{x}}}\right\|_{1}$
and ${\mathbf{x}}\in{\mathbb{R}}^{n}$. Without loss of generality, we will
assume hereafter that $\left\|{{{\mathbf{a}}}_{i}}\right\|_{2}=1$ for
$i=1\ldots{n}$.

Solving (1) may require a heavy computational load when the dimension of
${{\mathbf{x}}}$ becomes large. Therefore, the conception of computationally-
efficient techniques to solve (1) has become an active field of research [2,
3, 4]. One important contribution in this field is the so-called “safe” 222The
term “safe” refers to the fact that the elements identified by the screening
method always correspond to zeros in ${\mathbf{x}}^{\star}_{\lambda}$.
screening technique proposed by El Ghaoui et al. in [5] and refined in several
subsequent works [6, 7, 8, 9, 10, 11, 12, 13]. These methodologies aim at
decreasing the dimensionality of the problem to handle by identifying some of
the zeros of the target solution ${\mathbf{x}}^{\star}_{\lambda}$ via simple
tests. Screening procedures have been shown to allow for a dramatic reduction
of the complexity needed to solve (1). Nevertheless, their implementation may
still be computationally too-demanding in some applications. More
specifically, the complexity of all the screening procedures proposed so far
evolves linearly with the number of atoms in the dictionary. Hence, in
applications involving very large dictionaries,333As an extreme example, one
may think of the “continuous” dictionaries considered in [14, 15], containing
an infinite number of atoms. the implementation of these screening tests may
lead to unacceptable computational burdens. In this paper, we propose a new
screening methodology, dubbed “joint screening”, allowing to circumvent this
issue.

##  2 Some Convex Considerations

We first remind some of the properties of the solutions of (1). Problem (1) is
convex and always admits (at least) one solution. The dual problem associated
to (1) can be written as (see for example [16])

$\displaystyle{\boldsymbol{\theta}}^{\star}_{\lambda}=\operatornamewithlimits{arg\,min}_{{\boldsymbol{\theta}}\in\mathcal{D}}D_{\lambda}({{\mathbf{y}}},{\boldsymbol{\theta}}),$
(2)

where

$\displaystyle D_{\lambda}({{\mathbf{y}}},{\boldsymbol{\theta}})$
$\displaystyle=\frac{1}{2}\left\|{{{\mathbf{y}}}}\right\|_{2}^{2}-\frac{1}{2}\left\|{{{\mathbf{y}}}-\lambda{\boldsymbol{\theta}}}\right\|_{2}^{2},$
(3) $\displaystyle\mathcal{D}$
$\displaystyle=\\{{\boldsymbol{\theta}}\in{{\mathbb{R}}}^{m}:\left\langle{{{\mathbf{a}}}_{i},{\boldsymbol{\theta}}}\right\rangle\leq
1,\,i=1\ldots n\\},$ (4)

and $\left\langle{\cdot,\cdot}\right\rangle$ denotes the inner product in
${\mathbb{R}}^{m}$. Since $D_{\lambda}({{\mathbf{y}}},{\boldsymbol{\theta}})$
is a strictly concave and coercive function and $\mathcal{D}$ is a closed set,
problem (2) admits a unique solution
${\boldsymbol{\theta}}^{\star}_{\lambda}$, see [17, Proposition A.8].

The primal and dual solutions
$({\mathbf{x}}^{\star}_{\lambda},{\boldsymbol{\theta}}^{\star}_{\lambda})$ are
related through the Karush-Kuhn-Tucker conditions [17, Proposition 5.1.5]:

$\displaystyle{\mathbf{x}}^{\star}_{\lambda}\geq{\mathbf{0}},\
\left\langle{{\mathbf{a}}_{i},{\boldsymbol{\theta}}^{\star}_{\lambda}}\right\rangle\leq
1\mbox{ for all $i$},$ (5)
$\displaystyle\left({\left\langle{{\mathbf{a}}_{i},{\boldsymbol{\theta}}^{\star}_{\lambda}}\right\rangle-1}\right){\mathbf{x}}^{\star}_{\lambda}(i)=0\
\mbox{ for all $i$},$ (6)
$\displaystyle{\mathbf{y}}=\lambda{\boldsymbol{\theta}}^{\star}_{\lambda}+{\mathbf{A}}{\mathbf{x}}^{\star}_{\lambda},$
(7)

where ${\mathbf{x}}^{\star}_{\lambda}(i)$ denotes the $i$th component of
${\mathbf{x}}^{\star}_{\lambda}$.

##  3 Standard Screening Methodologies

The “safe” screening procedures proposed in [5, 6, 7, 8, 9, 10, 11, 12, 13]
leverage on the following observation: if
${{\mathcal{R}}}\subset{\mathbb{R}}^{m}$ is a region such that
${\boldsymbol{\theta}}^{\star}_{\lambda}\in{{\mathcal{R}}}$,444Such a region
is commonly referred to as “safe region” in the screening literature. then the
following inequality trivially holds

$\displaystyle\left\langle{{\mathbf{a}}_{i},{\boldsymbol{\theta}}^{\star}_{\lambda}}\right\rangle\leq\max_{{\boldsymbol{\theta}}\in{{\mathcal{R}}}}\left\langle{{{\mathbf{a}}}_{i},{\boldsymbol{\theta}}}\right\rangle,$

and from (6), we thus have

$\displaystyle\max_{{\boldsymbol{\theta}}\in{{\mathcal{R}}}}\left\langle{{{\mathbf{a}}}_{i},{\boldsymbol{\theta}}}\right\rangle<1\Rightarrow{\mathbf{x}}_{\lambda}^{\star}(i)=0.$
(8)

In other words, if the inequality in the left-hand side of (8) is satisfied,
one is ensured that the $i$th component of the solution vector
${\mathbf{x}}_{\lambda}^{\star}$ is equal to zero.

Since the seminal work by El Ghaoui et al., different screening tests, based
on different choices of the region ${{\mathcal{R}}}$, have been proposed in
the literature. The most popular ones are probably the “sphere” regions, that
is

$\displaystyle{{\mathcal{R}}}$
$\displaystyle=\left\\{{{\boldsymbol{\theta}}:\left\|{{\boldsymbol{\theta}}-{{\mathbf{c}}}}\right\|_{2}\leq
1-{\tau}}\right\\},$ (9)

for some parameters ${{\mathbf{c}}}\in{{\mathbb{R}}}^{m}$ and ${\tau}\leq 1$.
Interestingly, for this particular choice, the general screening test (8)
takes the following simple form:

$\displaystyle\left\langle{{{\mathbf{a}}}_{i},{{\mathbf{c}}}}\right\rangle<{\tau}\Rightarrow{\mathbf{x}}_{\lambda}^{\star}(i)=0.$
(10)

We find in the literature different definitions for the center
${{\mathbf{c}}}$ and the radius $1-{\tau}$ (see [5, 6, 7, 8, 9, 10, 11])
leading to screening tests of different effectiveness.

It is easy to see that the implementation of the standard screening test (8)
necessitates the evaluation of
$\max_{{\boldsymbol{\theta}}\in{{\mathcal{R}}}}\left\langle{{{\mathbf{a}}}_{i},{\boldsymbol{\theta}}}\right\rangle$
for each atom of the dictionary. Hence, the computational load required to
implement standard screening tests evolves linearly with the number of atoms
in the dictionary. For example, in the case where ${{\mathcal{R}}}$ is a
“sphere” region, (10) involves the computation of the inner product between
the center of the sphere ${{\mathbf{c}}}$ and each atom of the dictionary,
leading to a complexity scaling as $\mathcal{O}({m}{n})$. In the next section,
we propose a new procedure to reduce this computational load.

##  4 Joint Screening Procedures

In this section, we introduce a new screening procedure having a complexity
not depending on the number of atoms in the dictionary. We dub our methodology
“joint screening test” because it allows to screen a set of atoms by carrying
out one single test. In a first subsection, we derive tests allowing to screen
any atom belonging to some specific region
${\mathcal{G}}\subset{\mathbb{R}}^{m}$. In a second subsection, we elaborate
on the relative effectiveness of the proposed test for different choices of
the region ${\mathcal{G}}$. Finally, in the last subsection, we leverage on
these previous results to propose a novel screening procedure having a low
complexity with regard to standard screening tests.

###  4.1 Screening the atoms belonging to a region ${\mathcal{G}}$

---
Fig. 1: Illustration of the sphere region
${\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})$ (dotted area) and the dome
region ${\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})$ (cross-hatched area). The
region inside the dashed curves corresponds to set of atoms with a
$\left\|{\cdot}\right\|_{2}$-norm smaller than 1.

Let ${{\mathcal{A}}}=\left\\{{{{\mathbf{a}}}_{i}}\right\\}_{i=1}^{{n}}$ denote
the set of atoms of the dictionary and let
${{\mathcal{R}}}\subset{{\mathbb{R}}}^{m}$ be a safe region (that is
${\boldsymbol{\theta}}^{\star}_{\lambda}\in{{\mathcal{R}}}$). The “joint”
screening procedure proposed in this paper is a direct consequence of the
following observation:555The validity of (11) straightforwardly follows from
(8).

$\displaystyle\max_{{{\mathbf{a}}}\in{\mathcal{G}}}\max_{{\boldsymbol{\theta}}\in{{\mathcal{R}}}}\left\langle{{{\mathbf{a}}},{\boldsymbol{\theta}}}\right\rangle<1\Rightarrow{\mathbf{x}}_{\lambda}^{\star}(i)=0\quad\forall
i:{{\mathbf{a}}}_{i}\in{{\mathcal{A}}}\cap{\mathcal{G}}.$ (11)

In order words, if the inequality in the left-hand side of (11) is satisfied,
all the atoms ${{\mathbf{a}}}_{i}\in{{\mathcal{A}}}\cap{\mathcal{G}}$ can be
safely and jointly screened from problem (1).

In what follows, we will see that the verification of the inequality in the
left-hand side of (11) can be done very efficiently for some specific choices
of regions ${{\mathcal{R}}}$ and ${\mathcal{G}}$. First, we will assume that
${{\mathcal{R}}}$ is a sphere region (9). The joint screening test (11) then
takes the simple form:

$\displaystyle\max_{{{\mathbf{a}}}\in{\mathcal{G}}}\left\langle{{{\mathbf{a}}},{{\mathbf{c}}}}\right\rangle<{\tau}\Rightarrow{\mathbf{x}}_{\lambda}^{\star}(i)=0\quad\forall
i:{{\mathbf{a}}}_{i}\in{{\mathcal{A}}}\cap{\mathcal{G}}.$ (12)

Moreover, we will consider the two following options for ${\mathcal{G}}$:

  * •

“Sphere” :
${\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})=\left\\{{{{\mathbf{a}}}:\left\|{{{\mathbf{a}}}-{{\mathbf{t}}}}\right\|_{2}\leq{\epsilon}}\right\\}$,

  * •

“Dome”  :
${\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})=\left\\{{{{\mathbf{a}}}:\left\langle{{{\mathbf{a}}},{{\mathbf{t}}}}\right\rangle\geq{\delta},\left\|{{{\mathbf{a}}}}\right\|_{2}\leq
1}\right\\}$,

where ${{\mathbf{t}}}\in{{\mathbb{R}}}^{m}$ and ${\epsilon}$, ${\delta}$ are
some parameters. ${\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})$ and
${\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})$ have some easy geometric
interpretations: ${\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})$ corresponds to
the set of vectors located in a ball of radius ${\epsilon}$ centered on
${{\mathbf{t}}}$; ${\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})$ is a dome
including all the vectors of norm smaller than one and having an inner product
with ${{\mathbf{t}}}$ greater than or equal to ${\delta}$. A graphical
representation is given in Fig. 1.

For these two choices of regions, the joint screening test defined in (12)
admits the following simple analytical solutions:

  * •

Joint sphere test:
$\displaystyle{\max_{{{\mathbf{a}}}\in{\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})}\left\langle{{{\mathbf{a}}},{{\mathbf{c}}}}\right\rangle<\tau}$
if and only if

$\displaystyle\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle<{\tau}-{\epsilon}\,\left\|{{{\mathbf{c}}}}\right\|_{2}.$
(13)

  * •

Joint dome test:
$\displaystyle{\max_{{{\mathbf{a}}}\in{\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})}\left\langle{{{\mathbf{a}}},{{\mathbf{c}}}}\right\rangle<\tau}$
if and only if 666We assume that $\left\|{{{\mathbf{t}}}}\right\|_{2}=1$.

$\displaystyle\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle<{\tau},$
(14)

and

$\displaystyle{\delta}>\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle{\tau}+\sqrt{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}-\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle^{2}}\sqrt{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}-{\tau}^{2}}}{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}}.$
(15)

A proof of this result can be found in Appendix A.

###  4.2 Relative effectiveness of the screening tests

It is easy to see from (11) that the choice of region ${\mathcal{G}}$ is a
compromise between the number of atoms that can be jointly screened and the
ease of passing the test. Indeed, although large regions allow to screen more
atoms, they are also less likely to pass the joint screening test since, for
any ${\mathcal{G}}_{1}\subseteq{\mathcal{G}}_{2}$, we have

$\displaystyle\max_{{{\mathbf{a}}}\in{\mathcal{G}}_{1}}\max_{{\boldsymbol{\theta}}\in{{\mathcal{R}}}}\left\langle{{{\mathbf{a}}},{\boldsymbol{\theta}}}\right\rangle\leq\max_{{{\mathbf{a}}}\in{\mathcal{G}}_{2}}\max_{{\boldsymbol{\theta}}\in{{\mathcal{R}}}}\left\langle{{{\mathbf{a}}},{\boldsymbol{\theta}}}\right\rangle.$
(16)

In particular, letting
${\mathcal{G}}_{1}=\left\\{{{{\mathbf{a}}}_{i}}\right\\}$ and
${\mathcal{G}}_{2}={\mathcal{G}}$ in the above inequality, we see that passing
the joint screening test (11) requires in particular that the standard
screening test (8) is verified for any atom
${{\mathbf{a}}}_{i}\in{{\mathcal{A}}}\cap{\mathcal{G}}$. Hence, quite
logically, joint screening test (11) can only lead to inferior screening
performance as compared to standard screening test (8).

Another question of interest is the relative effectiveness of the joint sphere
and dome tests proposed in (13) and (14)-(15), respectively. The next lemma
provides some insights into this question.

######  Lemma 1.

The smallest777“Smallest” should be understood as the one with the smallest
volume. dome containing a set of unit-norm vectors ${\cal{S}}$ is always
contained in the smallest sphere containing ${\cal{S}}$.

A proof of this statement can be found in Appendix B. In view of (16), a
direct consequence of Lemma 1 is as follows: if one wishes to jointly screen a
set of unit-norm atoms, there always exists a joint dome test leading to
screening performance at least as good as the “best”888“Best” should be
understood as the test involving the sphere of smallest volume. joint sphere
test.

###  4.3 Low-complexity screening procedures

In this section, we discuss the following screening procedure:

  * 1)

Select a set of ${L}$ (dome or sphere) regions
$\left\\{{{\mathcal{G}}_{{l}}}\right\\}_{{l}=1}^{L}$,

  * 2)

Apply screening test (13) or (14)-(15) for ${l}=1\ldots{L}$.

We note that since (13) and (14)-(15) only involve the evaluation of one inner
product (namely $\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle$),
the screening procedure described above only requires to carry out a total
number of ${L}$ inner products.

On the other hand, the effectiveness of this screening procedure obviously
depends on the choice of the regions
$\left\\{{{\mathcal{G}}_{{l}}}\right\\}_{{l}=1}^{L}$. In order to find a
trade-off between the two conflicting objectives emphasized in the first point
of the previous section, we consider hereafter some specific choices of the
regions $\left\\{{{\mathcal{G}}_{{l}}}\right\\}_{{l}=1}^{L}$.

Let us focus on one particular region ${\mathcal{G}}_{l}$ for a given ${l}$.
We first assume that ${\mathcal{G}}_{{l}}$ is a sphere, that is
${\mathcal{G}}_{{l}}={\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})$. Given the
value of ${{\mathbf{t}}}$, we want to tune the value of ${\epsilon}$ so that
${\mathcal{G}}$ is the largest sphere passing (if possible) the joint
screening test (13). We note then that the joint sphere test (13) is satisfied
as soon as the radius ${\epsilon}$ verifies

$\displaystyle{\epsilon}<{\epsilon}_{{{\mathbf{t}}},{{\mathbf{c}}}}\triangleq\frac{{\tau}-\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle}{\left\|{{{\mathbf{c}}}}\right\|_{2}}.$
(17)

Now, letting the radius ${\epsilon}$ of ${\mathcal{G}}_{l}$ tend to its
largest value ${\epsilon}_{{{\mathbf{t}}},{{\mathbf{c}}}}$, we have that any
atom ${{\mathbf{a}}}_{i}\in{\mathcal{A}}$ having a distance to
${{\mathbf{t}}}$ strictly smaller than
${\epsilon}_{{{\mathbf{t}}},{{\mathbf{c}}}}$ will be screened by test (13),
that is

$\displaystyle\left\|{{{\mathbf{a}}}_{i}-{{\mathbf{t}}}}\right\|_{2}<{\epsilon}_{{{\mathbf{t}}},{{\mathbf{c}}}}\Rightarrow{\mathbf{x}}_{\lambda}^{\star}(i)=0.$
(18)

We note that (18) defines a screening test on all the elements of the
dictionary (it may be applied to any atom
${{\mathbf{a}}}_{i}\in{{\mathcal{A}}}$) although it only requires the
evaluation of one inner product
$\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle$ (to evaluate
${\epsilon}_{{{\mathbf{t}}},{{\mathbf{c}}}}$). Let us moreover mention that
the quantities
$\left\\{{\left\|{{{\mathbf{a}}}_{i}-{{\mathbf{t}}}}\right\|_{2}}\right\\}_{i=1}^{n}$
can be precomputed and sorted once for all in advance, so that the
identification of the atoms verifying (18) can be done very efficiently (one
may for example achieve a complexity scaling as ${\mathcal{O}}(\log_{2}{n})$).
As a consequence, the “on-line” complexity associated to the implementation of
(18) is of the order of ${\mathcal{O}}({m}+\log_{2}{n})$.

|
---|---
Fig. 2: Proportion of zeros identified by the screening procedures as a
function of $-\log_{10}(\lambda_{t}/\lambda_{max})$ (horizontal axis) and the
($\log_{10}$ of the) number of iterations (vertical axis): GAP sphere test
(left) and proposed procedure with a dome region (right)

We can apply the same kind of reasoning when ${\mathcal{G}}_{l}$ is a dome
region, that is
${\mathcal{G}}_{l}={\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})$. If we assume
that ${{\mathbf{t}}}\in{\mathbb{R}}^{{m}}$ is given, a tight lower bound on
the value of ${\delta}$ verifying the joint dome test is trivially given by
the right-hand side of (15), that is

$\displaystyle{\delta}>{\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}},$ (19)

where

$\displaystyle{\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}}\triangleq\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle{\tau}+\sqrt{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}-\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle^{2}}\sqrt{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}-{\tau}^{2}}}{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}}.$
(20)

Hence, provided that
$\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle<{\tau}$, letting
parameter ${\delta}$ tend to its smallest value
${\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}}$ will lead to the screening of any
atom ${{\mathbf{a}}}_{i}\in{{\mathcal{A}}}$ having an inner product with
${{\mathbf{t}}}$ strictly greater than
${\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}}$, that is:

$\displaystyle\left\\{\begin{array}[]{l}\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle<{\tau}\\\
\left\langle{{{\mathbf{t}}},{{\mathbf{a}}}_{i}}\right\rangle>{\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}}\end{array}\right.\Rightarrow{\mathbf{x}}_{\lambda}^{\star}(i)=0.$
(23)

Again, the quantities
$\left\\{{\left\langle{{{\mathbf{t}}},{{\mathbf{a}}}_{i}}\right\rangle}\right\\}_{i=1}^{n}$
can be precomputed and sorted once for all in advance, so that a complexity
scaling as ${\mathcal{O}}({m}+\log_{2}{n})$ can also be achieved here.

Going back to the screening procedure advocated at the beginning of this
section, we see that adapting the parameter ${\epsilon}$ (resp. ${\delta}$)
for each region ${\mathcal{G}}_{{l}}$ as discussed above is equivalent to
applying test (18) (resp. (23)) for each of the ${L}$ different test vectors
${{\mathbf{t}}}$ specifying the regions
$\left\\{{{\mathcal{G}}_{{l}}}\right\\}_{{l}=1}^{L}$. The overall complexity
of this procedure thus scales as ${\mathcal{O}}({L}{m}+{L}\log_{2}{n})$. This
is to compare to the complexity in ${\mathcal{O}}({m}{n})$ of the standard
screening tests. The joint screening procedures proposed in this paper will
then be of particular interest when dealing with high-dimensional
dictionaries.

##  5 Numerical experiments

In this section we perform some numerical experiments to evaluate the behavior
of the proposed method. We confront our screening procedure to the standard
one (8) within the following setup. We consider a dictionary
${{\mathbf{A}}}\in{\mathbb{R}}^{100\times 2000}$ made up of ${L}=100$ clusters
of $20$ atoms. For each cluster, a “seed” atom is created as the
${m}$-dimensional realization of a zero-mean circular Gaussian with covariance
matrix ${m}^{-1}{\mathbf{I}}_{m}$, where ${\mathbf{I}}_{m}$ is the
${m}\times{m}$ identity matrix. The other atoms of the cluster are generated
so that their inner products with the seed atom are not smaller than $0.9$. We
assume that ${{\mathbf{y}}}$ is a linear combination of $10$ columns (chosen
randomly) of the dictionary. The nonzero coefficients are generated as
independent realizations of a zero-mean Gaussian with variance equal to $1$.

Considering this data set, we target the solution of problem (1) for a
decreasing sequence of $\lambda$ going from
$\lambda_{\mathrm{max}}\triangleq\left\|{{{{\mathbf{A}}}}^{\operatorname{T}}{{\mathbf{y}}}}\right\|_{\infty}$
to $10^{-1.5}\lambda_{\mathrm{max}}$. The solution is searched via the FISTA
algorithm [4]. At each iteration of FISTA, the screening procedure is
implemented as follows. A “safe” sphere ${{\mathcal{R}}}$ is computed
according to the GAP procedure proposed in [10]. ${{\mathcal{R}}}$ is then
used to implement both a standard screening test (8) and the reduced-
complexity screening test presented in Section 4.3. Due to space limitation,
we only consider the results obtained with the test based on the dome
region,999The results corresponding to the test based on the sphere region
(18) are however sensibly similar. see (23). The ${L}$ test vectors appearing
in (23) are set to be equal to the “seed” vectors used to generate each
cluster of the dictionary.

We evaluate the performance of the methods as the good detection rate of zeros
in the solution vector ${\mathbf{x}}^{\star}_{\lambda}$. Fig. 2 presents this
figure of merit as a function of $\lambda$ (horizontal axis) and the iteration
number (vertical axis). As expected (see Section 4.2), the standard screening
test (left figure) presents better performance than the proposed methodology
(right figure). However, this performance must be weighed against the
complexity required to perform the tests: the standard procedure requires 2000
scalar products for each test, whereas the proposed method involves only 100
scalar products. We thus see that the proposed procedure allows for a good
compromise between computational complexity and the ability to identify zeros
of ${\mathbf{x}}^{\star}_{\lambda}$.

##  6 Conclusions

In this paper, we proposed a new screening methodology for the (nonnegative)
LASSO problem. Our procedure aims to jointly screen a set of similar atoms by
carrying out one single test. We considered two instances of such test
(focussing on sets of atoms belonging to either a sphere or a dome region of
${\mathbb{R}}^{m}$) and showed that the latter take a very simple form. In
particular, both tests only require the evaluation of one inner product in
${\mathbb{R}}^{{m}}$. Leveraging on this result, we showed that screening
procedures for the entire dictionary can be devised by considering an
arbitrary number, say ${L}$, of regions. The resulting screening procedure has
a complexity scaling as ${\mathcal{O}}({L}{m}+{L}\log_{2}{n})$, where ${n}$ is
the number of atoms in the dictionary. This has to be compared to the
complexity of standard screening procedures scaling as
${\mathcal{O}}({m}{n})$.

Our future avenues of research include designing new joint tests (based on
more refined regions ${\mathcal{G}}$) and devising low-complexity
methodologies to identify safe regions ${{\mathcal{R}}}$.

##  Appendix A Derivation of the joint screening tests

In this appendix, we provide a the detailed derivations leading to the joint
screening tests stated in (13) and (14)-(15). Some steps of our reasoning are
based on the technical lemmas stated in Appendix C.

###  A.1 Sphere joint test (13)

Let us first notice that the sphere region
${\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})$ can be written as

$\displaystyle{\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})=\left\\{{{{\mathbf{a}}}={{\mathbf{t}}}+{\boldsymbol{z}}:\left\|{{\boldsymbol{z}}}\right\|_{2}\leq{\epsilon}}\right\\}.$
(24)

Therefore, we have

$\displaystyle\max_{{{\mathbf{a}}}\in{\mathcal{G}}^{s}({{\mathbf{t}}},{\epsilon})}\left\langle{{{\mathbf{a}}},{{\mathbf{c}}}}\right\rangle$
$\displaystyle=\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle+\max_{\left\|{{\boldsymbol{z}}}\right\|_{2}\leq{\epsilon}}\left\langle{{\boldsymbol{z}},{{\mathbf{c}}}}\right\rangle$
$\displaystyle=\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle+{\epsilon}\,\left\|{{{\mathbf{c}}}}\right\|_{2},$
(25)

where the last equality is a consequence of the tightness of the Cauchy-
Schwarz inequality. The joint screening test (13) then straightforwardly
follows from (25).

###  A.2 Dome joint test (14)-(15)

We assume $\left\|{{{\mathbf{t}}}}\right\|_{2}=1$. We first note that the dome
region ${\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})$ can be written as

$\displaystyle{\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})=\left\\{{{\alpha}{{\mathbf{t}}}+{\boldsymbol{z}}:{\boldsymbol{z}}\in{\mathcal{Z}}_{\alpha},{\delta}\leq{\alpha}\leq
1}\right\\},$ (26)

where

$\displaystyle{\mathcal{Z}}_{\alpha}=\left\\{{{\boldsymbol{z}}:{\boldsymbol{z}}\in(\mathrm{span}[{{\mathbf{t}}}])^{\perp},\left\|{{\boldsymbol{z}}}\right\|_{2}\leq\sqrt{1-{\alpha}^{2}}}\right\\}.$
(27)

Therefore, we have

$\displaystyle\max_{{{\mathbf{a}}}\in{\mathcal{G}}^{d}({{\mathbf{t}}},{\delta})}\left({\left\langle{{{\mathbf{a}}},{{\mathbf{c}}}}\right\rangle}\right)$
$\displaystyle=\max_{{\delta}\leq{\alpha}\leq 1}\left({{\alpha}\
\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle+\max_{{\boldsymbol{z}}\in{\mathcal{Z}}_{\alpha}}\left({\left\langle{{\boldsymbol{z}},{{\mathbf{c}}}}\right\rangle}\right)}\right)$
$\displaystyle=\max_{{\delta}\leq{\alpha}\leq 1}\left({{\alpha}\
\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle+\max_{{\boldsymbol{z}}\in{\mathcal{Z}}_{\alpha}}\left({\left\langle{{\mathbf{z}},P_{{{\mathbf{t}}}}^{\perp}({{\mathbf{c}}})}\right\rangle}\right)}\right)$
$\displaystyle=\underbrace{\max_{{\delta}\leq{\alpha}\leq 1}\left({{\alpha}\
\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle+\sqrt{1-{\alpha}^{2}}\,\left\|{P_{{{\mathbf{t}}}}^{\perp}({{\mathbf{c}}})}\right\|_{2}}\right)}_{\triangleq
g({\delta})},$

where $P_{{{\mathbf{t}}}}^{\perp}(\cdot)$ denotes the projector onto
$(\mathrm{span}[{{\mathbf{t}}}])^{\perp}$. The last equality is a consequence
of the tightness of the Cauchy-Schwarz inequality.

The joint dome test can thus simply be rewritten as

$\displaystyle g({\delta})<{\tau}.$ (28)

Using Lemma 2 with
$A=\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle}{\left\|{{{\mathbf{c}}}}\right\|_{2}}$,101010We
use the fact that
$\left\|{P_{{{\mathbf{t}}}}^{\perp}({{\mathbf{c}}})}\right\|_{2}=\sqrt{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}-\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle^{2}}$.
we obtain that

$\displaystyle g({\delta})$
$\displaystyle=\left\\{\begin{array}[]{ll}\left\|{{{\mathbf{c}}}}\right\|_{2}&\mbox{if
$A<\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle}{\left\|{{{\mathbf{c}}}}\right\|_{2}}$}\\\
\delta\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle+\sqrt{1-{\delta}^{2}}\sqrt{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}-\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle^{2}}&\mbox{otherwise}\end{array}\right..$
(31)

The joint group test (14)-(15) can then be shown as follows. First, satisfying
(28) necessarily requires that

$\displaystyle\tau>\min_{\tilde{\delta}\in[-1,1]}g(\tilde{\delta})=g(1)=\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle.$
(32)

This corresponds to the condition enforced by (14).

Moreover, we have from Lemma 3 that

$\displaystyle\tau\leq\left\|{{{\mathbf{c}}}}\right\|_{2}$

provided that $\tau$ is associated to the radius of a safe sphere. Therefore,
if (14) holds, owing to the continuity of $g$ and the fact that it is strictly
decreasing over
$[\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle}{\left\|{{{\mathbf{c}}}}\right\|_{2}},1]$
(see Lemma 2), there exists
${\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}}\in[\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle}{\left\|{{{\mathbf{c}}}}\right\|_{2}},1]$
such that $g({\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}})=\tau.$ Using the
expression of $g$ over
$[\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle}{\left\|{{{\mathbf{c}}}}\right\|_{2}},1]$
in (31), we find

$\displaystyle{\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}}$
$\displaystyle=\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle{\tau}+\sqrt{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}-\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle^{2}}\sqrt{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}-{\tau}^{2}}}{\left\|{{{\mathbf{c}}}}\right\|_{2}^{2}}.$
(33)

Invoking the strict decrease of $g$ over
$[\frac{\left\langle{{{\mathbf{t}}},{{\mathbf{c}}}}\right\rangle}{\left\|{{{\mathbf{c}}}}\right\|_{2}},1]$
(see Lemma 2), we have that
$\tau=g({\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}})>g({\delta})$ if and only if

$\displaystyle{\delta}>{\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}}.$

Combining this condition with the expression of
${\delta}_{{{\mathbf{t}}},{{\mathbf{c}}}}$ in (33), we obtain (15).

##  Appendix B Proof of Lemma 1

On the one hand, the dome of smallest volume including all the elements of
${\cal{S}}$ is given by
${\mathcal{G}}^{d}({{\mathbf{t}}}^{\star},{\delta}^{\star})$ with

$\displaystyle{{\mathbf{t}}}^{\star}$
$\displaystyle=\operatornamewithlimits{arg\,max}_{{{\mathbf{t}}}:\left\|{{{\mathbf{t}}}}\right\|_{2}=1}\min_{{{\mathbf{a}}}\in{\cal{S}}}\left\langle{{{\mathbf{t}}},{{\mathbf{a}}}}\right\rangle,$
(34) $\displaystyle{\delta}^{\star}$
$\displaystyle=\min_{{{\mathbf{a}}}\in{\cal{S}}}\left\langle{{{\mathbf{t}}}^{\star},{{\mathbf{a}}}}\right\rangle.$
(35)

On the other hand, the minimum-volume sphere covering all the elements of
${\cal{S}}$ is given by
${\mathcal{G}}^{s}({\tilde{{{\mathbf{t}}}}}^{\star},{\epsilon}^{\star})$ with

$\displaystyle{\tilde{{{\mathbf{t}}}}}^{\star}$
$\displaystyle=\operatornamewithlimits{arg\,min}_{{\tilde{{{\mathbf{t}}}}}}\max_{{{\mathbf{a}}}\in{\cal{S}}}\left\|{{{\mathbf{a}}}-{\tilde{{{\mathbf{t}}}}}}\right\|_{2},$
(36) $\displaystyle{\epsilon}^{\star}$
$\displaystyle=\max_{{{\mathbf{a}}}\in{\cal{S}}}\left\|{{{\mathbf{a}}}-{\tilde{{{\mathbf{t}}}}}^{\star}}\right\|_{2}.$
(37)

We first show that the optimal parameters
$({{\mathbf{t}}}^{\star},{\delta}^{\star})$ and
$({\tilde{{{\mathbf{t}}}}}^{\star},{\epsilon}^{\star})$ are related as follows

$\displaystyle{\tilde{{{\mathbf{t}}}}}^{\star}$
$\displaystyle=\bar{{\delta}}\,{{\mathbf{t}}}^{\star},$ (38)
$\displaystyle{\epsilon}^{\star}$ $\displaystyle=\sqrt{1-\bar{{\delta}}^{2}},$
(39)

where

$\displaystyle\bar{{\delta}}=\max(0,{\delta}^{\star}).$ (40)

Indeed, setting ${\tilde{{{\mathbf{t}}}}}=\beta{{\mathbf{u}}}$ with $\beta\geq
0$ and $\left\|{{{\mathbf{u}}}}\right\|_{2}=1$, (36) can also be rewritten as

$\displaystyle(\beta^{\star},{{\mathbf{u}}}^{\star})$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\beta\geq
0,\left\|{{{\mathbf{u}}}}\right\|_{2}=1}\max_{{{\mathbf{a}}}\in{\cal{S}}}\left\|{{{\mathbf{a}}}-\beta{{\mathbf{u}}}}\right\|_{2}^{2},$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\beta\geq
0,\left\|{{{\mathbf{u}}}}\right\|_{2}=1}\left({\beta^{2}-2\beta\min_{{{\mathbf{a}}}\in{\cal{S}}}\left\langle{{{\mathbf{u}}},{{\mathbf{a}}}}\right\rangle}\right).$
(41)

From (41), we clearly have that

$\displaystyle{{\mathbf{u}}}^{\star}$
$\displaystyle=\operatornamewithlimits{arg\,max}_{\left\|{{{\mathbf{u}}}}\right\|_{2}=1}\min_{{{\mathbf{a}}}\in{\cal{S}}}\left\langle{{{\mathbf{u}}},{{\mathbf{a}}}}\right\rangle.$

In view of (34), we thus have ${{\mathbf{u}}}^{\star}={{\mathbf{t}}}^{\star}$.
Taking this fact into account, we deduce

$\displaystyle\beta^{\star}$
$\displaystyle=\operatornamewithlimits{arg\,min}_{\beta\geq
0}\left({\beta^{2}-2\beta{\delta}^{\star}}\right)=\bar{{\delta}},$

where $\bar{{\delta}}$ is defined in (40), and thus
${\tilde{{{\mathbf{t}}}}}^{\star}=\bar{{\delta}}\,{{\mathbf{t}}}^{\star}$.
Plugging
${\tilde{{{\mathbf{t}}}}}^{\star}=\bar{{\delta}}\,{{\mathbf{t}}}^{\star}$ in
(37) and using the definition of ${\delta}^{\star}$ in (35), we find

$\displaystyle{\epsilon}^{\star}=\sqrt{1-\bar{{\delta}}^{2}}.$

This shows (38)-(39).

We now prove the result of the lemma, that is

$\displaystyle{\mathcal{G}}^{d}({{\mathbf{t}}}^{\star},{\delta}^{\star})\subseteq{\mathcal{G}}^{s}({\tilde{{{\mathbf{t}}}}}^{\star},{\epsilon}^{\star}).$

This statement can equivalently be rewritten as

$\displaystyle\forall{{\mathbf{a}}}\in{\mathcal{G}}^{d}({{\mathbf{t}}}^{\star},{\delta}^{\star}):\,\left\|{{{\mathbf{a}}}-\bar{{\delta}}{{\mathbf{t}}}^{\star}}\right\|_{2}^{2}\leq
1-\bar{{\delta}}^{2}.$

If $\bar{{\delta}}=0$, the inequality is true since
$\left\|{{{\mathbf{a}}}}\right\|_{2}\leq$
$\forall\,{{\mathbf{a}}}\in{\mathcal{G}}^{d}({{\mathbf{t}}}^{\star},{\delta}^{\star})$.
If $\bar{{\delta}}={\delta}^{\star}$, the inequality is also verified because

$\displaystyle\left\|{{{\mathbf{a}}}-{\delta}^{\star}{{\mathbf{t}}}^{\star}}\right\|_{2}^{2}$
$\displaystyle=1+({\delta}^{\star})^{2}-2{\delta}^{\star}\left\langle{{{\mathbf{t}}}^{\star},{{\mathbf{a}}}}\right\rangle$
$\displaystyle\leq 1-({\delta}^{\star})^{2}$

where the last inequality follows from the fact that

$\displaystyle\forall{{\mathbf{a}}}\in{\mathcal{G}}^{d}({{\mathbf{t}}}^{\star},{\delta}^{\star}):\
\left\langle{{{\mathbf{t}}}^{\star},{{\mathbf{a}}}}\right\rangle\geq{\delta}^{\star}.$

##  Appendix C Miscellaneous Technical Lemmas

In this section, we state and prove two technical lemmas which are useful for
the derivation of the dome sphere test in Appendix A. The first lemma (Lemma
2) characterizes the properties of a particular function. The second lemma
(Lemma 3) establishes a relationship between the radius parameter $\tau$ and
the center ${{\mathbf{c}}}$ of a safe sphere.

######  Lemma 2.

If $A\in[-1,1]$ (resp. $A\in(-1,1)$), the function

$\displaystyle f(\xi)$ $\displaystyle=A\,\xi+\sqrt{1-A^{2}}\sqrt{1-\xi^{2}}$
(42)

is concave (resp. strictly concave) over the interval $[-1,1]$. Moreover, the
function $g(\xi)\triangleq\max_{\xi\leq\xi^{\prime}\leq 1}f(\xi^{\prime})$ can
be written as follows in the interval $\xi\in[-1,1]$:

$\displaystyle g(\xi)$ $\displaystyle=\left\\{\begin{array}[]{ll}1&\mbox{if
$\xi<A$}\\\
A\,\xi+\sqrt{1-A^{2}}\sqrt{1-\xi^{2}}&\mbox{otherwise}\end{array}\right..$
(45)

$g(\xi)$ is concave and non-increasing over the interval $[-1,1]$. If
$A\in(-1,1)$, it is strictly concave and strictly decreasing over the interval
$[A,1]$.

Proof: The strict concavity of $f(\xi)$ over $[-1,1]$ for $A\in(-1,1)$ can be
proved by showing that its second derivative is strictly negative over this
interval. Now, we have

$\displaystyle f^{\prime\prime}(\xi)$
$\displaystyle=-\sqrt{\frac{1-A^{2}}{(1-\xi^{2})^{3}}}<0\quad\forall\,\xi\in[-1,1].$

The concavity of $f(\xi)$ over $[-1,1]$ for $A\in[-1,1]$ then follows by
noticing that $f(\xi)$ is a linear function when $A=\pm 1$.

The expression of $g(\xi)$ in (45) can be found as follows. If $A=1$, we have

$\displaystyle\max_{\xi\leq\xi^{\prime}\leq 1}f(\xi^{\prime})$
$\displaystyle=\max_{\xi\leq\xi^{\prime}\leq
1}\xi^{\prime}=1\quad\forall\xi\in[-1,1].$ (46)

This corresponds to the definition of $g(\xi)$ in (45). If $A=-1$, we have

$\displaystyle\max_{\xi\leq\xi^{\prime}\leq 1}f(\xi^{\prime})$
$\displaystyle=\max_{\xi\leq\xi^{\prime}\leq
1}-\xi^{\prime}=-\xi\quad\forall\xi\in[-1,1].$ (47)

This again corresponds to the definition of $g(\xi)$ in (45). Let us finally
consider the case where $A\in(-1,1)$. Using the first part of the lemma, we
have that $f(\xi^{\prime})$ is strictly concave over $\xi^{\prime}\in[-1,1]$.
Simple calculus shows that $\xi^{\prime}=A$ cancels out the first derivative
of $f(\xi^{\prime})$. We thus have

$\displaystyle 1=f(A)=\max_{-1\leq\xi^{\prime}\leq 1}f(\xi^{\prime}).$ (48)

Using standard optimality conditions for concave problems, we then obtain
(45).

Finally, the concavity and the non-increasing (resp. the strict concavity and
the strictly decreasing) nature of $g(\xi)$ over $[-1,1]$ (resp. $[A,1]$) for
$A\in[-1,1]$ (resp. $A\in(-1,1)$) follows from its definition of $g(\xi)$ and
the concavity (resp. strict concavity) of $f(\xi)$.

$\square$

######  Lemma 3.

Let
${{\mathcal{R}}}=\left\\{{{\boldsymbol{\theta}}:\left\|{{\boldsymbol{\theta}}-{{\mathbf{c}}}}\right\|_{2}\leq
1-{\tau}}\right\\}$ be a safe sphere for problem (2) with
$\lambda<\lambda_{\mathrm{max}}$ (that is
${\boldsymbol{\theta}}^{\star}_{\lambda}\in{{\mathcal{R}}}$). Then, we have

$\displaystyle{\tau}\leq\left\|{{{\mathbf{c}}}}\right\|_{2}.$ (49)

Proof: If
${{\mathcal{R}}}=\left\\{{{\boldsymbol{\theta}}:\left\|{{\boldsymbol{\theta}}-{{\mathbf{c}}}}\right\|_{2}\leq
1-{\tau}}\right\\}$ is a safe region, then

$\displaystyle\left\|{{\boldsymbol{\theta}}^{\star}_{\lambda}-{{\mathbf{c}}}}\right\|_{2}\leq
1-{\tau},$ (50)

which leads, by using a triangle inequality, to

$\displaystyle\left\|{{\boldsymbol{\theta}}^{\star}_{\lambda}}\right\|_{2}-1+{\tau}\leq\left\|{{{\mathbf{c}}}}\right\|_{2}.$
(51)

Now, if $\lambda<\lambda_{\mathrm{max}}$, we have

$\displaystyle\left\|{{\boldsymbol{\theta}}^{\star}_{\lambda}}\right\|_{2}\geq
1.$ (52)

The latter claim follows from the following arguments: if
$\lambda<\lambda_{\mathrm{max}}$, we necessarily have
${\mathbf{x}}^{\star}_{\lambda}(i)>0$ for some $i\in[1\ldots{n}]$. From the
optimality condition (7), we have for such $i$:
$\left\langle{{{\mathbf{a}}}_{i},{\boldsymbol{\theta}}^{\star}_{\lambda}}\right\rangle=1$.
Hence, we obtain (52) by using the Cauchy-Schwarz inequality:

$\displaystyle\left\|{{\boldsymbol{\theta}}^{\star}_{\lambda}}\right\|_{2}\geq\left\langle{{{\mathbf{a}}}_{i},{\boldsymbol{\theta}}^{\star}_{\lambda}}\right\rangle=1.$

Finally, we obtain the main result (49) by combining (51) and (52).
$\hfill\square$

## References

  * [1] Mario A. T. Figueiredo,  “Teaching a new trick to an old dog: Revisiting the quadratic programming formulation of sparse recovery using ADMM,”  in Acoustics, Speech and Signal Processing (ICASSP), 2014 IEEE International Conference on. May 2014, pp. 1512–1516, IEEE.
  * [2] M. R. Osborne, B. Presnell, and B. A. Turlach,  “A new approach to variable selection in least squares problems,”  IMA Journal of Numerical Analysis, vol. 20, no. 3, pp. 389–403, July 2000.
  * [3] Bradley Efron, Trevor Hastie, Iain Johnstone, and Robert Tibshirani,  “Least angle regression,”  The Annals of Statistics, vol. 32, no. 2, pp. 407–451, 2004.
  * [4] Amir Beck and Marc Teboulle,  “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,”  SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 183–202, Jan. 2009.
  * [5] Laurent El Ghaoui, Vivian Viallon, and Tarek Rabbani,  “Safe feature elimination in sparse supervised learning,”  Tech. Rep. UC/EECS-2010-126, EECS Dept., University of California at Berkeley, Sept. 2010.
  * [6] Zhen J. Xiang, Hao Xu, and Peter J. Ramadge,  “Learning sparse representations of high dimensional data on large scale dictionaries,”  in Advances in Neural Information Processing Systems 24, J. Shawe-taylor, Zemel, P. Bartlett, Pereira, and Weinberger, Eds., pp. 900–908. 2011.
  * [7] Liang Dai and Kristiaan Pelckmans,  “An ellipsoid based, two-stage screening test for BPDN,”  in Signal Processing Conference (EUSIPCO), 2012 Proceedings of the 20th European. Aug. 2012, pp. 654–658, IEEE.
  * [8] Jie Wang, Peter Wonka, and Jieping Ye,  “Lasso screening rules via dual polytope projection,”  Journal of Machine Learning Research, 2015.
  * [9] Antoine Bonnefoy, Valentin Emiya, Liva Ralaivola, and Remi Gribonval,  “Dynamic screening: Accelerating first-order algorithms for the Lasso and group-Lasso,”  Signal Processing, IEEE Transactions on, vol. 63, no. 19, pp. 5121–5132, Oct. 2015.
  * [10] O. Fercoq, A. Gramfort, and J. Salmon,  “Mind the duality gap: safer rules for the Lasso,”  in ICML, 2015.
  * [11] C. Herzet and A. Malti,  “Safe screening tests for LASSO based on firmly non-expansiveness,”  in 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), March 2016, pp. 4732–4736.
  * [12] Zhen J. Xiang and Peter J. Ramadge,  “Fast Lasso screening tests based on correlations,”  in Acoustics, Speech and Signal Processing (ICASSP), 2012 IEEE International Conference on. Mar. 2012, pp. 2137–2140, IEEE.
  * [13] Zhen J. Xiang, Yun Wang, and Peter J. Ramadge,  “Screening tests for Lasso problems,” arXiv:1405.4897v1, May 2014\.
  * [14] Emmanuel J. Candès and Carlos Fernandez-Granda,  “Towards a mathematical theory of super-resolution,”  Comm. Pure Appl. Math, vol. 67, no. 6, pp. 906–956, June 2014.
  * [15] Vincent Duval and Gabriel Peyré,  “Exact support recovery for sparse spikes deconvolution,”  Foundations of Computational Mathematics, vol. 15, no. 5, pp. 1315–1355, 2015.
  * [16] S. Foucart and H. Rauhut,  A mathematical introduction to compressive sensing.,  Applied and Numerical Harmonic Analysis. Birkhaüser, 2013.
  * [17] D. P. Bertsekas,  Nonlinear Programming,  Athena Scientific, USA, 2003.
  * [18] Cédric Herzet and Angélique Drémeau,  “Joint screening tests for Lasso,”  arXiv:1710.09809, 2017.