Sketched least squares and subspace embeddings

Regard $H$ as a complex Hermitian matrix when $\mathbb{K}=\mathbb{R}$. By [F1], it has an orthonormal eigenbasis over $\mathbb{C}$; every eigenvalue is real because $Hv=\lambda v$ and $H=H^{\ast }$ give $\lambda \mathrm{\parallel }v{\mathrm{\parallel }}_2^2=v^{\ast }Hv=\overline{v^{\ast }Hv}=\bar{\lambda }\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$. Choose a unit eigenvector $z$ for an eigenvalue $\lambda$ of largest absolute value. The diagonalization shows $\mathrm{\parallel }H{\mathrm{\parallel }}_2=\mathrm{\mid }\lambda \mathrm{\mid }$ over $\mathbb{C}$. If $\mathbb{K}=\mathbb{C}$, set $u=z$. If $\mathbb{K}=\mathbb{R}$, write $z=a+ib$; since $H$ and $\lambda$ are real, $Ha=\lambda a$ and $Hb=\lambda b$, and at least one of $a,b$ is nonzero. Normalize a nonzero part as $u$. The same diagonalization bounds the real operator norm by $\mathrm{\mid }\lambda \mathrm{\mid }$, while $u$ attains that bound, so $\mathrm{\mid }{u}^{\ast }Hu\mathrm{\mid }=\mathrm{\mid }\lambda \mathrm{\mid }=\mathrm{\parallel }H{\mathrm{\parallel }}_2$ over either field.

Apply [F2] in real dimension $q=d$ when $\mathbb{K}=\mathbb{R}$, and $q=2d$ when $\mathbb{K}=\mathbb{C}$, to obtain the stated net-size bound and a $v\in \mathcal{N}$ with $\mathrm{\parallel }u-v{\mathrm{\parallel }}_2\le 1\mathrm{/}4$.

Since $H=H^{\ast }$ and $u,v$ are unit vectors, $\mathrm{\mid }{u}^{\ast }Hu-v^{\ast }Hv\mathrm{\mid }\le \mathrm{\mid }(u-v{)}^{\ast }Hu\mathrm{\mid }+\mathrm{\mid }{v}^{\ast }H(u-v)\mathrm{\mid }\le 2\mathrm{\parallel }u-v{\mathrm{\parallel }}_2\mathrm{\parallel }H{\mathrm{\parallel }}_2\le \mathrm{\parallel }H{\mathrm{\parallel }}_2\mathrm{/}2$, using [F3] and the definition of operator norm. Therefore $\mathrm{\mid }{v}^{\ast }Hv\mathrm{\mid }\ge \mathrm{\mid }{u}^{\ast }Hu\mathrm{\mid }-\mathrm{\parallel }H{\mathrm{\parallel }}_2\mathrm{/}2=\mathrm{\parallel }H{\mathrm{\parallel }}_2\mathrm{/}2$, proving the claimed bound.

Let $Q^{\mathrm{\prime }}$ be another orthonormal basis matrix of $U$, and set $W=Q^{\ast }{Q}^{\mathrm{\prime }}$. Since each column of $Q^{\mathrm{\prime }}$ lies in $U=\mathrm{Ran}(Q)$, the orthogonal projection $Q{Q}^{\ast }$ fixes it, so $Q^{\mathrm{\prime }}=Q{Q}^{\ast }{Q}^{\mathrm{\prime }}=QW$. Thus $W^{\ast }W=Q^{\mathrm{\prime }\ast }Q{Q}^{\ast }{Q}^{\mathrm{\prime }}=Q^{\mathrm{\prime }\ast }{Q}^{\mathrm{\prime }}=I_d$. The square matrix $W$ is unitary, and right multiplication by $W$ preserves the Euclidean norm of every row; hence $\mathrm{\parallel }{e}_i^{\ast }{Q}^{\mathrm{\prime }}{\mathrm{\parallel }}_2^2=\mathrm{\parallel }{e}_i^{\ast }Q{\mathrm{\parallel }}_2^2$ for every $i$.

