Simple Bounds for Noisy Linear Inverse Problems with Exact Side Information

Introduction

Lasso is introduced by Tibshirani in . The standard Lasso problem solves,

2. SOCP with exact side information

SOCP is the name given to a class of algorithms. For linear inverse problems, a commonly used instance is the following ,

Here $\delta$ is a known upper bound on the noise level $\|\mathbf{z}\|$. This ensures that the unknown signal $\mathbf{x}_{0}$ is feasible for the SOCP. In this work, we will assume the exact information of $\|\mathbf{z}\|$ and solve,

Lasso will assume the knowledge about the signal, $f(\mathbf{x}_{0})$.

SOCP will assume the knowledge about the noise, $\|\mathbf{z}\|$.

Can we give very sharp bounds with small and accurate constants?

Can we do these non-asymptotically, i.e., for possibly very small number of measurements and/or sparsity levels?

Result

We will first state the general result and will consider specific examples later on. Let us introduce the “Gaussian width” of a set. This concept is crucial for the statement of our results.

Next, we require the definition of the tangent cone of a function $f(\cdot)$ at some $\mathbf{x}\in\mathbf{R}^{n}$. For this definition, let $\text{cone}(\cdot)$ and $\text{Cl}(\cdot)$ return the conic hull and the closure of a set, respectively.

where $\eta(\mathbf{x}_{0},t)=\frac{\sqrt{m}}{\gamma_{m-1}}\frac{\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))+t}{\gamma_{m}-\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))-t}$.

Remark 1: Observing that $\gamma_{m-1}\gamma_{m}=m-1$ and $\gamma_{m-1}\leq\sqrt{m-1}$ leads to the bound, $\eta(\mathbf{x}_{0},t)\leq\ratio\frac{\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))+t}{\sqrt{m-1}-\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))-t}$.

Remark 2: In Theorem 1, we require $\gamma_{m}\geq\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$. It has been shown that, this is indeed necessary, . When $\gamma_{m}<\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$, it is futile to expect noise robustness, as one cannot perfectly recover $\mathbf{x}_{0}$ from noiseless observations $\mathbf{y}=\mathbf{A}\mathbf{x}$ (cf. Theorem 3.4 of ).

Our bound is only in terms of the Gaussian width; which has been the subject of several works . This makes it possible to apply Theorem 1 for specific choices of $f(\cdot)$ and $\mathbf{x}_{0}$ previously studied in the literature.

State-of-the-art applications

We will now state our results for specific signal choices by making use of the existing results in the literature that compute upper bounds on the Gaussian width term $\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$.

$\bullet$ Low-rank matrices: Nuclear norm (sum of the singular values) is the standard choice to encourage a low-rank solution. Suppose $\mathbf{x}_{0}$ is a rank-$r$ matrix of size $d\times d$. For this choice, it is known that $\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))\leq\sqrt{3r(2d-r)}$, .

$\bullet$ Other low-dimensional models: There are increasingly more signal classes that exhibit low-dimensionality and to which our results would apply. Some of these are as follows.

Non-negativity constraint: $\mathbf{x}_{0}$ has non-negative entries, .

Low-rank plus sparse matrices: $\mathbf{x}_{0}$ can be represented as sum of a low-rank and a sparse matrix, .

Signals with sparse gradient: Rather than $\mathbf{x}_{0}$, its gradient ${\bf{d}}_{\mathbf{x}_{0}}(i)=\mathbf{x}_{0}(i)-\mathbf{x}_{0}(i-1)$ is sparse, .

Low-rank tensors: $\mathbf{x}_{0}$ is a tensor and its unfoldings are low-rank matrices (see ).

Simultaneously sparse and low-rank matrices: For instance, $\mathbf{x}_{0}=\mathbf{s}\mathbf{s}^{T}$ for a sparse vector $\mathbf{s}$, .

For more examples, the reader is referred to .

Interpretation of the results

We will now argue that, one can easily interpret our results when the system $\mathbf{y}=\mathbf{A}\mathbf{x}_{0}+\mathbf{z}$ is seen as an $m\times\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))^{2}$ system rather than $m\times n$.

Consider the least-squares problem where one simply solves,

