Source-linked AI summary
Sketching Outside the Hilbert Space for the Infinite-Dimensional Randomised SVD
Morgan Lynch-Davies, Marcus Webb
TL;DR
Infinite-dimensional isotropic sketch vectors may not belong to a separable Hilbert space, complicating the extension of randomized SVD. The paper introduces sketch functionals to handle general sketch distributions and applies the framework to sub-Gaussian sketches. It develops infinite-dimensional randomized-SVD results for bounded covariance operators and sub-Gaussian sketches.
Problem
Infinite-dimensional isotropic sketch vectors may not be elements of the Hilbert space, while existing approaches use trace-class Gaussian-process covariances or leave the isotropic sketch implicit.
Source: §1 · pp. 1, 3Method
Results
The framework extends infinite-dimensional randomized-SVD and Nyström analysis to general sketch distributions, including sub-Gaussian sketches and bounded covariance operators.
Source: §1 · p. 1Takeaways & Limitations
Sketch functionals may also apply to other randomized algorithms whose first step multiplies the target operator by a sketch matrix, including least squares and trace estimation.
Source: §5 · p. 31For the Schrödinger example, an inexact approximate singular basis combined with overly strong decay can make βk grow quickly.
Source: §4.1 · p. 28
Abstract
from arXiv · showhide
In randomised numerical linear algebra, common choices for distributions of sketch vectors $\omega \in \mathbb R^n$ are isotropic, so that $\mathbb E[\omega \omega^T]=I_n$. Unfortunately, the natural extension of an isotropic vector in $(\mathbb R^n, \|\cdot \|_{2})$ to an infinite-dimensional separable Hilbert space $\mathcal H$ may not exist as an element of the space, posing an obstacle for any attempt to lift the randomised SVD to infinite-dimensional target operators $A$. Current workarounds either forego isotropy and take $\omega$ to be a continuous Gaussian process with trace-class covariance operators, or leave $\omega$ implicit by instead sampling $A\omega$ as if $\omega$ were isotropic Gaussian. We unify their approaches by introducing "sketch functionals", an example of cylindrical random variables (Vakhania--Tarieladze--Chobanyan 1987) which allow us to treat general, non-Gaussian distributions with bounded covariance operators. To demonstrate the utility of the new theory, we apply it to develop novel bounds for the infinite-dimensional randomised SVD with a general class of sub-Gaussian sketch distributions.
1 Introduction
The introduction frames infinite-dimensional isotropic sketching as problematic because such sketch vectors need not belong to the Hilbert space, and develops a framework for randomised SVD and Nyström approximation with general sketch distributions. It situates this framework among prior Gaussian approaches and motivates its extension to sub-Gaussian sketches.
1 Introduction
- The paper develops a framework for infinite-dimensional randomised SVD and Nyström approximation with general sketch distributions, extending prior work restricted to isotropic Gaussian sketches or trace-class Gaussian-process covariances.The authors apply the framework to sub-Gaussian processes, extending the theory of Saibaba–Międlar to infinite dimensions.Source: §1 · p. 1
- The finite-dimensional randomized SVD sketches ℓ random vectors by applying A, forms an orthonormal basis for their images, then computes an SVD of the reduced operator.The resulting approximation has rank at most ℓ; the introduction identifies applying A a total of 2ℓ times as a dominant computational cost.Source: §1 · pp. 1–2
- The classical randomized-SVD error statement compares the random rank-ℓ approximation with the optimal rank-k Frobenius error, with a high-probability multiplicative excess.The supplied introduction identifies the optimal error as ∥Σ⊥∥F but does not include the theorem's explicit bound.Source: §1 · p. 2
- Infinite-dimensional isotropic sketch vectors need not be elements of the Hilbert space, creating a basic obstacle to directly extending finite-dimensional sketching.The White Noise Problem states that an isotropic random vector in an infinite-dimensional Hilbert space has infinite expected squared norm.Source: §1 · p. 3
- Existing infinite-dimensional approaches use either Gaussian processes with trace-class covariance or implicit isotropic Gaussian sketches sampled through Aω; the latter recovers nearly the known finite-dimensional bounds for Hilbert–Schmidt A.Allowing general covariance can improve approximation when it aligns with the target operator, while the trace-class Gaussian bounds are described as suboptimal relative to isotropic-case theory.Source: §1 · p. 3
- The introduction presents sketch functionals as a framework that encompasses both approaches, recovers isotropic Gaussian bounds, extends results to bounded covariance operators, and enables sub-Gaussian results.The paper compares the sub-Gaussian bounds with numerical experiments in Section 4.Source: §1 · p. 3
2 Infinite-Dimensional Randomised NLA with Sketch Functionals
This section develops sketch functionals as a way to formulate infinite-dimensional randomized NLA through tests against vectors, defining their covariance and operator actions and presenting a randomized SVD framework. It also examines finite-dimensional truncation for Hilbert–Schmidt targets and Gaussian sketch functionals, including bounded covariance operators.
2.2 Sketch Functionals
- Sketch functionals replace Hilbert-space-valued sketches with bounded, centred linear tests having finite second moments, and their covariance is a bounded symmetric positive semi-definite operator.Their framework is a special case of cylindrical random variables, and the paper identifies the space H# with centred cylindrical random variables having finite weak second moments [22, §VI.3.2 and §VI.5.1].Source: §2 · p. 4, §2.2 · pp. 5–6
2.1 Definitions and Concepts from Functional Analysis
- For compact operators, trace-class implies Hilbert–Schmidt, which implies compactness, while the framework also applies to non-compact self-adjoint operators that have eigendecompositions.Hilbert–Schmidt operators have singular values in ℓ2, and trace-class operators with eigenvalues in ℓ1.Source: §2.1 · p. 5
2.2 Sketch Functionals
- For a sketch functional with covariance C, applying a bounded operator A changes the covariance to ACAT; isotropy means C is the identity, though an isotropic sketch need not be Hilbert-space-valued.In fact, isotropic sketch functionals have infinite expected squared Hilbert-space norm, but an example shows they can have finite norm almost surely.Source: §2.2 · pp. 7–8
- For a Hilbert–Schmidt operator A, applying a sketch functional yields a K-valued random element almost surely, enabling the algorithm to form AS and compute a rank-ℓ approximation.The algorithm orthogonalises AS, computes an SVD of Q^T A, and returns QQ^T A. A structural bound is given in spectral and Hilbert–Schmidt norms when the projected sketch matrix S1 has full row rank.Source: §2.2 · pp. 8–9
2.3 Reduction to Finite Dimensions
- Finite-dimensional computation projects a sketch functional onto the first n basis vectors; for each fixed x this converges, but if C is not compact the truncations do not converge in operator norm.An exact isotropic Gaussian sample cannot be stored because it has infinitely many non-shrinking components.Source: §2.3 · p. 10
- Finite-dimensional projection makes sketching viable for Hilbert–Schmidt targets, with truncation error controlled and the analysis carrying over to Nyström approximation.The section also analyzes the error from truncating the sketch in the randomized SVD.Source: §2.3 · pp. 10–11
2.4 A Note on the Gaussian Case
- A Gaussian sketch functional is defined by requiring s(x) to be Gaussian for every x in H, following the convention used for Gaussian random vectors.The section states that finite collections of evaluations are jointly Gaussian by linearity.Source: §2.4 · p. 11
- The section gives a probabilistic bound for Gaussian sketch functionals with bounded SPSD covariance and states exact recovery almost surely when the target’s tail is zero.The theorem assumes a Hilbert–Schmidt target and a condition on the covariance restricted to the leading right-singular subspace; βk measures covariance alignment.Source: §2.4 · p. 12
- Boullé–Townsend’s Gaussian-vector result [6] extends to bounded SPSD covariance with sketch functionals, under its other hypotheses.Its alignment factor αk/γk plays a role similar to βk; the factors are finite when their stated conditions hold, while the zero-tail case gives exact recovery almost surely.Source: §2.4 · p. 13
3 Sub-Gaussian Random Processes
This section develops sub-Gaussian sketch functionals and processes, along with low-rank approximation results including infinite-dimensional randomized SVD error-tail bounds and Nyström approximation. It also presents random-matrix bounds for analyzing sub-Gaussian sketches.
3.1 Sub-Gaussian Random Variables, Vectors and Processes
- Sub-Gaussian sketch functionals are defined by a uniform ψ2 bound on s(x) for unit x; an isotropic Rademacher sketch functional has norm 1.The Rademacher construction uses independent unit-variance coefficients along an orthonormal basis.Source: §3.1 · pp. 14–15
3.2 Sub-Gaussian Processes
- A centred process that is pointwise sub-Gaussian with norm at most K induces a sub-Gaussian random vector with norm at most K.The converse need not hold: an L2-valued process can have finite sub-Gaussian vector norm while a point value is exponential and not sub-Gaussian.Source: §3.2 · p. 16
- A centred sketch functional with bounded covariance defines a mean-square continuous process whose stochastic Riemann integral recovers s(f), but this does not guarantee continuous sample paths.For Rademacher sketches, the resulting processes generally fail to be local martingales, so Itô calculus does not apply.Source: §3.2 · p. 17
3.3 Low-Rank Operator Approximation Results
- Theorem 3.15 gives error tail bounds for a Hilbert–Schmidt target operator sketched with independent isotropic sub-Gaussian sketch functionals.The sketches have sub-Gaussian norm at most K; the theorem also imposes conditions on the target rank and sketch count.Source: §3.3 · p. 18
- Theorem 3.15 requires oversampling of order K^2 for large k and ℓ, unlike the Gaussian case where ℓ/k can approach 1.The K^2 requirement is sharp within the cited general matrix family.Source: §3.3 · p. 19
- The authors obtain ℓ = O(K^2k) sampling, compared with ℓ = O(K^4k) suggested by Saibaba–Międlar, and resolve unspecified constants.Their bounds share a limitation: the error floor is ∥A − Â∥ ≤ ∥Σ⊥∥HS; unlike the comparable Gaussian result [16], they do not capture cross-cancellation as oversampling grows.Source: §3.3 · p. 20
- Theorem 3.18 extends the analysis to sketches C^1/2ω for bounded SPSD covariance operator C, and gives exact recovery when ∥Σ⊥∥HS = 0.Here ω is isotropic and sub-Gaussian, and the theorem uses the same D > 0 condition as Theorem 3.15.Source: §3.3 · p. 20
- The bounds use β_k to measure covariance alignment and separately encode covariance quality and the sub-Gaussian norms of sketch components, as in [6].The authors note that component sub-Gaussian norms and second moments are intertwined but not equivalent.Source: §3.3 · p. 21
- When the residual tail has zero nuclear norm, the infinite-dimensional Nyström output equals A with at least the same probability in either sketch setting.The result applies to an SPSD trace-class target and the sketch settings described in Corollary 3.19.Source: §3.3 · pp. 21–22
- The Nyström approximation can be recast as a randomized SVD for A^1/2, with a positive-semidefinite error enabling bounds from prior results.The reduction uses the projection onto the columns of Z = A^1/2S.Source: §3.3 · p. 22
3.4 Sub-Gaussian Random Matrix Theory
- The section invokes two-sided singular-value bounds for matrices with independent, centered, isotropic sub-Gaussian rows, with constants depending on K [25].These bounds address the need to control the pseudoinverse in the sub-Gaussian analysis.Source: §3.4 · pp. 23, 25
4 Numerical Experiments
Experiments on continuous and discrete Schrödinger operators show that using prior spectral structure can improve randomized SVD accuracy, while an isotropic low-entropy sketch performs poorly. Results also compare isotropic distributions and theoretical bounds across both settings.
4 Numerical Experiments
- In Section 4.1, G is represented using its first 500 eigenpairs, omitting an error of less than 10−3 in the Hilbert–Schmidt norm.Source: §4 · p. 25
4.1 The Continuous Schrödinger Operator
- Isotropic Rademacher and Gaussian sketches perform almost identically in practice, although the sub-Gaussian bounds are much worse and require higher oversampling.Figure 3 compares practice and theory errors for the two sketch types.Source: §4.1 · p. 26, Figure 3 · p. 27
- Most isotropic distributions perform similarly, but lowering q in sparse Rademacher sketches has a substantial effect at low sketch ranks.Figure 4 reports median Hilbert–Schmidt errors over 15 trials.Source: §4.1 · p. 26, Figure 4 · p. 27
- Using a trigonometric covariance informed by G improves accuracy over isotropic sketches, but the available bounds do not capture that improvement.The sketches use eigenvalues 1/(n + 1)^2 for sine and cosine basis functions and 1 for constants.Source: §4.1 · p. 26, Figure 6 · p. 28
- Changing Gaussian covariance decay can yield marginal performance gains, with λn = (n + 1)−1 giving a compact but non-trace-class covariance.Figure 5 compares isotropic sketches with decays of (n + 1)−2 and (n + 1)−1.Source: §4.1 · p. 28, Figure 5 · p. 28
4.2 The Discrete Schrödinger Operator
- For the discrete operator with V(n) tending to infinity, the potential dominates the bounded-spectrum Laplacian, giving E eigenvalues of O(n^2) and trace-class G.Source: §4.2 · p. 30
- A one-dimensional random variable Θ and a sign flip define an isotropic sketch supported on discrete-Laplacian eigenvectors outside ℓ2.The sketch vectors lie in ℓ∞ but not ℓ2; sketch functionals can treat these eigenvectors directly.Source: §4.2 · p. 30
- The low-entropy sketch has much higher error variance than isotropic Gaussian and Rademacher sketches, which perform indistinguishably well.Its large error bands reflect dependence on relatively few independent random variables; progress can plateau when sampled angles are close to previous ones.Source: §4.2 · p. 31, Figure 7 · p. 31
5 Conclusions
The paper applies cylindrical random variables through sketch functionals to unify and extend infinite-dimensional randomized NLA results, and argues this framework may support other randomized algorithms. Its bounds retain a large-ℓ limitation, and its theory assumes independent sketch functionals.
5 Conclusions
- Sketch functionals unite and generalize prior infinite-dimensional randomized NLA results to sketches with bounded covariance operators and yield the first infinite-dimensional randomized SVD results for sub-Gaussian sketches.The paper presents them as a natural framework for reasoning about infinite-dimensional random sketches.Source: §5 · p. 31
- Sketch functionals may also support lifting randomized least squares and randomized trace estimation to infinite dimensions.These are proposed as possible future applications.Source: §5 · p. 31
- For large ℓ, the sub-Gaussian bounds give ∥A−Â∥2 ≤ 2∥Σ⊥∥2, while comparable Gaussian results have the factor tending to 1.The authors suggest the difference may arise from the conditional-probability argument for Gaussian sketches versus a crude submultiplicativity bound for sub-Gaussian sketches.Source: §5 · p. 32
- The theory focuses on independent sketch functionals, although finite-dimensional SRFT sketches are a dependent alternative.The paper says the infinite-dimensional analogue of SRFT is unclear, but its columns could likely be captured by sketch functionals.Source: §5 · p. 32
Tool and Computational Resource Disclosure
The authors disclose using Claude and Codex for copyediting and referee-style reports, Codex for an initial proof draft, and Opus for modifying MATLAB figure code; they verified all suggestions and contributions.
Tool and Computational Resource Disclosure
- Claude and Codex assisted with copyediting and referee-style reports; Codex drafted an initial proof of Lemma 3.21, and Opus modified MATLAB code for Section 4 figures.The authors state that they verified all suggestions and contributions and take full responsibility for the content.Source: Tool and Computational Resource… · p. 32