OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings

Introduction

There has been much recent work on applications of dimensionality reduction to handling large datasets. Typically special features of the data such as low “intrinsic” dimensionality, or sparsity, are exploited to reduce the volume of data before processing, thus speeding up analysis time. One success story of this approach is the applications of fast algorithms for the Johnson-Lindenstrauss lemma [JL84], which allows one to reduce the dimension of a set of vectors while preserving all pairwise distances. There have been two popular lines of work in this area: one focusing on fast embeddings for all vectors [AC09, AL09, AL11, HV11, KMR12, KW11, Vyb11], and one focusing on fast embeddings specifically for sparse vectors [Ach03, BOR10, DKS10, KN10, KN12].

In this work we focus on the problem of constructing an oblivious subspace embedding (OSE) [Sar06] and on applications of these embeddings. Roughly speaking, the problem is to design a data-independent distribution over linear mappings such that when data come from an unknown low-dimensional subspace, they are reduced to roughly their true dimension while their structure (all distances in the subspace in this case) is preserved at the same time. It can be seen as a continuation of the approach based on the Johnson-Lindenstrauss lemma to subspaces. Here we focus on the setting of sparse inputs, where it is important that the algorithms take time proportional to the input sparsity. These embeddings have found applications in numerical linear algebra problems such as least squares regression, low rank approximation, and approximating leverage scores [CW09, CW12, DMIMW12, NDT09, Sar06, Tro11]. We refer the interested reader to the surveys [HMT11, Mah11] for an overview of this area.

Here $n,d,\varepsilon,\delta$ are given parameters of the problem and we would like $m$ as small as possible.

The $O(nd\log n)$ running time of the above scheme to compute $\Pi A$ seems almost linear, and thus nearly optimal, since the input size is already $nd$ to describe $A$. While this is true for dense $A$, in many practical instances one often expects the input matrix $A$ to be sparse, in which case linear time in the input description actually means $O(\operatornamewithlimits{nnz}(A))$, where $\operatornamewithlimits{nnz}(\cdot)$ is the number of non-zero entries. For example consider the case of $A$ being the Netflix matrix, where $A_{i,j}$ is user $i$’s score for movie $j$: $A$ is very sparse since most users do not watch, let alone score, most movies [ZWSP08].

In the following paragraph we let $S_{\Pi}$ be the space required to store $\Pi$ implicitly (e.g. store the seed to some hash function that specifies $\Pi$). We let $t_{c}$ be the running time required by an algorithm which, given a column index and the length-$S_{\Pi}$ seed specifying $\Pi$, returns the list of all non-zeroes in that column in $\Pi$.

1 Problem Statements and Bounds

We now formally define all numerical linear algebra problems we consider. Plugging our new OSE’s into previous algorithms for the above problems yields the bounds in Figure 1; the value $r$ used in bounds denotes $\operatorname{rank}(A)$.

Least Squares Regression:

Low Rank Approximation:

2 Our Construction and Techniques

Bounding this latter quantity is a simple calculation and fits in under a page (Theorem 3).

The two constructions with smaller $m\approx d/\varepsilon^{2}$ are the sparse Johnson-Lindenstrauss matrices of [KN12]. In particular, the only properties we need from our OSE in our analyses are the following. Let each matrix in the support of the OSE have entries in $\{0,1/\sqrt{s},-1/\sqrt{s}\}$. For a randomly drawn $\Pi$, let $\delta_{i,j}$ be an indicator random variable for the event $\Pi_{i,j}\neq 0$, and write $\Pi_{i,j}=\delta_{i,j}\sigma_{i,j}/\sqrt{s}$, where the $\sigma_{i,j}$ are random signs. Then the properties we need are

For any $j\in[n]$, $\sum_{i=1}^{m}\delta_{i,j}=s$ with probability $1$.

The second property says the $\delta_{i,j}$ are negatively correlated. We call any matrix drawn from an OSE with the above properties an oblivious sparse norm-approximating projection (OSNAP).