It is clear that when $m<n$, (4.1) is hopeless and when $m>n$ and $\mathbf{A}$ has i.i.d. entries, $\mathbf{A}$ becomes full rank and the solution is $\mathbf{x}^{*}=(\mathbf{A}^{T}\mathbf{A})^{-1}\mathbf{A}^{T}\mathbf{y}$. Hence, denoting the projection of $\mathbf{z}$ onto the range space of $\mathbf{A}$ by $\text{Proj}(\mathbf{z},\text{Range}(\mathbf{A}))$ and the minimum singular value of $\mathbf{A}$ by $\sigma_{min}(\mathbf{A})$,

It is well known that, when $\mathbf{A}$ has $\mathcal{N}(0,\frac{1}{m})$ entries, $\sigma_{min}(\mathbf{A})\approx 1-\sqrt{\frac{n}{m}}$, . Also, since the range space is generated uniformly at random, $\|\text{Proj}(\mathbf{z},\text{Range}(\mathbf{A}))\|\approx\sqrt{\frac{n}{m}}\|\mathbf{z}\|$. Consequently,

So, what is the relation between (4.3) and (2.1)? Ignoring the $t$’s and using $\gamma_{m}\approx\sqrt{m}$ in (2.1) , we find,

One can move from (4.4) to (4.3) by simply replacing the $\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$ terms with $\sqrt{n}$. This indeed indicates that the Lasso and SOCP problems behave as $m\times\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))^{2}$ systems rather than $m\times n$ ones.

2. Comparison to related works

Sparse recovery: A classical result states that, when $\mathbf{x}_{0}$ is a sparse signal and when $\mathbf{A}$ has independent $\mathcal{N}(0,\frac{1}{m})$ entries the Lasso estimation error obeys $\mathcal{O}\left(\|\mathbf{z}\|\sqrt{\frac{{k\log n}}{m}}\right)$ when $m=\Omega({k\log\frac{n}{k}})$, . Our bound given in Corollary 1 is fully consistent with this, however, we provide very small and accurate constants. In particular, the phase transition occurring around $2k\log\frac{2n}{k}$ number of measurements shows up explicitly in our bound in Corollary 1 (see the term $\sqrt{m-1}-\sqrt{2k\log\frac{2n}{k}}$ in the denominator).

Generalized linear inverse problems: Close to the present paper is the work due to . In , Chandrasekaran et al. perform error analysis of the SOCP problem. Their result (cf. Corollary 3.3 in ) shows that with probability $1-\exp(-\frac{1}{2}t^{2})$,

Our approach is related; however, we provide a more careful analysis. As a result of this, and in contrast to the error bound in (4.5) which grows linearly with the noise level $\|\mathbf{z}\|$, our bound (2.1) is scaled by a constant factor of $\frac{\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))}{\sqrt{m}}$. This is due to the fact that we are able to carefully remove a significant component of the noise which cannot contribute to the error term.

Sharp error bounds for the Lasso estimator: There has been significant research interest in characterizing the error performance of the Lasso estimators. provides a unified analysis of the error performance of the Lasso estimator (1.1), which can be specialized to many regularizer functions. More recent works establish sharper bounds for the Lasso estimation error. In ; Bayati, Montanari and Donoho provide explicit characterizations in an asymptotic setting for $f(\cdot)=\|\cdot\|_{1}$. Closer in nature to the present paper, are the works and . The author in analyzes the Lasso problem (1.2) with prior information on $f(\mathbf{x}_{0})$ when $f(\cdot)=\|\cdot\|_{1}$. generalizes the precise analysis to arbitrary convex functions and, most importantly, extends it to penalized Lasso problems of the form (1.1). Although tighter, the bounds in require stronger assumptions than ours, namely, an i.i.d. Gaussian noise vector $\mathbf{z}$ and an asymptotic setting where $m$ and $\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$ is large enough. Their results translates to our framework as,

The difference between (4.4) and (4.6) is in the denominator. $\sqrt{m-\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))^{2}}\geq\sqrt{m}-\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$ for all regimes of $0\leq\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))^{2}<m$. The contrast becomes significant when $m\approx\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))^{2}$. In particular, setting $m=(1+\epsilon)^{2}\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))^{2}$, we have,

In summary, when $\epsilon$ is large, the bounds of this paper are as good as those of . When $\epsilon$ is small, they can be arbitrarily worse. Simulation results (see Figure 1) verify that the error bounds of Theorem 1 become sharp for large number of measurements $m$. This difference can be intuitively explained by considering the least-squares error in (4.2). There, using $\sigma_{min}(\mathbf{A})$ as an upper bound results in a looser bound. For a vector $\mathbf{z}$ independent of $\mathbf{A}$, we actually have,

