Simple Error Bounds for Regularized Noisy Linear Inverse Problems

I Introduction

It solves for an estimate $\hat{\mathbf{x}}$ that best fits the vector of observations $\mathbf{y}$ while at the same time retains structure similar to that of $\mathbf{x}_{0}$. Program (1), with $f(\mathbf{x})=\|x\|_{1}$, was introduced in by Tibshirani for estimating sparse signals and is known as the “lasso” in the statistics literature. In practical situations, prior knowledge of $f(\mathbf{x}_{0})$ is typically not available, which makes (1) impossible to solve. Instead, one can solve regularized versions of it, like,

I-B Contribution

In this work, we derive a simple non-asymptotic upper bound on the normalized estimation error $\frac{\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|_{2}}{\|\mathbf{z}\|_{2}}$ of the regularized estimator (2), which holds for arbitrary convex regularizers $f(\cdot)$. We assume that the measurement matrix $\mathbf{A}$ has independent zero-mean normal entries of variance $\frac{1}{m}$. For the noise vector $\mathbf{z}$, we only require it being chosen independently of $\mathbf{A}$.

Our upper bound is a simple function of the number of measurements $m$ and, of a summary parameter $\delta({\lambda}\partial f(\mathbf{x}_{0}))$, termed the Gaussian squared distance; $\delta({\lambda}\partial f(\mathbf{x}_{0}))$ captures the structure induced by $f(\cdot)$, the particular $\mathbf{x}_{0}$ we are trying to recover and the value of the regularizer parameter ${\lambda}$. For example, when we are interested in a sparse signal, the structure is captured by $f(\cdot)$, whereas the actual sparsity level (i.e. how many entries are zero) is captured by $\mathbf{x}_{0}$. (Thus $\delta({\lambda}\partial f(\mathbf{x}_{0}))$ is the same for all $k$-sparse $\mathbf{x}_{0}$). In recent works , $\delta({\lambda}\partial f(\mathbf{x}_{0}))$ has been calculated for a number of practical regularizers $f(\cdot)$; making use of these results, translates our bound to explicit formulae. Finally, the constants involved in our result are small and nearly accurate. As a byproduct, our bound provides a guideline on the important practical problem of optimally tuning the regularizer parameter ${\lambda}$.

I-C Related work

II preliminaries

For the rest of the paper, let $\mathcal{N}(\mu,\sigma^{2})$ denote the normal distribution of mean $\mu$ and variance $\sigma^{2}$. Also, to simplify notation, let us write $\|\cdot\|$ instead of $\|\cdot\|_{2}$.

$\partial f(\mathbf{x}_{0})$ is a nonempty, convex and compact set . It, also, does not contain the origin since we assumed that $\mathbf{x}_{0}$ is not a minimizer. For any nonnegative number ${\lambda}\geq 0$, we denote the scaled (by ${\lambda}$) subdifferential set as ${\lambda}\partial f(\mathbf{x}_{0})=\{{\lambda}\mathbf{s}|\mathbf{s}\in\partial f(\mathbf{x}_{0})\}$. Also, for the conic hull of the subdifferential $\partial f(\mathbf{x}_{0})$, we write $\text{cone}(\partial f(\mathbf{x}_{0}))=\{\mathbf{s}|\mathbf{s}\in{\lambda}\partial f(\mathbf{x}_{0}),\text{ for some }{\lambda}\geq 0\}$.

II-A2 Gaussian squared distance

II-B Gordon’s Comparison Lemma and Concentration results

In the current section, we outline the main tools that underly the proof of our result. We begin with a very useful lemma proved by Gordon which allows a probabilistic comparison between two Gaussian processes. Here, we use a slightly modified version of the original lemma (see Lemma 5.1 in ).

III Result

Theorem III.1 provides a simple, general, non-asymptotic and (rather) sharp upper bound on the error of the regularized lasso estimator (2), which also takes into account the specific choice of the regularizer parameter ${\lambda}\geq 0$. In principle, the bound applies to any signal class that exhibits some sort of low-dimensionality (see and references therein). It is non-asymptotic and is applicable in any regime of $m$, $\lambda$ and $\delta({\lambda}\partial f(\mathbf{x}_{0}))$. Also, the constants involved in it are small making it rather tightWe suspect and is also supported by our simulations (e.g. Figure 2) that the factor of 2 in (4) is an artifact of our proof technique and not essential..