The work of [KN12] gave two OSNAP distributions, either of which suffice for our current OSE problem. In the first construction, each column is chosen to have exactly $s$ non-zero entries in random locations, each equal to $\pm 1/\sqrt{s}$ uniformly at random. For our purposes the signs $\sigma_{i,j}$ need only be $O(\log d)$-wise independent, and each column can be specified by a $O(\log d)$-wise independent permutation, and the seeds specifying the permutations in different columns need only be $O(\log d)$-wise independent. In the second construction we pick hash functions $h:[d]\times[s]\rightarrow[m/s]$, $\sigma:[d]\times[s]\rightarrow\{-1,1\}$, both $O(\log d)$-wise independent, and thus each representable using $O(\log d\log nd)$ random bits. For each $(i,j)\in[d]\times[s]$ we set $\Pi_{(j-1)s+h(i,j),i}=\sigma(i,j)/\sqrt{s}$, and all other entries in $\Pi$ are set to zero. Note also that the TZ sketch is itself an OSNAP with $s=1$.

Our approach follows the classical moment method in random matrix theory; see [Tao12, Section 2] or [Ver12] introductions to this area. In particular, our approach is inspired by one taken by Bai and Yin [BY93], who in our notation were concerned with the case $n=d$, $U=I$, $\Pi$ dense. Most of the complications in our proof arise because $U$ is not the identity matrix, so that rows of $U$ are not orthogonal. For example, in the case of $U$ having orthogonal rows all graphs $G$ in the last paragraph have no edges other than self-loops and are trivial to analyze.

Analysis

Let $M,H,P$ be $n\times n$ Hermitian matrices where $M$ has eigenvalues $\mu_{1}\geq\ldots\geq\mu_{n}$, $H$ has eigenvalues $\nu_{1}\geq\ldots\geq\nu_{n}$, and $P$ has eigenvalues $\rho_{1}\geq\ldots\geq\rho_{n}$. Then $\forall\ 1\leq i\leq n$, it holds that $\nu_{i}+\rho_{n}\leq\mu_{i}\leq\nu_{i}+\rho_{1}$.

Let $S=(\Pi U)^{*}\Pi U$. Letting $I$ be the $d\times d$ identity matrix, Weyl’s inequality with $M=S$, $H=(1+\varepsilon^{2})I$, and $P=S-(1+\varepsilon^{2})I$ implies that all the eigenvalues of $S$ lie in the range $[1+\varepsilon^{2}+\lambda_{min}(P),1+\varepsilon^{2}+\lambda_{max}(P)]\subseteq[1+\varepsilon^{2}-\|P\|,1+\varepsilon^{2}+\|P\|]$, where $\lambda_{min}(M)$ (resp. $\lambda_{max}(M)$) is the smallest (resp. largest) eigenvalue of $M$. Since $\|P\|\leq\varepsilon^{2}+\|S-I\|$, it thus suffices to show

since $\|P\|\leq 2\varepsilon$ implies that all eigenvalues of $S$ lie in $[(1-\varepsilon)^{2},(1+\varepsilon)^{2}]$.

Before proceeding with our proofs below, observe that for all $k,k^{\prime}$

Noting $\langle u^{k},u^{k}\rangle=\|u^{k}\|^{2}=1$ and $\langle u^{k},u^{k^{\prime}}\rangle=0$ for $k\neq k^{\prime}$, we have for all $k,k^{\prime}$

For $\Pi$ an OSNAP with $s=1$ and $\varepsilon\in(0,1)$, with probability at least $1-\delta$ all singular values of $\Pi U$ are $1\pm\varepsilon$ as long as $m\geq\delta^{-1}(d^{2}+d)/(2\varepsilon-\varepsilon^{2})^{2}$, $\sigma$ is $4$-wise independent, and $h$ is pairwise independent.

