I’m excited to share that my paper, Fast and forward stable randomized algorithms for linear least-squares problems has been released as a preprint on arXiv.
With the release of this paper, now seemed like a great time to discuss a topic I’ve been wanting to write about for a while: sketching. For the past two decades, sketching has become a widely used algorithmic tool in matrix computations. Despite this long history, questions still seem to be lingering about whether sketching really works:
In this post, I want to take a critical look at the question “does sketching work”? Answering this question requires answering two basic questions:
- What is sketching?
- What would it mean for sketching to work?
I think a large part of the disagreement over the efficacy of sketching boils down to different answers to these questions. By considering different possible answers to these questions, I hope to provide a balanced perspective on the utility of sketching as an algorithmic primitive for solving linear algebra problems.
In matrix computations, sketching is really a synonym for (linear) dimensionality reduction. Suppose we are solving a problem involving one or more high-dimensional vectors or perhaps a tall matrix . A sketching matrix is a matrix where . When multiplied into a high-dimensional vector or tall matrix , the sketching matrix produces compressed or “sketched” versions and that are much smaller than the original vector and matrix .
Let be a collection of vectors. For to be a “good” sketching matrix for , we require that preserves the lengths of every vector in up to a distortion parameter :
For linear algebra problems, we often want to sketch a matrix . In this case, the appropriate set that we want our sketch to be “good” for is the column space of the matrix , defined to be
Remarkably, there exist many sketching matrices that achieve distortion
with an output dimension of roughly
. In particular, the sketching dimension
is proportional to the number of columns
. This is pretty neat! We can design a single sketching matrix
which preserves the lengths of all infinitely-many vectors
in the column space of
There are many types of sketching matrices, each with different benefits and drawbacks. Many sketching matrices are based on randomized constructions in the sense that entries of are chosen to be random numbers. Broadly, sketching matrices can be classified into two types:
- Data-dependent sketches. The sketching matrix is constructed to work for a specific set of input vectors .
- Oblivious sketches. The sketching matrix is designed to work for an arbitrary set of input vectors of a given size (i.e., has elements) or dimension ( is a -dimensional linear subspace).
We will only discuss oblivious sketching for this post. We will look at three types of sketching matrices: Gaussian embeddings, subsampled randomized trignometric transforms, and sparse sign embeddings.
The details of how these sketching matrices are built and their strengths and weaknesses can be a little bit technical. All three constructions are independent from the rest of this article and can be skipped on a first reading. The main point is that good sketching matrices exist and are fast to apply: Reducing to requires roughly operations, rather than the operations we would expect to multiply a matrix and a vector of length .
The simplest type of sketching matrix is obtained by (independently) setting every entry of to be a Gaussian random number with mean zero and variance . Such a sketching matrix is called a Gaussian embedding.
Benefits. Gaussian embeddings are simple to code up, requiring only a standard matrix product to apply to a vector or matrix . Gaussian embeddings admit a clean theoretical analysis, and their mathematical properties are well-understood.
Drawbacks. Computing for a Gaussian embedding costs operations, significantly slower than the other sketching matrices we will consider below. Additionally, generating and storing a Gaussian embedding can be computationally expensive.
The subsampled randomized trigonometric transform (SRTT) sketching matrix takes a more complicated form. The sketching matrix is defined to be a scaled product of three matrices
These matrices have the following definitions:
- is a diagonal matrix whose entries are each a random (chosen independently with equal probability).
- is a fast trigonometric transform such as a fast discrete cosine transform.
- is a selection matrix. To generate , let be a random subset of , selected without replacement. is defined to be a matrix for which for every vector .
To store on a computer, it is sufficient to store the diagonal entries of and the selected coordinates defining . Multiplication of against a vector should be carried out by applying each of the matrices , , and in sequence, such as in the following MATLAB code:
% Generate randomness for S
signs = 2*randi(2,m,1)-3; % diagonal entries of D
idx = randsample(m,d); % indices i_1,...,i_d defining R
% Multiply S against b
c = signs .* b % multiply by D
c = dct(c) % multiply by F
c = c(idx) % multiply by R
c = sqrt(n/d) * c % scale
Benefits. can be applied to a vector in operations, a significant improvement over the cost of a Gaussian embedding. The SRTT has the lowest memory and random number generation requirements of any of the three sketches we discuss in this post.
Drawbacks. Applying to a vector requires a good implementation of a fast trigonometric transform. Even with a high-quality trig transform, SRTTs can be significantly slower than sparse sign embeddings (defined below). SRTTs are hard to parallelize. In theory, the sketching dimension should be chosen to be , larger than for a Gaussian sketch.
A sparse sign embedding takes the form
Here, each column
is an independently generated random vector with exactly
nonzero entries with random
values in uniformly random positions. The result is a
matrix with only
nonzero entries. The parameter
is often set to a small constant like
Benefits. By using a dedicated sparse matrix library, can be very fast to apply to a vector (either or operations) to apply to a vector, depending on parameter choices (see below). With a good sparse matrix library, sparse sign embeddings are often the fastest sketching matrix by a wide margin.
Drawbacks. To be fast, sparse sign embeddings requires a good sparse matrix library. They require generating and storing roughly random numbers, higher than SRTTs (roughly numbers) but much less than Gaussian embeddings ( numbers). In theory, the sketching dimension should be chosen to be and the sparsity should be set to ; the theoretically sanctioned sketching dimension (at least according to existing theory) is larger than for a Gaussian sketch. In practice, we can often get away with using and .
Using either SRTTs or sparse maps, a sketching a vector of length down to dimensions requires only to operations. To apply a sketch to an entire matrix thus requires roughly operations. Therefore, sketching offers the promise of speeding up linear algebraic computations involving , which typically take operations.
How Can You Use Sketching?
The simplest way to use sketching is to first apply the sketch to dimensionality-reduce all of your data and then apply a standard algorithm to solve the problem using the reduced data. This approach to using sketching is called sketch-and-solve.
As an example, let’s apply sketch-and-solve to the least-squares problem:
We assume this problem is highly overdetermined with
having many more rows
To solve this problem with sketch-and-solve, generate a good sketching matrix for the set . Applying to our data and , we get a dimensionality-reduced least-squares problem
is the sketch-and-solve solution to the least-squares problem, which we can use as an approximate solution to the original least-squares problem.
Least-squares is just one example of the sketch-and-solve paradigm. We can also use sketching to accelerate other algorithms. For instance, we could apply sketch-and-solve to clustering. To cluster data points , first apply sketching to obtain and then apply an out-of-the-box clustering algorithms like k-means to the sketched data points.
Does Sketching Work?
Most often, when sketching critics say “sketching doesn’t work”, what they mean is “sketch-and-solve doesn’t work”.
To address this question in a more concrete setting, let’s go back to the least-squares problem (2). Let denote the optimal least-squares solution and let be the sketch-and-solve solution (3). Then, using the distortion condition (1), one can show that
If we use a sketching matrix with a distortion of
, then this bound tells us that
Is this a good result or a bad result? Ultimately, it depends. In some applications, the quality of a putative least-squares solution is can be assessed from the residual norm . For such applications, the bound (4) ensures that is at most twice . Often, this means is a pretty decent approximate solution to the least-squares problem.
For other problems, the appropriate measure of accuracy is the so-called forward error , measuring how close is to . For these cases, it is possible that might be large even though the residuals are comparable (4).
Let’s see an example, using the MATLAB code from my paper:
[A, b, x, r] = random_ls_problem(1e4, 1e2, 1e8, 1e-4); % Random LS problem
S = sparsesign(4e2, 1e4, 8); % Sparse sign embedding
sketch_and_solve = (S*A) \ (S*b); % Sketch-and-solve
direct = A \ b; % MATLAB mldivide
Here, we generate a random least-squares problem of size 10,000 by 100 (with condition number and residual norm ). Then, we generate a sparse sign embedding of dimension (corresponding to a distortion of roughly ). Then, we compute the sketch-and-solve solution and, as reference, a “direct” solution by MATLAB’s \.
We compare the quality of the sketch-and-solve solution to the direct solution, using both the residual and forward error:
fprintf('Residuals: sketch-and-solve %.2e, direct %.2e, optimal %.2e\n',...
norm(b-A*sketch_and_solve), norm(b-A*direct), norm(r))
fprintf('Forward errors: sketch-and-solve %.2e, direct %.2e\n',...
Here’s the output:
Residuals: sketch-and-solve 1.13e-04, direct 1.00e-04, optimal 1.00e-04
Forward errors: sketch-and-solve 1.06e+03, direct 8.08e-07
The sketch-and-solve solution has a residual norm of , close to direct method’s residual norm of . However, the forward error of sketch-and-solve is nine orders of magnitude larger than the direct method’s forward error of .
Does sketch-and-solve work? Ultimately, it’s a question of what kind of accuracy you need for your application. If a small-enough residual is all that’s needed, then sketch-and-solve is perfectly adequate. If small forward error is needed, sketch-and-solve can be quite bad.
One way sketch-and-solve can be improved is by increasing the sketching dimension and lowering the distortion . Unfortunately, improving the distortion of the sketch is expensive. Because of the relation , to decrease the distortion by a factor of ten requires increasing the sketching dimension by a factor of one hundred! Thus, sketch-and-solve is really only appropriate when a low degree of distortion is necessary.
Iterative Sketching: Combining Sketching with Iteration
Sketch-and-solve is a fast way to get a low-accuracy solution to a least-squares problem. But it’s not the only way to use sketching for least-squares. One can also use sketching to obtain high-accuracy solutions by combining sketching with an iterative method.
There are many iterative methods for least-square problems. Iterative methods generate a sequence of approximate solutions that we hope will converge at a rapid rate to the true least-squares solution, .
To using sketching to solve least-squares problems iteratively, we can use the following observation:
If is a sketching matrix for , then .
Therefore, if we compute a QR factorization
Notice that we used the fact that
has orthonormal columns. The conclusion is that
Let’s use the approximation to solve the least-squares problem iteratively. Start off with the normal equations
We can obtain an approximate solution to the least-squares problem by replacing
in (5) and solving. The resulting solution is
This solution will typically not be a good solution to the least-squares problem (2), so we need to iterate. To do so, we’ll try and solve for the error . To derive an equation for the error, subtract from both sides of the normal equations (5), yielding
Now, to solve for the error, substitute
again and solve for
, obtaining a new approximate solution
We can now go another step: Derive an equation for the error , approximate , and obtain a new approximate solution . Continuing this process, we obtain an iteration
This iteration is known as the iterative sketching
method. If the distortion is small enough, this method converges at an exponential rate, yielding a high-accuracy least squares solution after a few iterations.
Let’s apply iterative sketching to the example we considered above. We show the forward error of the sketch-and-solve and direct methods as horizontal dashed purple and red lines. Iterative sketching begins at roughly the forward error of sketch-and-solve, with the error decreasing at an exponential rate until it reaches that of the direct method over the course of fourteen iterations. For this problem, at least, iterative sketching gives high-accuracy solutions to the least-squares problem!
To summarize, we’ve now seen two very different ways of using sketching:
- Sketch-and-solve. Sketch the data and and solve the sketched least-squares problem (3). The resulting solution is cheap to obtain, but may have low accuracy.
- Iterative sketching. Sketch the matrix and obtain an approximation to . Use the approximation to produce a sequence of better-and-better least-squares solutions by the iteration (6). If we run for enough iterations , the accuracy of the iterative sketching solution can be quite high.
By combining sketching with more sophisticated iterative methods such as conjugate gradient and LSQR, we can get an even faster-converging least-squares algorithm, known as sketch-and-precondition. Here’s the same plot from above with sketch-and-precondition added; we see that sketch-and-precondition converges even faster than iterative sketching does!
“Does sketching work?” Even for a simple problem like least-squares, the answer is complicated:
A direct use of sketching (i.e., sketch-and-solve) leads to a fast, low-accuracy solution to least-squares problems. But sketching can achieve much higher accuracy for least-squares problems by combining sketching with an iterative method (iterative sketching and sketch-and-precondition).
We’ve focused on least-squares problems in this section, but these conclusions could hold more generally. If “sketching doesn’t work” in your application, maybe it would if it was combined with an iterative method.
Just How Accurate Can Sketching Be?
We left our discussion of sketching-plus-iterative-methods in the previous section on a positive note, but there is one last lingering question that remains to be answered. We stated that iterative sketching (and sketch-and-precondition) converge at an exponential rate. But our computers store numbers to only so much precision; in practice, the accuracy of an iterative method has to saturate at some point.
An (iterative) least-squares solver is said to be forward stable if, when run for a sufficient number of iterations, the final accuracy is comparable to accuracy of a standard direct method for the least-squares problem like MATLAB’s \ command or Python’s scipy.linalg.lstsq. Forward stability is not about speed or rate of convergence but about the maximum achievable accuracy.
The stability of sketch-and-precondition was studied in a recent paper by Meier, Nakatsukasa, Townsend, and Webb. They demonstrated that, with the initial iterate , sketch-and-precondition is not forward stable. The maximum achievable accuracy was worse than standard solvers by orders of magnitude! Maybe sketching doesn’t work after all?
Fortunately, there is good news:
- The iterative sketching method is provably forward stable. This result is shown in my newly released paper; check it out if you’re interested!
- If we use the sketch-and-solve method as the initial iterate for sketch-and-precondition, then sketch-and-precondition appears to be forward stable in practice. No theoretical analysis supporting this finding is known at present.
These conclusions are pretty nuanced. To see what’s going, it can be helpful to look at a graph:
The performance of different methods can be summarized as follows: Sketch-and-solve can have very poor forward error. Sketch-and-precondition with the zero initialization is better, but still much worse than the direct method. Iterative sketching and sketch-and-precondition with fair much better, eventually achieving an accuracy comparable to the direct method.
Put more simply, appropriately implemented, sketching works after all!
Sketching is a computational tool, just like the fast Fourier transform or the randomized SVD. Sketching can be used effectively to solve some problems. But, like any computational tool, sketching is not a silver bullet. Sketching allows you to dimensionality-reduce matrices and vectors, but it distorts them by an appreciable amount. Whether or not this distortion is something you can live with depends on your problem (how much accuracy do you need?) and how you use the sketch (sketch-and-solve or with an iterative method).