Writing $q_j$ for column $j$ of $Q$, finite-sum reordering gives ${\sum }_{i=0}^{n-1}{\mathrm{\ell }}_i={\sum }_i{\sum }_{j=0}^{d-1}\mathrm{\mid }{Q}_{ij}{\mathrm{\mid }}^2={\sum }_j\mathrm{\parallel }{q}_j{\mathrm{\parallel }}_2^2=d$, because every column is a unit vector.

Put $P=Q{Q}^{\ast }$. Then $P=P^{\ast }$ and $P^2=P$ by [F2], so $e_i=P{e}_i+(I-P)e_i$ is an orthogonal decomposition. Also ${\mathrm{\ell }}_i=\mathrm{\parallel }{Q}^{\ast }{e}_i{\mathrm{\parallel }}_2^2=\mathrm{\parallel }Q{Q}^{\ast }{e}_i{\mathrm{\parallel }}_2^2=\mathrm{\parallel }P{e}_i{\mathrm{\parallel }}_2^2$, using $Q^{\ast }Q=I_d$. Therefore $0\le {\mathrm{\ell }}_i\le \mathrm{\parallel }{e}_i{\mathrm{\parallel }}_2^2=1$, and ${\mathrm{\ell }}_i=0$ exactly when $Q^{\ast }{e}_i=0$, which is exactly when row $i$ of $Q$ is zero.

Set $C=SA$ and $c=Sb$. By [F1], the converged call uses threshold zero and returns $\widehat{x}=C_0^{+}c$, where $C_0$ retains exactly the singular values of $C$ that are strictly positive.

In an exact SVD $C=U\mathrm{\Sigma }{V}^{\ast }$, zero singular values contribute zero terms and every positive singular value is retained at threshold zero. Thus $C_0=U\mathrm{\Sigma }{V}^{\ast }=C$, including the rank-zero case.

Apply [F2] to the truncated matrix $C_0$. It says that $C_0^{+}c$ is its unique minimum-norm least-squares solution. By step 2.1, $C_0=C$, so $\widehat{x}$ is the unique minimum-norm minimizer of $\mathrm{\parallel }Cx-c{\mathrm{\parallel }}_2=\mathrm{\parallel }SAx-Sb{\mathrm{\parallel }}_2$; the zero-threshold rank count is precisely the number of positive singular values of $C$, hence $\mathrm{rank}(C)$.

If $y\in {\mathbb{K}}^d$ is nonzero, full column rank gives $Ay\mathrm{\ne }0$; then [F1] gives $\mathrm{\parallel }SAy{\mathrm{\parallel }}_2^2\ge (1-\epsilon )\mathrm{\parallel }Ay{\mathrm{\parallel }}_2^2>0$. Thus $SA$ has full column rank. The reduced QR factorization in [F2] exists. If $Rv=0$, then $SAv=QRv=0$; injectivity of $SA$ forces $v=0$, so $R$ is nonsingular and $P_S=R^{-1}$ is defined.

For any $y\in {\mathbb{K}}^d$, $SA{P}_{S}y=QR{R}^{-1}y=Qy$, so $\mathrm{\parallel }SA{P}_{S}y{\mathrm{\parallel }}_2^2=\mathrm{\parallel }Qy{\mathrm{\parallel }}_2^2=\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$ by [F2]. Since $A{P}_{S}y\in \mathrm{Ran}(A)$, [F1] yields $(1-\epsilon )\mathrm{\parallel }A{P}_{S}y{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }y{\mathrm{\parallel }}_2^2\le (1+\epsilon )\mathrm{\parallel }A{P}_{S}y{\mathrm{\parallel }}_2^2$.

For every unit $y$, step 2.1 implies $1\mathrm{/}\sqrt{1+\epsilon }\le \mathrm{\parallel }A{P}_{S}y{\mathrm{\parallel }}_2\le 1\mathrm{/}\sqrt{1-\epsilon }$. By [F3], the minimum and maximum of these values over the unit sphere are ${\sigma }_{\min }(A{P}_S)$ and ${\sigma }_{\max }(A{P}_S)$, respectively. This proves both singular-value bounds.