Noting $0=\langle u^{k},u^{k^{\prime}}\rangle^{2}=\sum_{k=1}^{n}(u^{k}_{i})^{2}(u^{k^{\prime}}_{i})^{2}+\sum_{i\neq j}u^{k}_{i}u^{k^{\prime}}_{i}u^{k}_{j}u^{k^{\prime}}_{j}$ we have that $\sum_{i\neq j}u^{k}_{i}u^{k^{\prime}}_{i}u^{k}_{j}u^{k^{\prime}}_{j}\leq 0$, so

Before proving the next theorem, it is helpful to state a few facts that we will repeatedly use. Recall that $u^{i}$ denotes the $i$th column of $U$, and we will let $u_{i}$ denote the $i$th row of $U$.

and this inner product is $1$ for $i=j$ and otherwise. $\blacksquare$

A multigraph $G$ has $k$ edge-disjoint spanning trees iff

for every partition $P$ of the vertex set of $G$, where $E_{P}(G)$ is the set of edges of $G$ crossing between two different partitions in $P$.

The following corollary is standard, and we will later only need it for the case $k=2$.

Let $G$ be a multigraph formed by removing at most $k$ edges from a multigraph $G^{\prime}$ that has edge-connectivity at least $2k$. Then $G$ must have at least $k$ edge-disjoint spanning trees.

Proof. For any partition $P$ of the vertex set, each partition must have at least $2k$ edges leaving it in $G^{\prime}$. Thus the number of edges crossing partitions must be at least $k|P|$ in $G^{\prime}$, and thus at least $k|P|-k$ in $G$. Theorem 6 thus implies that $G$ has $k$ edge-disjoint spanning trees. $\blacksquare$

Proof. We have $\sup_{\|x\|,\|y\|=1}x^{*}By\leq\|B\|$ since $x^{*}By\leq\|x\|\cdot\|B\|\cdot\|y\|$. To show that unit norm $x,y$ exist which achieve $\|B\|$, let $B=U\Sigma V^{*}$ be the singular value decomposition of $B$. That is, $U,V$ are unitary and $\Sigma$ is diagonal with entries $\sigma_{1}\geq\sigma_{2}\geq\ldots\sigma_{d}\geq 0$ so that $\|B\|=\sigma_{1}$. We can then achieve $x^{*}By=\sigma_{1}$ by letting $x$ be the first column of $U$ and $y$ be the first column of $V$. $\blacksquare$

For $\Pi$ an OSNAP with $s=\Theta(\log^{3}(d/\delta)/\varepsilon)$ and $\varepsilon\in(0,1)$, with probability at least $1-\delta$, all singular values of $\Pi U$ are $1\pm\varepsilon$ as long as $m=\Omega(d\log^{8}(d/\delta)/\varepsilon^{2})$ and $\sigma,h$ are $\Omega(\log(d/\delta))$-wise independent.

Proof. We will again show Eq. (2). Recall that by Eq. (1) we have

Now we make some observations. Due to the random signs $\sigma_{r,i}$, a monomial $\psi$ has expectation zero unless every bond in $\mathop{MR}(G)$ has even multiplicity, in which case the product of random signs in $\psi$ is $1$. Also, note the expectation of the product of the $\delta_{r,i}$ terms in $\psi$ is at most $(s/m)^{b}$ by OSNAP properties. Thus letting $\mathcal{G}$ be the set of all such graphs $G$ with even bond multiplicity in $\mathop{MR}(G)$ that arise from some monomial $\psi$ appearing in Eq. (6), we have

Before continuing further it will be convenient to introduce a notion we will use in our analysis called a generalized dot product multigraph. Such a graph $\widehat{G}$ is just as in the case of a dot product multigraph, except that each edge $e=(i,j)$ is associated with some matrix $M_{e}$. We call $M_{e}$ the edge-matrix of $e$. Also since $\widehat{G}$ is undirected, we can think of an edge $e=(i,j)$ with edge-matrix $M_{e}$ also as an edge $(j,i)$, in which case we say its associated edge-matrix is $M_{e}^{*}$. We then associate with $\widehat{G}$ the product