In this sense, considers the precise behavior of the left-hand side in (4.2) and we consider the looser bound given in the right-hand side; which makes use of the minimum singular value $\sigma_{min}(\mathbf{A})$.

Further remarks

For our results, we either assumed knowledge about the signal $f(\mathbf{x}_{0})$, or knowledge about the noise $\|\mathbf{z}\|$. It is desirable to not be dependent on such quantities. A natural way to break this dependence is by using the following program,

While we leave the analysis of (5.1) to a future work, we should emphasize that, proposed using,

2. Adversarial noise

We will now consider the scenario where one has adversarial noise, i.e., noise has the information of the sensing matrix $\mathbf{A}$ and can adapt itself accordingly. In this case, the reconstruction error can become significantly worse. The following proposition illustrates this for the Lasso problem (1.2).

Let $\mathbf{x}^{*}=\arg\min f(\mathbf{x})$. Then, choose $\mathbf{z}=\mathbf{A}(\mathbf{x}^{*}-\mathbf{x}_{0})$; which yields $\mathbf{y}=\mathbf{A}\mathbf{x}_{0}+\mathbf{z}=\mathbf{A}\mathbf{x}^{*}$. By construction, $\mathbf{z}\sim\mathcal{N}(0,\frac{\|\mathbf{x}^{*}-\mathbf{x}_{0}\|^{2}}{m}\mathbf{I}_{m})$, hence with probability $1-\exp(-\frac{t^{2}}{2})$, $\|\mathbf{z}\|\leq(\gamma_{m}+t)\frac{\|\mathbf{x}^{*}-\mathbf{x}_{0}\|}{\sqrt{m}}$. Since $f(\mathbf{x}^{*})\leq f(\mathbf{x}_{0})$ and $\mathbf{A}\mathbf{x}^{*}-\mathbf{y}=0$, $\mathbf{x}^{*}$ is a (feasible) minimizer of (1.2) and $\|\mathbf{x}^{*}-\mathbf{x}_{0}\|\geq\frac{\sqrt{m}}{\gamma_{m}+t}\|\mathbf{z}\|$. ∎

Proposition 1 suggests that we can make error as big as the noise term $\|\mathbf{z}\|$. This contrasts with Theorem 1 where the error is approximately $\frac{\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))}{\sqrt{m}}\|\mathbf{z}\|$ for sufficiently large $m$. The adversarial noise scenario can again be connected to least-squares in Section 4.1. In (4.2), if the noise $\mathbf{z}$ already lies on $\text{Range}(\mathbf{A})$, we will not have the reduction of $\sqrt{\frac{n}{m}}$ in the error. Similarly, Proposition 1 constructs a noise vector that that lies in $\text{Range}(\mathbf{A})$ and originates from the tangent cone element $\mathbf{x}^{*}-\mathbf{x}_{0}$. Hence, the resulting error norm is amplified by approximately $\frac{\sqrt{m}}{\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))}$.

Our next result gives an upper bound on the worst case error, which is close to the lower bound when $\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))\ll\gamma_{m}$. This uses a very similar argument to Corollary 3.3 of .

From Lemma 1, with probability $1-\exp(-\frac{t^{2}}{2})$, we have,

Assuming this happens, we will show the result.

Proof for Lasso: $\mathbf{x}_{0}$ is feasible for (1.2) hence $\|\mathbf{y}-\mathbf{A}\mathbf{x}^{*}_{L}\|\leq\|\mathbf{z}\|$. Also $\mathbf{x}^{*}_{L}-\mathbf{x}_{0}\in T_{f}(\mathbf{x}_{0})$. Consequently,

Proof for SOCP: $\mathbf{x}_{0}$ is feasible for (1.3) hence $f(\mathbf{x}^{*}_{S})\leq f(\mathbf{x}_{0})$ and $\|\mathbf{y}-\mathbf{A}\mathbf{x}^{*}_{S}\|\leq\|\mathbf{z}\|$ holds. Hence (5.2) will apply for $\mathbf{x}^{*}_{S}$ as well.

Proof of the Main Result

We begin with introducing some necessary notation in Section 6.1. In Section 6.2, we enlist two critical results for our analysis. Finally, Section 6.3 provides the proof.

