Motivation
Large matrix computations often spend most of their effort reading rows and accumulating outer products. A randomized approximation asks whether a smaller random collection of contributions can answer the intended question accurately enough. The goal is not to make randomness look sophisticated. It is to trade a precisely measured error for less arithmetic or less communicated information, while stating the cost of preparing the sampling distribution.
There are several different promises a sketch might make. It may approximate one matrix product in mean square, preserve the length of one fixed vector with high probability, or preserve an entire subspace uniformly. These statements have different quantifiers. A guarantee for one vector selected before the sketch does not automatically hold for a vector chosen afterwards by an optimizer that has inspected the sketch. This distinction is especially important when a sampled Gram matrix is used inside a linear solver.
We develop two elementary finite algorithms: importance sampling of row outer products and random-sign projection. Both have proofs that can be checked with basic expectations and inner products. They supply a rigorous entry to randomized numerical linear algebra, while leaving stronger subspace-embedding and least-squares sampling theorems as additional topics. All software below is framework-neutral Python; its seeded generator provides a repeatable demonstration, while the theorems use ideal independent draws.
Definitions
Definition 6.1.1
(Importance-sampled matrix product)
Let and . Write their rows as transposed column vectors . Then
Choose probabilities summing to one, positive whenever ; such probabilities are called admissible. Draw independent indices with replacement and define
Terms with zero probability have zero outer product and are never drawn. The Frobenius norm is the square root of the sum of squared entries; its inner product makes matrices an ordinary finite-dimensional Euclidean space. In particular, .
Definition 6.1.2
(Random-sign sketch)
A random-sign sketch is a matrix whose entries are independent signs, each equally likely to be plus or minus . It maps to .
Computing stores only coordinates for a vector with coordinates, but a dense implementation still reads all coordinates and uses sign contributions. Compression of the output does not by itself prove cheaper input processing. The same observation applies when sketching all columns of a matrix.
For both algorithms the data are fixed before the random choices. Expectations describe repetition over those choices. Finite-precision sampling probabilities and arithmetic introduce additional numerical questions; unbiasedness below is an exact-arithmetic identity. A single printed estimate need not equal its expectation, and a reproducible seed is not an accuracy certificate.
Concept lensAlgebraic
Both estimators are sketched products
Row sampling is also multiplication by a random matrix. Let have -th row . Then row of is , and
Both theorems below therefore measure how far a random matrix or is from the identity, as seen through the data. For signs, has diagonal entries exactly one and off-diagonal entries of mean zero, so . For sampling, , which is the identity on the rows with positive probability; admissibility is exactly what makes . The same algebra shows that is also an unbiased estimate of , without any probabilities.
Theorem/proposition
The first result concerns the sampled product; the second concerns lengths of fixed vectors under a sign sketch.
Theorem 6.1.3
(An unbiased product and its exact mean-square error)
For the row-sampling estimator,
If , choosing minimizes this error among admissible probabilities. Its value is . For any , the probability that the Frobenius error is at least is bounded by this mean-square error divided by .
The sign-sketch statement needs fourth moments, because the quantity of interest is already a square.
Theorem 6.1.4
(A random-sign length guarantee for a fixed finite set)
For a fixed ,
For fixed nonzero vectors, a union bound gives simultaneous relative squared-length error less than with failure probability at most . This bound may exceed one and can be conservative. The set must be chosen independently of the sketch.
Proof sketch or proof idea
Proof
(Unbiasedness, variance and optimal probabilities)
Let for one draw . Only indices with are drawn, so , which equals because every omitted term has zero outer product. Its expected squared Frobenius norm is , the sum in the theorem. Subtracting the squared norm of its mean gives its variance in the Euclidean matrix space. Independent averaging divides that quantity by , because centered cross inner products have zero expectation.
To optimize probabilities, put . Cauchy–Schwarz gives . Equality is attained by probabilities proportional to the nonzero . Markov's inequality applied to the squared error gives the tail statement. The result is about absolute matrix error; if the true product nearly cancels, relative error can still be poor.
The second proof reduces the sketched length to one row of signs.
Proof
(Fourth moments of one sign row)
For one row of an unscaled sign matrix, write . Independence and zero sign means give . In the fourth power only terms whose indices occur an even number of times survive, so
The squared sketched norm is the average of independent copies of . Subtracting from the fourth moment gives , and averaging divides it by , proving the variance formula. Chebyshev's inequality bounds one vector's relative error by . Adding those failure bounds for the fixed set proves the finite-set claim; independence between different vectors' failures is not required.
Proof X-ray
Where each property of the signs enters
The sign proof uses three different properties at three different places. Zero mean and pairwise independence remove the cross terms of ; that alone is unbiasedness.
The variance is the one non-routine step, and it is a count. A term equals one when the four indices pair up and zero otherwise. For a fixed pair , the multiset has orderings, which gives the coefficient six. The diagonal contributes because . A standard Gaussian entry would contribute instead, giving the larger variance , which is exactly the upper bound in the theorem.
Independence of the rows is used only to divide the variance by , and Chebyshev needs nothing beyond that variance. The union bound needs no independence between vectors, but each vector's failure probability is computed with the vector held fixed. The second worked example shows that this hypothesis cannot be removed: for every realized one-row sketch some column-space direction is sent to zero, so a direction chosen after seeing can fail with probability one.
Worked examples
Worked example 6.1.5
(An executable importance-sampled product)
Take rows and scalar rows . The product is . The optimal probabilities are one third and two thirds. One sampled contribution is either or , so the mean-square error after draws is . Uniform sampling instead gives . Here is a complete finite implementation, including the all-zero-contribution case:
import math
import random
import bisect
from itertools import accumulate
def sampled_product(A, B, draws, seed=7):
if draws < 1 or not A or len(A) != len(B):
raise ValueError("invalid sample dimensions")
d, k = len(A[0]), len(B[0])
if any(len(a) != d for a in A) or any(len(b) != k for b in B):
raise ValueError("ragged matrix")
weights = [math.sqrt(sum(x*x for x in a)) *
math.sqrt(sum(y*y for y in b)) for a, b in zip(A, B)]
total = math.fsum(weights)
answer = [[0.0] * k for _ in range(d)]
if total == 0:
return answer
active = [(i, weight) for i, weight in enumerate(weights) if weight > 0]
cdf = list(accumulate(weight / total for i, weight in active))
cdf[-1] = 1.0
rng = random.Random(seed)
for _ in range(draws):
position = bisect.bisect_right(cdf, rng.random())
i = active[position][0]
scale = total / (draws * weights[i])
for j in range(d):
for ell in range(k):
answer[j][ell] += scale * A[i][j] * B[i][ell]
return answer
A = [[1.0, 0.0], [0.0, 2.0]]
B = [[1.0], [1.0]]
estimate = sampled_product(A, B, draws=6)
print(estimate)
With the displayed seed this prints [[1.5], [1.5]]. Its difference from the true product is ordinary sampling error, not evidence against unbiasedness. Computing the probabilities requires an initial row-norm pass, and sampling then requires row access. The small demonstration stores its inputs. A large-file implementation would additionally need an index, a reservoir design or another access strategy; its cost cannot be omitted from a claimed speedup.
Worked example 6.1.6
(A sign sketch can lose a particular vector completely)
For and one sketch row, the squared length is zero when the two signs differ and four when they agree, each with probability one half. Its expectation is the correct value two, while its variance is four. Averaging rows reduces that variance to . A possible complete cancellation in one outcome is compatible with an unbiased length estimator.
For a matrix with two columns and a sketch with , the matrix has a nonzero null vector . If the original columns are independent, is a genuine original column-space direction with . Thus every realized one-row sketch loses some direction of that column space. A fixed-vector guarantee and a uniform guarantee over all directions are genuinely different statements, even when their formulas look similar.
Worked example 6.1.7
(Unbiased inputs do not make an unbiased linear solve)
Let a positive scalar estimate be one or three with equal probability, so . With a fixed right-hand side one, the expected solved coefficient is , whereas solving the mean system gives . Inversion is nonlinear. The same warning applies to sampled Gram matrices: unbiased entries alone do not establish unbiased coefficients or even invertibility of each sampled system.
There is a useful deterministic bridge to a solver. It converts an operator-norm event about the sampled Gram matrix into a coefficient bound.
Proposition 6.1.8
(A perturbation bound for a sampled normal-equation solve)
Let be positive definite with smallest eigenvalue , let , and let . Suppose is symmetric with for some , and . Then is invertible, and the solution of satisfies
Proof
(A lower quadratic form, then subtraction)
For a unit vector , . Since is symmetric, its smallest eigenvalue is at least , so it is invertible and . Subtracting from gives , whose norm is at most . Multiplying by gives the bound.
Turning a randomized product theorem into a solver theorem therefore needs a sufficiently strong joint event, not just an expectation. A Frobenius error bound can control operator norm because the latter is no larger, but the resulting sample budget may be conservative.
A useful budget has to name its error scale
An absolute matrix error target can be normalized by the input energies rather than by the possibly tiny true product.
Corollary 6.1.9
(A draw budget on the input-energy scale)
Assume and use the optimal probabilities. For every ,
Hence draws give failure probability at most .
Proof
(Cauchy–Schwarz on the row norms)
Cauchy–Schwarz gives , which is positive because . The optimal mean-square error is . Markov's inequality with gives the display.
This is a meaningful dimension-independent count of sampled outer products, but it is not a relative-error theorem for itself. If two large contributions nearly cancel, the input-energy scale can be much larger than the answer.
Arithmetic and access costs must accompany that budget. Once row probabilities are available, each sampled dense outer product needs work, and the cumulative probability array in the program permits a binary search in comparisons. Preparing row norms and that array still reads the inputs and uses additional probability storage in this reference implementation. Direct exact multiplication costs arithmetic. Sampling can save outer-product work when the selected budget is much smaller than the row count, yet a small problem or an expensive access pattern can erase the benefit. These expressions describe counts, not a measured runtime advantage.
Common mistakes
Common mistake
(Dropping the inverse-probability weights)
Averaging the sampled outer products without dividing by estimates , a probability-weighted product, not . For scalar contributions one and three with probabilities and , the unweighted average has expectation , whereas the target is four. The division by is what makes every draw an unbiased estimate of the whole sum.
Counterexample mode
A zero probability on a nonzero contribution
Claim: dividing each drawn term by its probability makes the estimator unbiased for every probability vector. Take scalar contributions one and three and probabilities . Every draw is the first index, so every estimate equals and the expectation is one, not four; the second contribution can never be recovered. The repair is the admissibility condition in the definition: whenever . A contribution that is exactly zero may receive probability zero, since the expectation then omits only zero terms.
Probabilities proportional to the products of paired row norms are optimal for the stated product-error criterion; they are not automatically optimal for subspace preservation or downstream prediction risk.
Common mistake
(Treating output dimension as input cost)
Applying the dense random-sign algorithm directly costs for one vector and for a matrix with columns. It reduces the dimension passed to later stages, but may be a poor first operation for a very sparse matrix. Structured or sparse sketches require their own construction and proof. A method's name is not a resource analysis.
Common mistake
(Reporting the most attractive seed)
Repeated random experiments can estimate typical performance, but selecting only the most attractive seed changes the reported procedure. Record the sampling budget, probabilities and selection rule. The theorem's probability space concerns all draws from the declared design, including inconvenient outcomes.
Summary
Importance sampling gives an unbiased matrix product with an exact variance and an optimal row-probability choice for Frobenius error. Random signs preserve fixed-vector squared lengths in expectation and admit a finite-set probability bound. Solver stability, uniform subspace preservation and computational access costs need additional arguments. These limits explain which conclusions a small sketch actually supports.
Exercises
Exercise 6.1.10
(For scalar contributions one and three, compare the variance of a one-draw inverse-probability estimator under uniform sampling and under probabilities proportional to the contributions.)
Foundation
Solution · Answer
The true sum is four. Uniform sampling returns or , with variance four. Proportional probabilities are ; either sampled contribution divided by its probability equals four, so variance is zero. The cancellation-free scalar structure makes this special case exact; matrix contributions pointing in different directions need not enjoy zero variance under the same probability rule.
Exercise 6.1.11
(Use the random-sign bound to give a sufficient sketch size for ten fixed nonzero vectors, relative squared-length error below , and failure probability at most . Is this a sharp dimension estimate?)
Foundation
Solution · Answer
Require , giving . This follows from elementary fourth moments and a union bound, so it is sufficient and potentially very loose. It is not the logarithmic finite-set dimension bound obtainable from stronger concentration arguments, which have not been proved here.
Exercise 6.1.12
(Why can a sample size equal to the number of columns still produce a singular sampled Gram matrix when row sampling uses replacement? Give a two-row example.)
Core
Solution · Answer
Let and draw two rows with replacement, each with positive probability. Drawing the first row twice has positive probability and produces a Gram estimate supported only on the first coordinate. Its second eigenvalue is zero, although the original Gram matrix is the identity. Sample count alone is not a rank certificate.
Exercise 6.1.13
(In the perturbation bound for the sampled solve, take , , and . Compute the coefficient-error bound and identify why the condition matters.)
Core
Solution · Answer
The numerator is , and the denominator is . The bound is . The strict condition keeps the lower eigenvalue estimate positive; at one the argument allows the approximate matrix to become singular, so no finite inverse-norm bound follows from this reasoning.