Note that a dot product multigraph is simply a generalized dot product multigraph in which $M_{e}=I$ for all $e$. Also, in such a generalized dot product multigraph, we treat multiedges as representing the same bond iff the associated edge-matrices are also equal (in general multiedges may have different edge-matrices).

Let $H$ be a connected generalized dot product multigraph on vertex set $[N]$ with $E(H)\neq\emptyset$ and where every bond has even multiplicity. Also suppose that for all $e\in E(H)$, $\|M_{e}\|\leq 1$. Define

where $v_{a_{i}}=u_{a_{i}}$ for $i\neq 1$, and $v_{a_{1}}$ equals some fixed vector $c$ with $\|c\|\leq 1$. Then $f(H)\leq\|c\|^{2}$.

Proof. Let $\pi$ be some permutation of $\{2,\ldots,N\}$. For a bond $q=(i,j)\in B(H)$, let $2\alpha_{q}$ denote the multiplicity of $q$ in $H$. Then by ordering the assignments of the $a_{t}$ in the summation

according to $\pi$, we obtain the exactly equal expression

Here we have taken the product over $t\leq\pi^{-1}(j)$ as opposed to $t<\pi^{-1}(j)$ since there may be self-loops. By Lemma 5 and the fact that $\|c\|\leq 1$ we have that for any $i,j$, $\langle v_{i},v_{j}\rangle^{2}\leq\|v_{i}\|^{2}\cdot\|v_{j}\|^{2}\leq 1$, so we obtain an upper bound on Eq. (8) by replacing each $\langle v_{a_{\pi(t)}},v_{a_{j}}\rangle^{2\alpha_{v}}$ term with $\langle v_{a_{\pi(t)}},v_{a_{j}}\rangle^{2}$. We can thus obtain the sum

which upper bounds Eq. (8). Now note for $2\leq t\leq N$ that for any nonnegative integer $\beta_{t}$ and for $\{q\in B(H):q=(\pi(t),j),t<\pi^{-1}(j)\}$ non-empty (note the strict inequality $t<\pi^{-1}(j)$),

where Eq. (10) used Lemma 5, Eq. (11) used Lemma 4, and Eq. (12) used that $\|M_{q}\|\leq 1$. Now consider processing the alternating sum-product in Eq. (9) from right to left. We say that a bond $(i,j)\in B(H)$ is assigned to $i$ if $\pi^{-1}(i)<\pi^{-1}(j)$. When arriving at the $t$th sum-product and using the upper bound Eq. (11) on the previous $t-1$ sum-products, we will have a sum over $\|v_{a_{\pi(t)}}\|^{2}$ raised to some nonnegative power (specifically the number of bonds incident upon $\pi(t)$ but not assigned to $\pi(t)$, plus one if $\pi(t)$ has a self-loop) multiplied by a product of $\langle v_{a_{\pi(t)}},v_{a_{j}}\rangle^{2}$ over all bonds $(\pi(t),j)$ assigned to $\pi(t)$. There are two cases. In the first case $\pi(t)$ has no bonds assigned to it. We will ignore this case since we will show that we can choose $\pi$ to avoid it.

The other case is that $\pi(t)$ has at least one bond assigned to it. In this case we are in the scenario of Eq. (11) and thus summing over $a_{\pi(t)}$ yields a non-empty product of $\|v_{a_{j}}\|^{2}$ for the $j$ for which $(\pi(t),j)$ is a bond assigned to $\pi(t)$. Thus in our final sum, as long as we choose $\pi$ to avoid the first case, we are left with an upper bound of $\|c\|$ raised to some power equal to the edge-degree of vertex $1$ in $H$, which is at least $2$. The lemma would then follow since $\|c\|^{j}\leq\|c\|^{2}$ for $j\geq 2$.