Throughout the proofs, $\mathbf{A}{T}_{f}(\mathbf{x}_{0})$ will denote the cone obtained by multiplying elements of $T_{f}(\mathbf{x}_{0})$ by $\mathbf{A}$., i.e.,

When $\mathcal{C}$ is a closed and convex cone, its polar is defined as \mathcal{C}^{\circ}=\{\mathbf{u}\big{|}\mathbf{u}^{T}\mathbf{v}\leq 0,~{}\text{for all}~{}\mathbf{v}\in\mathcal{C}\}. Moreau’s Decomposition Theorem , says that, any vector $\mathbf{v}$ can be decomposed as,

2. Preliminary Results

The next lemma is due to Gordon and relates the Gaussian width to the restricted eigenvalue. This concept is similar to restricted isometry property and has been topic of several related papers, .

The next theorem is the main technical contribution of this work. It provides an upper bound on the correlation between a vector and elements of a cone multiplied by a Gaussian matrix.

with probability $1-5\exp(-\frac{t^{2}}{26})$.

3. Proof of Theorem 1

We will start by providing deterministic bounds on the estimation error. Then, with the help of Lemma 1 and Theorem 2, we will finalize the proof.

Consider the problems (1.2) and (1.3). We have,

Using (6.1), let us write, $\mathbf{z}=\mathbf{z}_{1}+\mathbf{z}_{2}$ where $\mathbf{z}_{1}=\text{Proj}(\mathbf{z},\mathbf{A}{T}_{f}(\mathbf{x}_{0}))$, $\mathbf{z}_{2}=\text{Proj}(\mathbf{z},(\mathbf{A}{T}_{f}(\mathbf{x}_{0}))^{\circ})$, $\mathbf{z}_{1}^{T}\mathbf{z}_{2}=0$.

$\bullet$ Lasso: Let $\mathbf{w}^{*}=\mathbf{x}^{*}_{L}-\mathbf{x}_{0}$. We will first show that $\|\mathbf{A}\mathbf{w}^{*}\|\leq\|\mathbf{z}_{1}\|$. Assume it is not the case and let $\mathbf{w}^{\prime}=\frac{\|\mathbf{z}_{1}\|}{\|\mathbf{A}\mathbf{w}^{*}\|}\mathbf{w}^{*}$. From convexity, $f(\mathbf{x}_{0}+\mathbf{w}^{\prime})\leq f(\mathbf{x}_{0})$, hence $\mathbf{w}^{\prime}$ is feasible. We will show that $\|\mathbf{z}-\mathbf{A}\mathbf{w}^{\prime}\|<\|\mathbf{z}-\mathbf{A}\mathbf{w}^{*}\|$, which will contradict with the optimality of $\mathbf{w}^{*}$.

Hence $\|\mathbf{A}\mathbf{w}^{*}\|\leq\|\mathbf{z}_{1}\|$. To conclude, we use the fact that $\|\mathbf{w}^{*}\|\leq\frac{\|\mathbf{A}\mathbf{w}^{*}\|}{\sigma_{min}(\mathbf{A},T_{f}(\mathbf{x}_{0})\cap{\mathcal{S}}^{n-1})}$.

$\bullet$ SOCP: Let $\mathbf{w}^{*}=\mathbf{x}^{*}_{S}-\mathbf{x}_{0}$. Then, the problem becomes,

First observe that is feasible, hence $\mathbf{w}^{*}\in T_{f}(\mathbf{x}_{0})$. Then, for any $\mathbf{w}\in T_{f}(\mathbf{x}_{0})$,

where we used the fact that $\mathbf{z}_{2}^{T}\mathbf{A}\mathbf{w}\leq 0$ as $\mathbf{A}\mathbf{w}\in\mathbf{A}{T}_{f}(\mathbf{x}_{0})$. Now, using $\mathbf{w}^{*}\in T_{f}(\mathbf{x}_{0})$, we find,

Suppose $0\leq t<\gamma_{m}-\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$. We will make use of the fact that, the following events hold with probability $1-\exp(-\frac{t^{2}}{2})-5\exp(-\frac{t^{2}}{26})$.

Observe that $\bm{\omega}(T_{f}(\mathbf{x}_{0})\cap\mathcal{S}^{n-1})\leq\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$. Hence, applying Lemma 1 with $\mathbf{G}=\sqrt{m}\mathbf{A}$ and $\mathcal{C}=T_{f}(\mathbf{x}_{0})\cap{\mathcal{S}}^{n-1}$, with probability $1-\exp(-\frac{t^{2}}{2})$, we have,