The Gaussian distance term $\delta({\lambda}\partial f(\mathbf{x}_{0}))$ summarizes the geometry of the problem and is key in (4). In (Proposition 4.4), it is proven that $\delta({\lambda}\partial f(\mathbf{x}_{0}))$, when viewed as a function of ${\lambda}\geq 0$, is strictly convex, differentiable for ${\lambda}>0$ and achieves its minimum at a unique point. Figure 1 illustrates this behavior; $\sqrt{m-1}-\sqrt{\delta({\lambda}\partial f(\mathbf{x}_{0}))}$ achieves its unique maximum value at some ${\lambda}=\lambda_{\text{best}}$, it is strictly increasing for ${\lambda}<\lambda_{\text{best}}$ and strictly decreasing for ${\lambda}>\lambda_{\text{best}}$. For the bound in (4) to be at all meaningful, we require $m>\min_{{\lambda}\geq 0}\delta({\lambda}\partial f(\mathbf{x}_{0}))=\delta(\lambda_{\text{best}}\partial f(\mathbf{x}_{0}))$. This is perfectly in line with our discussion in Section II-A2, and translates to the number of measurements being large enough to at least guarantee noiseless recovery . Lemma 8.1 in proves that there exists a unique ${\lambda}_{max}$ satisfying ${\lambda}_{max}>\lambda_{\text{best}}$ and $\sqrt{\delta({\lambda}_{max}\partial f(\mathbf{x}_{0}))}=\sqrt{m-1}$. Similarly, when $m\leq n$, there exists unique ${\lambda}_{min}<\lambda_{\text{best}}$ satisfying $\sqrt{\delta({\lambda}_{min}\partial f(\mathbf{x}_{0}))}=\sqrt{m-1}$. From this, it follows that $\sqrt{m-1}>\sqrt{\delta({\lambda}\partial f(\mathbf{x}_{0}))}$ if and only if ${\lambda}\in({\lambda}_{min},{\lambda}_{max})$. This is exactly the range of values of the regularizer parameter ${\lambda}$ for which (4) is meaningful; see also Figure 1.

III-B Application to sparse and low-rank estimation

Any bound on $\delta({\lambda}\partial f(\mathbf{x}_{0}))$ translates, through Theorem III.1, into an upper bound on the estimation error of (2). Such bounds have been recently derived in , for a variety of structure-inducing functions $f(\cdot)$. For purposes of illustration and completeness, we review here those results for the celebrated cases of sparse and low-rank estimation.

Suppose $\mathbf{x}_{0}$ is a $k$-sparse signal and $f(\cdot)=\|\cdot\|_{1}$. Denote by $S$ the support set of $\mathbf{x}_{0}$, and by $S^{c}$ its complement. The subdifferential at $\mathbf{x}_{0}$ is,

Then, $\delta({\lambda}\partial\|\mathbf{x}_{0}\|_{1})$ is equal to ()

where $\text{erfc}(\cdot)$ denotes the standard complementary error function. Note that $\delta({\lambda}\partial\|\mathbf{x}_{0}\|_{1})$ depends only on $n,{\lambda}$ and $k=|S|$, and not explicitly on S itself (which is not known). Substituting the expression in (5) in place of the $\delta({\lambda}\partial f(\mathbf{x}_{0}))$ term in (4), yields an explicit expression for our upper bound, in terms of $n$, $m$, $k$ and ${\lambda}$. A simpler upper bound which does not involve error functions is obtained in Table 3 in , and is given by

Analogous expressions and closed-form upper bounds can be obtained when $\mathbf{x}_{0}$ is block-sparse .

III-B2 Low-rank matrices

III-C Comparison to related work

III-C2 Comparison to the constrained lasso

Under the same assumptions as in Theorem III.1, it is proven in that, for any $0<t\leq\sqrt{m-1}-\sqrt{\delta(\text{cone}(\partial f(\mathbf{x}_{0})))}$, with probability $1-{6}\exp(-{t^{2}}/{26})$, the estimation error $\|\hat{\mathbf{x}}-\mathbf{x}_{0}\|$ of (1) is upper bounded as follows,

Comparing this to (4) reveals the similar nature of the two results. Apart from a factor of $2$ in (4), the upper bound on the error of the regularized lasso (2) for fixed ${\lambda}$, is essentially the same as the upper bound on the error of the constrained lasso (1), with $\delta(\text{cone}(\partial f(\mathbf{x}_{0})))$ replaced by $\delta({\lambda}\partial f(\mathbf{x}_{0}))$. Recent works prove that $\delta(\text{cone}(\partial f(\mathbf{x}_{0})))\approx\min_{{\lambda}\geq 0}\delta({\lambda}\partial f(\mathbf{x}_{0}))=\delta(\lambda_{\text{best}}\partial f(\mathbf{x}_{0}))$. Our bound, then, suggests that setting ${\lambda}=\lambda_{\text{best}}$ in (2) achieves performance almost as good as that of (1).

III-C3 Sharp error bounds

performs a detailed analysis of the regularized lasso problem (2) under the additional assumption that the entries of the noise vector $\mathbf{z}$ are distributed $\mathcal{N}(0,\sigma^{2})$. In particular, when $\sigma\rightarrow 0$ and $m$ is large enough, they prove that with high probability,