The lower bound in step 3.1 is positive, so the ratio defining ${\kappa }_2$ is valid. Dividing the upper singular-value bound by the lower one gives ${\kappa }_2(A{P}_S)\le \sqrt{(1+\epsilon )\mathrm{/}(1-\epsilon )}$.

For real $Z$ and $\theta <1\mathrm{/}2$, put $c=1-2\theta >0$. By [F3], the substitution $u=\sqrt{c}x$ gives $\mathbb{E}{e}^{\theta Z^2}=c^{-1\mathrm{/}2}(2\pi {)}^{-1\mathrm{/}2}{\int }_{\mathbb{R}}{e}^{-u^2\mathrm{/}2}du=c^{-1\mathrm{/}2}$. The prefactored integral is one since [F1] is a probability density. For normalized complex $G$ and $\theta <1$, put $d=1-\theta >0$. On $\mathbb{C}\simeq {\mathbb{R}}^2$, the map $u=\sqrt{d}z$ has real determinant $d$, so [F3] gives $\mathbb{E}{e}^{\theta \mathrm{\mid }G{\mathrm{\mid }}^2}=d^{-1}{\pi }^{-1}{\int }_{{\mathbb{R}}^2}{e}^{-\mathrm{\mid }u{\mathrm{\mid }}^2}du=d^{-1}$. Again the prefactored integral is one by the normalized density [F1]. These identities include the finite integrability ranges needed below.

For the real case, [F4] applied to $X=e^{\lambda {\sum }_j{g}_j^2}$ at the positive threshold $a=e^{\lambda m(1+t)}$, with $\lambda =t\mathrm{/}(2(1+t))$, and independence together with the first formula of step 1.1 give $\mathrm{Pr}\{m^{-1}{\sum }_j{g}_j^2\ge 1+t\}\le \exp [-\frac{m}{2}(t-\log (1+t))]$. For the complex case use $X=e^{\lambda {\sum }_j\mathrm{\mid }{g}_j{\mathrm{\mid }}^2}$, the same threshold, $\lambda =t\mathrm{/}(1+t)$, and the second formula to obtain the stronger bound $\exp [-m(t-\log (1+t))]$. Both positive parameters lie in the finite mgf ranges of step 1.1. By [F5], $t-\log (1+t)={\int }_0^{t}u\mathrm{/}(1+u)du\ge t^2\mathrm{/}4$, so both upper tails are at most $e^{-m{t}^2\mathrm{/}8}$.

For the real lower tail, apply [F4] to $X=e^{-\lambda {\sum }_j{g}_j^2}$ at threshold $a=e^{-\lambda m(1-t)}>0$ with $\lambda =t\mathrm{/}(2(1-t))$; for the complex lower tail use $X=e^{-\lambda {\sum }_j\mathrm{\mid }{g}_j{\mathrm{\mid }}^2}$, the same threshold, and $\lambda =t\mathrm{/}(1-t)$. The event $X\ge a$ is precisely the lower-tail event because the exponential is decreasing in the squared norm sum. The mgf arguments $-\lambda$ lie in the finite ranges of step 1.1, and independence again factors the expectations. Step 1.1 gives respective bounds $\exp [-\frac{m}{2}(-t-\log (1-t))]$ and $\exp [-m(-t-\log (1-t))]$. By [F5], $-t-\log (1-t)={\int }_0^{t}u\mathrm{/}(1-u)du\ge t^2\mathrm{/}2$, so each is at most $e^{-m{t}^2\mathrm{/}8}$.

The event in the Statement is the union of the upper and lower tail events bounded in steps 2.1 and 2.2. The finite union bound [F6] therefore gives the claimed sum bound.

By [F3], choose an original least-squares minimizer $x_{\ast }\in {\mathbb{K}}^p$, and write $r_{\ast }=A{x}_{\ast }-b$, $\widehat{r}=A\widehat{x}-b$.

For every $x\in {\mathbb{K}}^p$, both $Ax$ and $b$ belong to $U$, so their difference $Ax-b$ belongs to $U$. In particular [F1] applies to $\widehat{r}$ and $r_{\ast }$.