Applying Theorem 2 with $\mathbf{A}=\frac{\mathbf{G}}{\sqrt{m}}$ and $\mathcal{C}=T_{f}(\mathbf{x}_{0})$, with probability $1-5\exp(-\frac{t^{2}}{26})$,

To see this, pick $\mathbf{v}$ in (6.2) such that $\mathbf{A}\mathbf{v}=\frac{\text{Proj}(\mathbf{z},\mathbf{A}{T}_{f}(\mathbf{x}_{0}))}{\|\text{Proj}(\mathbf{z},\mathbf{A}{T}_{f}(\mathbf{x}_{0}))\|}$, which gives $\mathbf{z}^{T}\mathbf{A}\mathbf{v}=\|\text{Proj}(\mathbf{z},\mathbf{A}{T}_{f}(\mathbf{x}_{0}))\|$.

Now, the bounds in (2.1) and (2.2) follow when we substitute (6.3) and (6.4) in Lemma 2. ∎

Proof of Theorem 2

There are a few ingredients of the proof. First, we require a result, which allows us to compare two Gaussian processes. This result is again due to Gordon (see Lemma 3.1 in ). We make use of a slightly modified version of the original lemma, which can be found in (cf. Lemma 5.1).

The next lemma is a standard result on concentration properties of Lipschitz functions of Gaussian vectors, .

The following lemma provides a useful identity for the projection of a vector onto a cone.

From (6.1), we have $\mathbf{v}=\text{Proj}(\mathbf{v},\mathcal{C})+\text{Proj}(\mathbf{v},\mathcal{C}^{\circ})$, where $\left<\text{Proj}(\mathbf{v},\mathcal{C}),\text{Proj}(\mathbf{v},\mathcal{C}^{\circ})\right>=0$. For any $\mathbf{u}\in\mathcal{C}$, $\mathbf{u}^{T}\text{Proj}(\mathbf{v},\mathcal{C}^{\circ})\leq 0$, hence, $\mathbf{u}^{T}\mathbf{v}\leq\mathbf{u}^{T}\text{Proj}(\mathbf{v},\mathcal{C})$. Since $\mathbf{u}\in{\mathcal{B}}^{n-1}$, we further find from the Cauchy-Schwarz inequality that $\mathbf{u}^{T}\mathbf{v}\leq\|\text{Proj}(\mathbf{v},\mathcal{C})\|$. On the other hand, picking $\mathbf{u}=\frac{\text{Proj}(\mathbf{v},\mathcal{C})}{\|\text{Proj}(\mathbf{v},\mathcal{C})\|}\in\mathcal{C}\cap{\mathcal{B}}^{n-1}$, achieves $\mathbf{u}^{T}\mathbf{v}=\|\text{Proj}(\mathbf{v},\mathcal{C})\|$.∎

2. Proof

When $\mathbf{z}=0$, the problem is trivial, hence, assume $\mathbf{z}\neq 0$. If $\alpha\geq\|\mathbf{z}\|$, we clearly have,

Hence, without loss of generality, we may assume $\frac{\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))+t}{\gamma_{m-1}}\|\mathbf{z}\|\leq\alpha<\|\mathbf{z}\|$ and $t<\gamma_{m-1}-\bm{\omega}(\hat{T}_{f}(\mathbf{x}_{0}))$. Define the set ${\mathcal{S}}_{\mathbf{z}}=\alpha{\mathcal{S}}^{m-1}-\mathbf{z}$ and let $\hat{\mathcal{C}}:=\mathcal{C}\cap{\mathcal{B}}^{n-1}$. Under this notation,

With this $\min\max$ formulation, we can apply Lemma 3 and use the fact that $\|\mathbf{v}\|=1$ to find,

where $\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}_{m})$ and $\mathbf{g}\sim\mathcal{N}(0,\mathbf{I}_{n})$. For the rest of the proof we focus on the analysis of the simpler optimization problem on the right hand side of (7.1). Begin by noting that $\mathcal{C}\cap{\mathcal{S}}^{n-1}\subset\hat{\mathcal{C}}$, hence,