It now remains to show that we can choose $\pi$ to avoid the first case where some $t\in\{2,\ldots,N\}$ is such that $\pi(t)$ has no bonds assigned to it. Let $T$ be a spanning tree in $H$ rooted at vertex $1$. We then choose any $\pi$ with the property that for any $i<j$, $\pi(i)$ is not an ancestor of $\pi(j)$ in $T$. This can be achieved, for example, by assigning $\pi$ values in reverse breadth first search order. $\blacksquare$

Let $\widehat{G}$ be any dot product graph as in Eq. (7). Then

Proof. We first note that we have the inequality

We can view the sum over $t$ on the right hand side of the above as creating $t-1$ new dot product multigraphs, each with one fewer vertex where we eliminated vertex $y$ and associated it with vertex $t$ for some $t$, and for each edge $(y,a)$ we effectively replaced it with $(t,a)$. Also in first sum where we sum over all $n$ values of $a_{y}$, we have eliminated the constraints $a_{y}\neq a_{i}$ for $i\neq y$. By recursively applying this inequality to each of the resulting $t$ summations, we bound

by a sum of contributions from $y!$ dot product multigraphs where in none of these multigraphs do we have the constraint that $a_{i}\neq a_{j}$ for $i\neq j$. We will show that each one of these resulting multigraphs contributes at most $d^{y-w+1}$, from which the lemma follows.

Let $G^{\prime}$ be one of the dot product multigraphs at a leaf of the above recursion so that we now wish to bound

where $M_{e}=I$ for all $e$ for $G^{\prime}$. Before proceeding, we first claim that every connected component of $G^{\prime}$ is Eulerian. To see this, observe $G$ has an Eulerian tour, by following the edges of $G$ in increasing order of label, and thus all middle vertices have even edge-degree in $G$. However they also have even edge-degree in $\mathop{MR}(G)$, and thus the edge-degree of a middle vertex in $\mathop{LM}(G)$ must be even as well. Thus, every vertex in $\widehat{G}$ has even edge-degree, and thus every vertex in each of the recursively created leaf graphs also has even edge-degree since at every step when we eliminate a vertex, some other vertex’s degree increases by the eliminated vertex’s degree which was even. Thus every connected component of $G^{\prime}$ is Eulerian as desired.

We now upper bound $F(G^{\prime})$. Let the connected components of $G^{\prime}$ be $C_{1},\ldots,C_{CC(G^{\prime})}$, where $CC(\cdot)$ counts connected components. An observation we repeatedly use later is that for any generalized dot product multigraph $H$ with components $C_{1},\ldots,C_{CC(H)}$,

We treat $G^{\prime}$ as a generalized dot product multigraph so that each edge $e$ has an associated matrix $M_{e}$ (though in fact $M_{e}=I$ for all $e$). Define an undirected multigraph to be good if all its connected components have two edge-disjoint spanning trees. We will show that $F(G^{\prime})\leq F(G^{\prime\prime})$ for some generalized dot product multigraph $G^{\prime\prime}$ that is good then will show $F(G^{\prime\prime})\leq d^{y-w+1}$. If $G^{\prime}$ itself is good then we can set $G^{\prime\prime}=G^{\prime}$. Otherwise, we will show $F(G^{\prime})=F(H_{0})=\ldots=F(H_{\tau})$ for smaller and smaller generalized dot product multigraphs $H_{t}$ (i.e. with successively fewer vertices) whilst maintaining the invariant that each $H_{t}$ has Eulerian connected components and has $\|M_{e}\|\leq 1$ for all $e$. We stop when some $H_{\tau}$ is good and we can set $G^{\prime\prime}=H_{\tau}$.