for ${\lambda}$ belonging to a particular subset of $({\lambda}_{min},{\lambda}_{max})$. As expected, our bound in Theorem III.1 is larger than the term in (7). However, apart from a factor of $2$, it only differs from the quantity in (7) in the denominator, where instead of $\sqrt{m-\delta({\lambda}\partial f(\mathbf{x}_{0}))}$, we have the smaller $\sqrt{m-1}-\sqrt{\delta({\lambda}\partial f(\mathbf{x}_{0}))}$. This difference becomes insignificant and indicates that our bound is rather tight when $m$ is large. Although the authors in conjecture that (7) upper bounds the estimation error for arbitrary values of the noise variance $\sigma^{2}$, they do not prove so. In that sense, and to the best of our knowledge, Theorem III.1 is the first rigorous upper bound on the estimation error of (2), which holds for general convex regularizers, is non-asymptotic and requires no assumption on the distribution of $\mathbf{z}$.

III-D Simulation results

Figure 2 illustrates the bound of Theorem III.1, which is given in red for $n=340$, $m=140$, $k=10$ and for $\mathbf{A}$ having $\mathcal{N}(0,\frac{1}{m})$ entries. The upper bound from , which is asymptotic in $m$ and only applies to i.i.d Gaussian $\mathbf{z}$, is given in black. In our simulations, we assume $\mathbf{x}_{0}$ is a random unit norm vector over its support and consider both i.i.d $\mathcal{N}(0,\sigma^{2})$, as well as, non-Gaussian noise vectors $\mathbf{z}$. We have plotted the realizations of the normalized error for different values of ${\lambda}$ and $\sigma$. As noted, the bound in is occasionally violated since it requires very large $m$, as well as, i.i.d Gaussian noise. On the other hand, the bound given in (4) always holds.

IV Proof of Theorem III.1

It is convenient to rewrite (2) in terms of the error vector $\mathbf{w}=\mathbf{x}-\mathbf{x}_{0}$ as follows:

Denote the solution of (8) by $\hat{\mathbf{w}}$. Then, $\hat{\mathbf{w}}=\hat{\mathbf{x}}-\mathbf{x}_{0}$ and (4) bounds $\|\hat{\mathbf{w}}\|$. To simplify notation, for the rest of the proof, we denote the value of that upper bound as

Fix ${\lambda}$ and $t$, as in the statement of the lemma. From the convexity of $f(\cdot)$, $f(\mathbf{x}_{0}+\mathbf{w})-f(\mathbf{x}_{0})\geq\max_{\mathbf{s}\in\partial f(\mathbf{x}_{0})}\mathbf{s}^{T}\mathbf{w}$. Hence, it suffices to prove that w.h.p. over $\mathbf{A}$,

where, $\mathcal{L}(t;\mathbf{g},\mathbf{h})$ is defined as

In the remaining, we analyze the simpler optimization problem defined in (11), and prove that $\mathcal{L}(t;\mathbf{g},\mathbf{h})>\|\overline{\mathbf{z}}\|$ holds with probability $1-\frac{5}{2}\exp(-t^{2}/32)$. We begin with simplifying the expression for $\mathcal{L}(t;\mathbf{g},\mathbf{h})$, as follows:

The first equality above follows after performing the trivial maximization over $\mathbf{a}$ in (11). The second, uses the fact that $\max_{\|w\|=\alpha}\min_{\mathbf{s}\in{\lambda}\partial f(\mathbf{x}_{0})}(\mathbf{h}-\mathbf{s})^{T}\mathbf{w}=\min_{\mathbf{s}\in{\lambda}\partial f(\mathbf{x}_{0})}\max_{\|w\|=\alpha}(\mathbf{h}-\mathbf{s})^{T}\mathbf{w}=\alpha\cdot\text{{dist}}(\mathbf{h},{\lambda}\partial f(\mathbf{x}_{0}))$, for all $\alpha\geq 0$. For a proof of this see Lemma E.1 in .

Next, we show that $\mathcal{L}(t;\mathbf{g},\mathbf{h})$ is strictly greater than $\|\overline{\mathbf{z}}\|$ with the desired high probability over realizations of $\mathbf{g}$ and $\mathbf{h}$. Consider the event $\mathcal{E}_{t}$ of $\mathbf{g}$ and $\mathbf{h}$ satisfying all three conditions listed below,

Fix any $0<t\leq(\sqrt{m-1}-\sqrt{\delta({\lambda}\partial f(\mathbf{x}_{0}))})$. Suppose $\mathbf{g}$ and $\mathbf{h}$ are such that (13) holds and recall the definition of $\mathcal{L}(t;\mathbf{g},\mathbf{h})$ in (12). Then, $\mathcal{L}(t;\mathbf{g},\mathbf{h})>\|\overline{\mathbf{z}}\|.$

V Future directions

References