The only term in which $\mathbf{v}$ appears above is $\mathbf{g}^{T}\mathbf{v}$. From Lemma 5, $\max_{\mathbf{v}\in\hat{\mathcal{C}}}\mathbf{g}^{T}\mathbf{v}=\|\text{Proj}(\mathbf{g},\mathcal{C})\|$. Hence, we find,

Now, we make the change of variable $\mathbf{u}=\alpha\mathbf{a}-\mathbf{z}$ and write the right-hand side above as,

Recall from (7.1), that we want to lower bound the optimization problem above. The choice of $\mathbf{a}$ is up to us and a good choice will guarantee a good lower bound on the right hand side of (7.2). Let $\hat{\mathbf{z}}:=\frac{\mathbf{z}}{\|\mathbf{z}\|}$. Further, denote the projection of $\mathbf{h}$ onto $\mathbf{z}$ as $\mathbf{h}_{2}:=\hat{\mathbf{z}}\hat{\mathbf{z}}^{T}\mathbf{h}$. Also, $\mathbf{h}_{1}:=\mathbf{h}-\mathbf{h}_{2}$ and $\mathbf{h}_{1}$ is, by construction, orthogonal to $\mathbf{z}$ and is independent of $\mathbf{h}_{2}$. Let us choose

for some $\tau>0$ (to be determined) and the associated probabilities which are obtained as an application of Lemma 4.

From the initial assumptions $\gamma_{m-1}-\bm{\omega}(\mathcal{\mathcal{C}}\cap{\mathcal{B}}^{n-1})>t$. For the rest of the discussion, let $\tau=\frac{t}{3.6}$ and assume the three events in (7.3) hold, which happens with probability $1-\frac{5}{2}\exp(-\frac{\tau^{2}}{2})\geq 1-\frac{5}{2}\exp(-\frac{t^{2}}{26})$. We will now show that $\kappa_{2}-\kappa_{1}-\kappa_{3}\geq 0$. First, observe that, we have the following list of inequalities.

Also, since $\|\mathbf{h}_{1}\|\geq\gamma_{m-1}-\tau$,

Let us focus on $\kappa_{2}-\kappa_{1}$ and let $\hat{\alpha}=\frac{\alpha}{\|\mathbf{z}\|}$. We may write,

Further normalizing by $\|\mathbf{h}_{1}\|$, we find,

For $\hat{\kappa}(\hat{\alpha})$, we have the following result.

Let $\beta$ be same as in (7.4). Then, for $1\geq\hat{\alpha}\geq\beta$, we have that $\hat{\kappa}(\hat{\alpha})\geq\sqrt{\frac{1-\beta}{2}}(\hat{\alpha}-\beta)$.

Observe that $\hat{\kappa}(\beta)=0$. Using $0\leq\beta<1$ and differentiating with respect to $\hat{\alpha}$, for $\hat{\alpha}\geq\beta$,

Since the second derivative is nonpositive, this means $\hat{\kappa}^{\prime}(\hat{\alpha})$ is minimized at $\hat{\alpha}=1$ over the region $\beta\leq\hat{\alpha}\leq 1$. Consequently, for $1\geq\hat{\alpha}\geq\beta$, we have,

To find $\hat{\kappa}^{\prime}(1)$, set $\hat{\alpha}=1$ in (7.6),

Here we used the fact that $\sqrt{1+\beta}-\frac{\beta}{\sqrt{2}}$ is minimized at $\beta=1$ over $0\leq\beta\leq 1$, which can be verified by differentiating. Substituting this in (7.7), we find the desired result. ∎

Now, applying Lemma 6 and using (7.5), we have,

Finally, to bound $\kappa_{3}$, for $1\geq\hat{\alpha}\geq\beta$, we use $0\leq\|\mathbf{z}\|-\alpha\beta\leq\|\mathbf{z}\|(1-\beta^{2})$. This gives

Here, the nonnegativity of the right-hand side is equivalent to,

Differentiating the $(1+\beta)(1-\beta^{2})$ term, we find that, it is maximized at $\beta=\frac{1}{3}$ and is upper bounded by $\frac{32}{27}\leq 1.28$. In summary, we have shown that, with probability $1-\frac{5}{2}\exp(-\frac{t^{2}}{26})$ (7.3) hold with $\tau=\frac{t}{3.6}$, and we have, $\kappa_{2}-\kappa_{1}-\kappa_{3}\geq 0$; which also implies nonnegativity of right-hand side of (7.2). Now, using (7.1), we find the desired result.

References