Let us now focus on constructing this sequence of $H_{t}$ in the case that $G^{\prime}$ is not good. Let $H_{0}=G^{\prime}$. Suppose we have constructed $H_{0},\ldots,H_{t-1}$ for $i\geq 1$ none of which are good, and now we want to construct $H_{t}$. Since $H_{t-1}$ is not good it cannot be $4$-edge-connected by Corollary 7, so there is some connected component $C_{j^{*}}$ of $H_{t-1}$ with some cut $S\subsetneq V(C_{j^{*}})$ with $2$ edges crossing the cut $(S,V(C_{j^{*}})\backslash S)$ (note that since $C_{j^{*}}$ is Eulerian, any cut has an even number of edges crossing it). Choose such an $S\subsetneq V(C_{j^{*}})$ with $|S|$ minimum amongst all such cuts. Let the two edges crossing the cut be $(g,h),(g^{\prime},h^{\prime})$ with $h,h^{\prime}\in S$ (note that it may be the case that $g=g^{\prime}$ and/or $h=h^{\prime}$). Note that $F(C_{j^{*}})$ equals the magnitude of

We define $H_{t}$ to be $H_{t-1}$ but where in the $j^{*}$th component we replace $C_{j^{*}}$ with $C_{j}^{*}(V(C_{j}^{*})\backslash S)$ and add an additional edge from $g$ to $g^{\prime}$ which we assign edge-matrix $M$. We thus have that $F(H_{t-1})=F(H_{t})$ by Eq. (14). Furthermore each component of $H_{t}$ is still Eulerian since every vertex in $H_{t-1}$ has either been eliminated, or its edge-degree has been preserved and thus all edge-degrees are even. It remains to show that $\|M\|\leq 1$.

We first claim that $C_{j^{*}}(S)$ has two edge-disjoint spanning trees. Define $C^{\prime}$ to be the graph $C_{j^{*}}(S)$ with an edge from $h$ to $h^{\prime}$ added. We show that $C^{\prime}(S)$ is $4$-edge-connected so that $C_{j^{*}}(S)$ has two edge-disjoint spanning trees by Corollary 7. Now to see this, consider some $S^{\prime}\subsetneq S$. Consider the cut $(S^{\prime},V(C^{\prime})\backslash S^{\prime})$. $C^{\prime}$ is Eulerian, so the number of edges crossing this cut is either $2$ or at least $4$. If it $2$, then since $|S^{\prime}|<|S|$ this is a contradiction since $S$ was chosen amongst such cuts to have $|S|$ minimum. Thus it is at least $4$, and we claim that the number of edges crossing the cut $(S^{\prime},S\backslash S^{\prime})$ in $C^{\prime}(S)$ must also be at least $4$. If not, then it is $2$ since $C^{\prime}(S)$ is Eulerian. However since the number of edges leaving $S^{\prime}$ in $C^{\prime}$ is at least $4$, it must then be that $h,h^{\prime}\in S^{\prime}$. But then the cut $(S\backslash S^{\prime},V(C^{\prime})\backslash(S\backslash S^{\prime}))$ has $2$ edges crossing it so that $S\backslash S^{\prime}$ is a smaller cut than $S$ with $2$ edges leaving it in $C^{\prime}$, violating the minimality of $|S|$, a contradiction. Thus $C^{\prime}(S)$ is $4$-edge-connected, implying $C_{j^{*}}(S)$ has two edge-disjoint spanning trees $T_{1},T_{2}$ as desired.

Now to show $\|M\|\leq 1$, by Fact 8 we have $\|M\|=\sup_{\|x\|,\|x^{\prime}\|=1}x^{*}Mx^{\prime}$. We have that

where Eq. (16) used the AM-GM inequality, and Eq. (17) used Lemma 10 (note the graph with vertex set $S\cup\{g^{\prime}\}$ and edge set $E(C_{j^{*}}(S))\backslash T_{1}\cup\{(g^{\prime},h^{\prime})\}$ is connected since $T_{2}\subseteq E(C_{j^{*}}(S))\backslash T_{1}$). Thus we have shown that $H_{t}$ satisfies the desired properties. Now notice that the sequence $H_{0},\ldots,H_{1},\ldots$ must eventually terminate since the number of vertices is strictly decreasing in this sequence and any Eulerian graph on $2$ vertices is good. Therefore we have that $H_{\tau}$ is eventually good for some $\tau>0$ and we can set $G^{\prime\prime}=H_{\tau}$.