By [F2], $\widehat{x}$ minimizes the sketched residual, so $\mathrm{\parallel }S\widehat{r}{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }S{r}_{\ast }{\mathrm{\parallel }}_2^2$; squaring preserves order because both residual norms are nonnegative.

The lower inequality in [F1] gives $(1-\epsilon )\mathrm{\parallel }\widehat{r}{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }S\widehat{r}{\mathrm{\parallel }}_2^2$.

The upper inequality in [F1] gives $\mathrm{\parallel }S{r}_{\ast }{\mathrm{\parallel }}_2^2\le (1+\epsilon )\mathrm{\parallel }{r}_{\ast }{\mathrm{\parallel }}_2^2$.

Combining steps 3.1, 2.2 and 3.2 and dividing by $1-\epsilon >0$ proves the claimed estimate, since $x_{\ast }$ is an original minimizer by step 1.1.

Choose an orthonormal basis matrix $Q\in {\mathbb{K}}^{n\times d}$ for $U$, and let $\mathcal{N}$ be a $1\mathrm{/}4$-net of its unit sphere with $\mathrm{\mid }\mathcal{N}\mathrm{\mid }\le 9^{2d}$, which covers the real case too. For each fixed $v\in \mathcal{N}$, $Qv$ is a unit vector. Extend $Qv$ to an orthonormal basis of ${\mathbb{K}}^n$ by applying [F4] to its orthogonal complement; [F3] then shows that $GQv$ has $m$ independent standard Gaussian coordinates.

For each fixed $v\in \mathcal{N}$, apply [F5] with $t=\epsilon \mathrm{/}2$ to obtain $\mathrm{Pr}\{\mathrm{\mid }\mathrm{\parallel }SQv{\mathrm{\parallel }}_2^2-1\mathrm{\mid }\ge \epsilon \mathrm{/}2\}\le 2e^{-m{\epsilon }^2\mathrm{/}32}$. The finite union bound [F9] for the fixed finite net gives $\mathrm{Pr}\{\mathrm{\exists }v\in \mathcal{N}:\mathrm{\mid }\mathrm{\parallel }SQv{\mathrm{\parallel }}_2^2-1\mathrm{\mid }\ge \epsilon \mathrm{/}2\}\le 29^{2d}{e}^{-m{\epsilon }^2\mathrm{/}32}\le 2e^{2d\log 9-6d-6\log (1\mathrm{/}\delta )}\le \delta$. Here the sample-size hypothesis gives $m{\epsilon }^2\mathrm{/}32\ge 6(d+\log (1\mathrm{/}\delta ))$, and $\log 2+2d\log 9<6d$ for $d\ge 1$.

On the complementary event, put $H=Q^{\ast }{S}^{\ast }SQ-I_d$. This is Hermitian and $\mathrm{\mid }{v}^{\ast }Hv\mathrm{\mid }=\mathrm{\mid }\mathrm{\parallel }SQv{\mathrm{\parallel }}_2^2-1\mathrm{\mid }<\epsilon \mathrm{/}2$ for every $v\in \mathcal{N}$. By [F6], $\mathrm{\parallel }H{\mathrm{\parallel }}_2\le \epsilon$. For nonzero $y$, [F7] and [F8] give $\mathrm{\mid }{y}^{\ast }Hy\mathrm{\mid }\le \mathrm{\parallel }y{\mathrm{\parallel }}_2\mathrm{\parallel }Hy{\mathrm{\parallel }}_2\le \mathrm{\parallel }H{\mathrm{\parallel }}_2\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$; the zero vector satisfies the same inequality. Therefore $(1-\epsilon )\mathrm{\parallel }y{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }SQy{\mathrm{\parallel }}_2^2\le (1+\epsilon )\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$. Since $Q$ is an isometry onto $U$, [F1] identifies this as the required embedding inequality for every $x=Qy\in U$.