It remains to show that for our final good $G^{\prime\prime}$ we have $F(G^{\prime\prime})\leq d^{y-w+1}$. We will show this in two parts by showing that both $CC(G^{\prime\prime})\leq d^{y-w+1}$ and $F(G^{\prime\prime})\leq d^{CC(G^{\prime\prime})}$. For the first claim, note that $CC(G^{\prime\prime})\leq CC(\widehat{G})$ since every $H_{t}$ has the same number of connected components as $G^{\prime}$, and $CC(G^{\prime})\leq CC(\widehat{G})$. This latter inequality holds since in each level of recursion used to eventually obtain $G^{\prime}$ from $\widehat{G}$, we repeatedly identified two vertices as equal and merged them, which can only decrease the number of connected components. Now, all middle vertices in $G$ lie in one connected component (since $G$ is connected) and $\mathop{MR}(G)$ has $w$ connected components. Thus the at least $w-1$ edges connecting these components in $G$ must come from $\mathop{LM}(G)$, implying that $\mathop{LM}(G)$ (and thus $\widehat{G}$) has at most $y-w+1$ connected components, which thus must also be true for $G^{\prime\prime}$ as argued above.

It only remains to show $F(G^{\prime\prime})\leq d^{CC(G^{\prime\prime})}$. Let $G^{\prime\prime}$ have connected components $C_{1},\ldots,C_{CC(G^{\prime\prime})}$ with each $C_{j}$ having $2$ edge-disjoint spanning trees $T^{j}_{1},T^{j}_{2}$. We then have

where Eq. (18) used the AM-GM inequality, and Eq. (19) used Lemma 10, which applies since $V(C_{t})$ with edge set $T^{t}_{1}$ is connected, and $V(C_{t})$ with edge set $E(C_{t})\backslash T^{t}_{1}$ is connected (since $T_{2}^{t}\subseteq E(C_{t})\backslash T^{t}_{1}$). $\blacksquare$

Let $\alpha,\gamma>0$ be arbitrary constants. For $\Pi$ an OSNAP with $s=\Theta(1/\varepsilon)$ and $\varepsilon\in(0,1)$, with probability at least $1-1/d^{\alpha}$, all singular values of $\Pi U$ are $1\pm\varepsilon$ for $m=\Omega(d^{1+\gamma}/\varepsilon^{2})$ and $\sigma,h$ being $\Omega(\log d)$-wise independent. The constants in the big-$\Theta$ and big-$\Omega$ depend on $\alpha,\gamma$.

Applications

We use the fact that many matrix problems have the same time complexity as matrix multiplication including computing the matrix inverse [BH74][Har08, Appendix A], and QR decomposition [Sch73]. In this paper we only consider the real RAM model and state the running time in terms of the number of field operations. The algorithms for solving linear systems, computing inverse, QR decomposition, and approximating SVD based on fast matrix multiplication can be implemented with precision comparable to that of conventional algorithms to achieve the same error bound (with a suitable notion of approximation/stability). We refer readers to [DDH07] for details. Notice that it is possible that both algorithms based on fast matrix multiplication and conventional counterparts are unstable, see e.g. [AV97] for an example of a pathological matrix with very high condition number.

In this section we describe some applications of our subspace embeddings to problems in numerical linear algebra. All applications follow from a straightforward replacement of previously used embeddings with our new ones as most proofs go through verbatim. In the statement of our bounds we implicitly assume $\operatornamewithlimits{nnz}(A)\geq n$, since otherwise fully zero rows of $A$ can be ignored without affecting the problem solution.

This section describes the application of our subspace embedding from Theorem 9 or Theorem 12 to approximating the leverage scores. Consider a matrix $A$ of size $n\times d$ and rank $r$. Let $U$ be a $n\times r$ matrix whose columns form an orthonormal basis of the column space of $A$. The leverage scores of $A$ are the squared lengths of the rows of $U$. The algorithm for approximating the leverage scores and the analysis are the same as those of [CW12], which itself uses essentially the same algorithm outline as Algorithm 1 of [DMIMW12]. The improved bound is stated below (cf. [CW12, Theorem 21]).

2 Least Squares Regression

There is an algorithm for least squares regression running in time $O(\operatornamewithlimits{nnz}(A)+d^{3}\log(d/\varepsilon)/\varepsilon^{2})$ and succeeding with probability at least $2/3$.

Proof. Applying Theorem 3 to the subspace spanned by columns of $A$ and $b$, we get a distribution over matrices $\Pi$ of size $O(d^{2}/\varepsilon^{2})\times n$ such that $\Pi$ preserves lengths of vectors in the subspace up to a factor $1\pm\varepsilon$ with probability at least $5/6$. Thus, we only need to find $\operatornamewithlimits{argmin}_{x}\|\Pi Ax-\Pi b\|_{2}$. Note that $\Pi A$ has size $O(d^{2}/\varepsilon^{2})\times d$. By Theorem 12 of [Sar06], there is an algorithm that with probability at least $5/6$, finds a $1\pm\varepsilon$ approximate solution for least squares regression for the smaller input of $\Pi A$ and $\Pi b$ and runs in time $O(d^{3}\log(d/\varepsilon)/\varepsilon^{2})$. $\blacksquare$

The following theorem follows from using the embedding of Theorem 9 and the same argument as [CW12, Theorem 32].

Let $r$ be the rank of $A$. There is an algorithm for least squares regression running in time $O(\operatornamewithlimits{nnz}(A)((\log r)^{O(1)}+\log(n/\varepsilon))+r^{\omega}(\log r)^{O(1)}+r^{2}\log(1/\varepsilon))$ and succeeding with probability at least $2/3$.

3 Low Rank Approximation

In this section, we describe the application of our subspace embeddings to low rank approximation. Here given a matrix $A$, one wants to find a rank $k$ matrix $A_{k}$ minimizing $\|A-A_{k}\|_{F}$. Let $\Delta_{k}$ be the minimum $\|A-A_{k}\|_{F}$ over all rank $k$ matrices $A_{k}$. Notice that our matrices are of the same form as sparse JL matrices considered by [KN12] so the following property holds for matrices constructed in Theorem 9 (cf. [CW12, Lemma 24]).

[KN12, Theorem 19] Fix $\varepsilon,\delta>0$. Let $\mathcal{D}$ be the distribution over matrices given in Theorem 9 with $n$ columns. For any matrices $A,B$ with $n$ rows,

The matrices of Theorem 3 are the same as those of [CW12] so the above property holds for them as well. Therefore, the same algorithm and analysis as in [CW12] work. We state the improved bounds using the embedding of Theorem 3 and Theorem 9 below (cf. [CW12, Theorem 36 and 38]).

Given a matrix $A$ of size $n\times n$, there are 2 algorithms that, with probability at least $3/5$, find 3 matrices $U,\Sigma,V$ where $U$ is of size $n\times k$, $\Sigma$ is of size $k\times k$, $V$ is of size $n\times k$, $U^{T}U=V^{T}V=I_{k}$, $\Sigma$ is a diagonal matrix, and

Proof. The proof is essentially the same as that of [CW12] so we only mention the difference. We use 2 bounds for the running time: multiplying an $a\times b$ matrix and a $b\times c$ matrix with $c>a$ takes $O(a^{\omega-2}bc)$ time (simply dividing the matrices into $a\times a$ blocks), and approximating SVD for an $a\times b$ matrix $M$ with $a>b$ takes $O(ab^{\omega-1})$ time (time to compute $M^{T}M$, approximate SVD of $M^{T}M=QDQ^{T}$ in $O(b^{\omega})$ time [DDH07], and compute $MQ$ to complete the SVD of $M$). $\blacksquare$

Acknowledgments

We thank Andrew Drucker for suggesting the SNAP acronym for the OSE’s considered in this work, to which we added the “oblivious” descriptor.

References