Write $z_i=Q^{\ast }{e}_i\in {\mathbb{K}}^d$, so $\mathrm{\parallel }{z}_i{\mathrm{\parallel }}_2^2={\mathrm{\ell }}_i$. For draw $j$, let $J_j$ be its sampled index and define $Y_j=z_{J_j}{z}_{J_j}^{\ast }\mathrm{/}{\pi }_{J_j}$. By [F2], the $Y_j$ are independent and $\mathbb{E}{Y}_j={\sum }_{i:{\pi }_i>0}{z}_i{z}_i^{\ast }=Q^{\ast }Q=I_d$; terms with ${\pi }_i=0$ have $z_i=0$ by [F1] and contribute zero.

Put $R=d\mathrm{/}\beta \ge 1$ and $B_j=Y_j-I_d$. The rank-one identity $(z_i{z}_i^{\ast }{)}^2={\mathrm{\ell }}_i{z}_i{z}_i^{\ast }$ and ${\pi }_i\ge \beta {\mathrm{\ell }}_i\mathrm{/}d$ give $\mathrm{\parallel }{Y}_j{\mathrm{\parallel }}_2={\mathrm{\ell }}_{J_j}\mathrm{/}{\pi }_{J_j}\le R$ and $Y_j^2⪯R{Y}_j$. Thus $\mathrm{\parallel }{B}_j{\mathrm{\parallel }}_2\le \max (1,R-1)\le R$, $\mathbb{E}{B}_j=0$, and $0⪯\mathbb{E}{B}_j^2=\mathbb{E}{Y}_j^2-I_d⪯(R-1)I_d⪯R{I}_d$. Hence [F3] applies with both bounds equal to $R$.

Set $a=\log (2d\mathrm{/}\delta )$. By [F3], $\mathrm{Pr}\{\mathrm{\parallel }{\sum }_{j=1}^m{B}_j{\mathrm{\parallel }}_2>\sqrt{2mRa}+2Ra\mathrm{/}3\}\le 2d{e}^{-a}=\delta$. Under the first sample-size condition, $m{\epsilon }^2\ge 8Ra$, so $\sqrt{2mRa}\le m\epsilon \mathrm{/}2$. Also $m\epsilon \mathrm{/}2\ge 4Ra\mathrm{/}\epsilon \ge 2Ra\mathrm{/}3$, since $0<\epsilon <1$. Thus the Bernstein threshold is at most $m\epsilon$.

From the sampled-row definition in [F2], $Q^{\ast }{S}^{\ast }SQ=m^{-1}{\sum }_j{Y}_j$, so $Q^{\ast }{S}^{\ast }SQ-I_d=m^{-1}{\sum }_j{B}_j$. Step 2.1 therefore proves $\mathrm{\parallel }{Q}^{\ast }{S}^{\ast }SQ-I_d{\mathrm{\parallel }}_2\le \epsilon$ with probability at least $1-\delta$. For nonzero $y$, [F5] and [F6] imply $\mathrm{\mid }{y}^{\ast }(Q^{\ast }{S}^{\ast }SQ-I_d)y\mathrm{\mid }\le \mathrm{\parallel }y{\mathrm{\parallel }}_2\mathrm{\parallel }(Q^{\ast }{S}^{\ast }SQ-I_d)y{\mathrm{\parallel }}_2\le \epsilon \mathrm{\parallel }y{\mathrm{\parallel }}_2^2$; the same holds for zero $y$. Thus $(1-\epsilon )\mathrm{\parallel }y{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }SQy{\mathrm{\parallel }}_2^2\le (1+\epsilon )\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$, and because $Q$ is an isometry onto its range, this is the embedding property in [F4].

If $0<\delta \le 1\mathrm{/}2$ and $d\ge 1$, then $d\mathrm{/}\delta \ge 2$, hence $\log (2d\mathrm{/}\delta )=\log (d\mathrm{/}\delta )+\log 2\le 2\log (d\mathrm{/}\delta )$. Therefore the second stated sample-size condition implies the first. For any rank-$d$ matrix $A$, its range is $\mathrm{Ran}(Q)$, so the same embedding statement applies to $A$'s column space.