Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning

1.1 Motivation

• QML speedups rely on strong input and output assumptions, motivating classical counterparts that exploit analogous data-access structures to test whether exponential advantages persist.Prior work dequantized recommendation systems and many other QML algorithms, showing that advertised exponential speedups can disappear under comparable input assumptions [Tan19, Tan21, CGL+20, CLLW20, DBH21, CLS+19, DHLT20].Source: §1.1 · p. 3

1.2 Results

• The paper defines oversampling and query access as a classical analogue of quantum state preparation and shows it supports dimension-independent approximate matrix arithmetic and QSVT-like transformations.The model provides entry queries, norm sampling, and norm estimates; its oversampling overhead ϕ enables approximate queries with multiplicative overhead, while closure extends to products, linear combinations, Kronecker products, outer products, and f(A†A).Source: §1.2 · p. 4
• For QRAM-based inputs, the framework gives compelling evidence against exponential QSVT speedups, while retaining possible large polynomial gaps and requiring approximation overheads.QRAM supports both block-encodings normalized by Frobenius norm and classical sampling access, yielding classical runtimes polynomially slower than corresponding quantum algorithms except in ε; sparsity-based block-encodings fall outside this regime.Source: §1.2 · p. 6, §1.3 · p. 6

1.3 Technical overview

• The technical core approximates matrix products by sampling row outer products and represents singular-value transformations through compact RUR decompositions, avoiding dependence on input dimensions.Sampling yields Z with ||Z − A†B||_F < ε||A||_F||B||_F with probability 0.99, while direct SVT access to f(A†A) follows from repeated use of the key lemma.Source: §1.3 · pp. 6–7

1.4 Applications: dequantizing QML & more

• The framework recovers dequantization results for recommendation systems, PCA, supervised clustering, SVMs, matrix inversion, and SDP solving, while adding low-rank Hamiltonian simulation and discriminant analysis.All results match or improve prior dequantized algorithms except matrix inversion, whose prior incomparable runtime applies only to strictly rank-k inputs; the new inversion and SDP results handle close-to-low-rank matrices more generally.Source: §1.4 · p. 8

1.5 Related work

• Importance sampling is the core primitive distinguishing the quantum-inspired model, enabling dimension-independent runtimes under sampling and query access while yielding weaker guarantees than standard sketching algorithms [KV17].Other sketching methods such as Count-Sketch and Johnson–Lindenstrauss remain linear in input sparsity in these regimes.Source: §1.5 · p. 10
• The framework extends low-rank approximation ideas by showing that useful samples and entries can be produced in dimension-independent time, while improving spectral-norm runtimes and avoiding strictly low-rank inputs compared with prior approaches.Importance sampling also preserves the sampling and query-access assumptions needed by the output matrix, revealing closure properties with broader classical-sketching relevance.Source: §1.5 · pp. 10, 11, 13
• The results provide evidence against exponential quantum speedups for low-rank QRAM-based QML, but do not rule out large polynomial speedups or high-rank approaches based on sparse-access assumptions [HHL09].The discussion identifies sparse inputs and efficiently implementable high-rank operations such as the Quantum Fourier Transform as promising routes to exponential speedups.Source: §1.5 · pp. 12–13

1.6 Open questions

• Open questions include finding practically relevant QML problems with provable superpolynomial speedups, reducing condition-number and SVD costs, and extending the closure properties beyond ℓ2-norm importance sampling.The paper also asks whether classical algorithms can match quantum logarithmic precision dependence for output sampling and whether such advantages can be separated from estimation or decision problems.Source: §1.6 · p. 13
• The work also leaves unresolved whether other sampling distributions, including leverage-score or ℓp-norm sampling, possess analogous matrix-arithmetic closure properties.This question is separate from the runtime and quantum-speedup challenges and concerns generalizing the framework’s sampling primitive.Source: §1.6 · p. 13

1.7 Organization

• The paper’s organization moves from sampling and query-access closure properties through matrix sketching, approximation, and singular value transformation to QSVT dequantization, recovered applications, and more general SVT results.Sections 3–7 establish the primitives, framework, applications, and generalizations in that order.Source: §1.7 · p. 14

2 Preliminaries

• The paper fixes notation for indices, complex conjugation, asymptotic bounds, logarithms, unit-cost arithmetic, and oracle-query costs.Here, e O(g) denotes O(g poly(log g)), and oracle queries cost at least unit time.Source: §2 · p. 14

2.1 Linear algebra

• For complex matrices, the section defines row, column, entry, concatenation, vectorization, Euclidean, Frobenius, and spectral-norm notation.It also defines isometries as norm-preserving maps, equivalently subsets of columns of a unitary.Source: §2.1 · p. 14
• The section introduces SVDs, eigendecompositions, rank-k approximations, pseudoinverses, singular value transformations, and eigenvalue transformations.Singular value transformations require f(0)=0 for SVD-choice independence, while eigenvalue transformations of Hermitian matrices can distinguish eigenvalue signs.Source: §2.1 · p. 14
• It defines Lipschitz functions and α-approximate and α-approximate projective isometries for use in subsequent analyses.An α-approximate isometry has operator norm within α of one and lies within α of an exact isometry with the same column space.Source: §2.1 · p. 15

Access definitions

• Query access provides entry queries, while SQ(v) additionally samples indices from D_v(i)=|v(i)|^2/∥v∥^2 and exposes the associated query, sampling, and norm costs.For matrices, SQ(A) applies SQ access to every row and to the vector of row norms.Source: §3 · pp. 15, 16, 18

Oversampling

• ϕ-oversampling replaces the exact importance distribution with an efficiently accessible dominating distribution, enabling rejection sampling with acceptance probability 1/ϕ.The oversampling vector satisfies ∥ṽ∥^2=ϕ∥v∥^2 and |ṽ(i)|^2≥|v(i)|^2 for every index.Source: §3 · p. 16
• Given SQϕ(v), rejection sampling recovers samples from D_v with probability at least 1−δ and estimates ∥v∥ to multiplicative error ν using costs scaling with ϕ sqϕ(v) and logarithmic confidence factors.This makes f_sq(v)=ϕ sqϕ(v) log(1/δ) the relevant per-sample complexity measure for approximate outputs.Source: §3 · pp. 16–17

Compositional access

• Sampling and query access is closed under small linear combinations, with a cancellation factor ϕ=τ(Σ_t∥λ_t v_t∥^2)/∥Σ_tλ_t v_t∥^2 that captures norm loss.The same compositional principle extends to matrix linear combinations, while outer products multiply oversampling factors and add the component access costs.Source: §3 · pp. 17–18

Matrix access

• For matrices, SQϕ(A) provides row-wise sampling and sampling from row norms, and it implies access to the vectorized matrix by sampling a row and then an entry within that row.The framework also supports outer products and linear combinations of matrices, with explicit oversampling and query-cost compositions.Source: §3 · p. 18

Access implementations

• The alias-method data structure yields SQ access with constant sampling, query, and norm costs after linear preprocessing, turning an O(T sq(A)) quantum-inspired algorithm into O(nnz(A)+T) standard-model time.A dynamic QRAM-style structure instead gives q(A)=O(1), s(A)=O(log mn), and n(A)=O(1), while supporting entry updates in O(log mn).Source: §3 · pp. 19–20

Uniformity assumption

• Under a uniformity assumption, entry-query access to v and max_i |v(i)|^2 ≤ β/n yield SQ_ϕ(v) with ϕ = β/∥v∥^2 and sq_ϕ(v) = O(1).The construction uses the vector with all entries √(β/n) as the oversampling bound; querying entries in superposition also enables quantum-state preparation.Source: §3 · p. 21

Sparsity assumption

• For an s-sparse matrix with efficiently computable nonzero locations and entries bounded by c, uniform sampling over nonzeros provides SQ_ϕ(A) with ϕ = c^2s/m and explicit oversampling vectors.The construction sets ã(i) := c√s and uses row vectors containing c at nonzero positions, optionally adding dummy zeros; analogous sparse-access assumptions appear in QML and Hamiltonian simulation [HHL09].Source: §3 · p. 21

CT states

• Computationally tractable (CT) states are vectors with SQ(ψ) and sq(ψ) = polylog(n), including product, Fourier-transformed product, polynomial-bond-dimension matrix-product, stabilizer, and matchgate-circuit states [VdN11].Van den Nest introduced the CT-state notion in 2009 and provided efficient sampling and query-access examples [VdN11].Source: §3 · p. 21

4 Matrix sketches

• Sampling and query access generate implicit matrix sketches that reduce dimensionality approximately while enabling dimension-independent computation of sketched expressions.The sketch is represented by sampled row indices and normalization factors, and chained sketches can produce small matrices suitable for computing matrix functions.Source: §4 · pp. 21–22
• An importance sampling sketch samples rows according to their squared ℓ2 norms, while ϕ-oversampling uses bounding row norms from SQϕ(A).Rows are independently sampled and rescaled according to the selected distribution.Source: §4 · p. 21
• With r ≥ 2ϕ^2 log(2/δ) samples, sketching preserves sampling and query access for SA and (SA)† with probability at least 1−δ, using oversampling at most 2ϕ.When ϕ = 1, the corresponding access guarantees hold for all r.Source: §4 · p. 22

4.1 Approximation results

• Given sampling and query access, subsampling provides unbiased estimators for X†Y with Frobenius- and spectral-norm error bounds, including improved spectral dependence when X = Y.The framework uses variance bounds and Chebyshev-style amplification, with the X = Y case replacing a Frobenius-based dependence by one involving ∥X∥∥X∥F.Source: §4.1 · pp. 23–25
• Matrix-product approximation yields approximate closure of oversampling and query access under products, enabling approximate singular values of A from the singular values of SAT.The singular-value approximation follows by translating matrix-product norm-error bounds into singular-value-error bounds.Source: §4.1 · pp. 24–25
• The same sampling tools estimate vector inner products, trace inner products, and expectation values, and can convert importance sketches into approximate projective isometries.These procedures extend the basic inner-product estimator to higher-order tensor inner products and support later applications.Source: §4.1 · p. 26

Even singular value transformation

• The main result approximates f(A†A) by R†UR + f(0)I using an even singular value transformation based on Gilyén, Su, Low, and Wiebe [GSLW19].The decomposition uses sketches derived from SQϕ(A), with U obtained from a function of the sketched matrix.Source: §5 · p. 27

Theorem 5.1 assumptions

• Theorem 5.1 requires f and (f(x)−f(0))/x to be Lipschitz on a spectrum-enlarged domain, with approximation parameters ε and δ and either Frobenius or operator norm.The domain includes intervals around the squared singular values, and d controls the available room for approximation.Source: §5 · p. 27

Implementation

• The sketches S and T† are obtained by importance sampling, after which querying C and computing the sketched matrix function determine the implementation cost.For the applications discussed, the final matrix-function computation dominates the runtime, while the remaining costs are treated separately.Source: §5 · pp. 27–28

Restricted setting

• Under dimension-independent SQ(A), minimum singular value, norm-ratio, and Lipschitz-steepness assumptions, the resulting decomposition has dimensionless error and time bounds.The dependence on the minimum singular value arises through the bound on the Lipschitz constant of (f(x)−f(0))/x, implicitly enforcing a low-rank constraint.Source: §5 · p. 28

Error analysis and limitations

• Operator-norm analyses incur an unavoidable logarithmic term for general Lipschitz functions, although mild assumptions or particular functions can reduce or remove it.The section also provides norm bounds for the decomposition and matrix Lipschitz lemmas supporting the proof.Source: §5 · pp. 29–30

• The framework recovers prior dequantization results for recommendation systems, supervised clustering, principal component analysis, low-rank matrix inversion, support-vector machines, and low-rank semidefinite programs.Source: §6 · p. 30
• New quantum-inspired algorithms address QSVT, Hamiltonian simulation, and discriminant analysis.Source: §6 · p. 30
• Runtimes often assume known input spectral norms; otherwise, repeated norm estimation or the Frobenius norm from sampling and query access provides a suitable constant-factor bound.Source: §6 · p. 31

Theorem 6.2

• Theorem 6.2 considers a matrix A with ∥A∥F = 1, unit-norm vector b, and degree-d parity polynomial p bounded by 1 on [−1,1], using SQ access, and obtains SQϕ(v) with probability ≥1−δ.The SQ access complexities are O(log(mn)) for A and A† and O(log n) for b, with ε a sufficiently small constant.Source: §6.1 · p. 31

QRAM comparison

• In the QRAM model of [GSLW19], the classical procedure is only polynomially slower than QSVT and therefore provides no exponential quantum speedup for this task.The comparison applies because QRAM supplies the required sampling access, while both methods depend on polynomial degree, output norm, and logarithmic dimension factors.Source: §6.1 · p. 32

Density operators

• The same argument dequantizes QSVT for density operators ρ=A†A when A is available through structured classical sampling and query access.Since Tr(ρ)=1, ∥A∥F=1 and p(QV)(ρ)=r(QV)(A) for r(x)=p(x^2), reducing the case to Theorem 6.2.Source: §6.1 · p. 32

Proof mechanism

• The construction relies on polynomial smoothness and dimension-independent approximations of transformed matrix products, using low-rank sketches and ℓ2-norm sampling to build the output query structure.The smoothness bounds are controlled by degree, with the stated generic bounds potentially loose; the paper recommends application-specific main results for faster algorithms.Source: §6.1 · pp. 32–33

Access models

• Remark 6.4 argues that allowing QSVT access to A† instead of A does not restore an exponential advantage, because SQ(A) can simulate approximate sampling access for A†.The simulation constructs B with ∥B−A†∥≤ε∥A∥ with probability at least 1−δ, with details deferred to Appendix A.Source: §6.1 · p. 34

Comparison

• The framework yields a simpler and faster variant of Tang’s dequantization [Tan19] of the quantum recommendation system of Kerenidis and Prakash [KP17].The analysis avoids passing through the low-rank approximation guarantee of Frieze, Kannan, and Vempala, and improves on the previous runtime up to polylog(m, n) terms [CGJ19, Theorem 27].Source: §6.2 · p. 35

Problem formulation

• The recommendation task is to sample a product for user i from a preference matrix A using sampling and query access, up to total-variation error δ.Formally, the target distribution is based on Aσ,η, with ||Aσ,η − A||F ≤ ε||A||F.Source: §6.2 · p. 35

Method

• The algorithm writes the target low-rank approximation as A·t(A†A), approximates t(A†A) by some R†UR, and samples each resulting row using the described sampling techniques.Aσ,η keeps singular components with value ≥σ(1+η), sets those with value <σ(1−η) to zero, and leaves the middle range unspecified, allowing a family of matrices with error η.Source: §6.2 · p. 35

Runtime and guarantees

• Under 0 < ε ≲ ||A||/||A||F and η ≤ 0.99, Corollary 6.7 gives a classical algorithm for the recommendation-sampling problem.For the recommendation application, η = 1/6; exact sampling makes total-variation error arise only from failure probability.Source: §6.2 · pp. 35, 37

Unconditional extension

• Without assumptions on A, choosing σ = ε||A||F and η = 1/2 gives || − A|| ≲ ε||A||F and enables sampling or vector products in dimension-independent time.The output supports SQϕ(Â(i, ·)) and, more generally, products of  with a vector; the guarantee is described as myopic for individual rows.Source: §6.2 · p. 37

Problem formulation

• Supervised clustering assigns a new point to the cluster whose centroid is nearest, by estimating its squared distance to each centroid.The distance is represented as ∥wM∥2 for a suitable matrix M and weight vector w.Source: §6.3 · p. 37

Classical dequantization

• The dequantized algorithm solves Problem 6.9 by approximating (wM)(wM)T to additive ε error with probability at least 1 −δ [Tan21].The algorithm assumes sampling and query access to the data, matching the quantum-input setting.Source: §6.3 · p. 37

Runtime comparison

• The corresponding quantum algorithm has a quadratically faster runtime, ignoring polylog(n, d) factors [LMR13] [Tan21].The comparison concerns the clustering procedure reproduced from the swap-test dequantization of [Tan21].Source: §6.3 · pp. 37–38

Method

• The inner product is estimated by flattening tensor representations of u and v, obtaining SQ(u) from SQ(M), and applying the inner-product protocol.Sampling u uses row-norm distributions for indices i and k and row sampling for index j, while queries evaluate ui,j,k from M and the row norms.Source: §6.3 · p. 38

Quantum-inspired PCA

• The classical quantum-inspired approach solves this low-rank PCA problem, although the quantum PCA protocol is not exactly dequantized.This targets the only useful poly-logarithmic-time low-rank application suggested for quantum PCA by Lloyd, Mohseni, and Rebentrost [LMR14].Source: §6.4 · pp. 38–39

Problem formulation

• The low-rank PCA problem is to estimate the top k eigenvalues and approximate their eigenvectors with probability at least 1 −δ.The runtime must depend on condition-number and spectral-gap parameters to avoid degeneracy conditions.Source: §6.4 · p. 38

Complexity

• The method improves significantly over prior work [Tan21, Theorem 8] and has runtime independent of input dimension under the stated sampling assumptions.Its tame piecewise-linear derivatives avoid the quadratic and cubic condition-number overheads associated with thresholded inverse functions.Source: §6.4 · p. 39

Algorithm

• The algorithm first estimates eigenvalues from an importance-sampled submatrix whose singular values approximate those of X, then applies smooth step functions and the main theorem to construct rank-one RUR decompositions.The resulting decomposition has the form R†¯fi(CC†)R = ˆviˆv†i, yielding an eigenvector estimate with sampling and query access.Source: §6.4 · pp. 39–40

Guarantees

• The eigenvalue estimates satisfy the required accuracy with probability at least 1 −δ, and the eigenvector approximation guarantee holds simultaneously for all k components.The proof obtains the simultaneous guarantee by assigning failure probability δ/k to each component.Source: §6.4 · pp. 39–40

Matrix inversion and principal component regression

• The framework handles approximately low-rank matrix inversion by computing a thresholded pseudoinverse on a well-conditioned subspace, yielding principal component regression.This generalizes prior low-rank inversion approaches [GLT18] [CLW18] beyond strictly low-rank matrices.Source: §6.5 · p. 41
• The thresholded inverse equals 1/λ for singular values λ ≥ σ, is zero for λ < σ(1−η), and otherwise lies in [0, σ^-1].Source: §6.5 · p. 41
• Given SQφ(A) and Q(b), the algorithm returns SQϕ(ˆx) approximating x∗ := A+σ,ηb with error at most ε∥A∥^-1∥b∥ and failure probability δ.The method rewrites the solution using a thresholded function of A†A, approximates it through an RUR decomposition, and obtains the sampled output via sampling techniques.Source: §6.5 · p. 41
• Compared with [GLT18], the result applies beyond strictly rank-k matrices, while the corresponding block-encoding quantum algorithm takes O(∥A∥F/σ) time up to polylog(m, n) factors for constant η [GSLW19, Theorem 41].[GLT18] assumes φ = 1 and has an incomparable runtime.Source: §6.5 · p. 41
• Under the worst-case error requirement ∥ˆx−x∗∥ ≤ εσ^-1∥b∥, the algorithm works with runtime smaller by a factor of κ^3 and f sqϕ(ˆx) smaller by κ.Source: §6.5 · p. 41

• The SVM formulation classifies points in R^m using a separating hyperplane with slack vector e, minimizing squared residuals under y(i)(w^T x_i + b) = 1 − e(i).The slack variables satisfy e(j) ≥ 0, allowing cases where no hyperplane satisfies all constraints exactly.Source: §6.6 · p. 43
• The framework solves the quantum-inspired SVM problem by first obtaining SQϕ(F̂) and then applying the matrix-inversion procedure from Section 6.5.This addresses a version previously claimed to be dequantized in [DBH21], whose correctness and runtime bounds are not provided here.Source: §6.6 · p. 43
• Corollary 6.17 solves Problem 6.16 for 0 < ε ≲1 and η ≤0.99, under the assumption ∥ˆF∥≤1 also made by the quantum algorithm.Source: §6.6 · p. 43
• The normalization can fail when X has too small Frobenius norm, because singular values of XX^T are then filtered out; an appendix instead computes F+ with regularization.This alternative depends on ||X|| and Fγ in the runtime rather than the original normalization behavior.Source: §6.6 · p. 44
• Corollary 6.18 guarantees |b − b̂| ≤ ε(1 + b) and ||α̂ − α|| ≤ εγ||y|| with probability at least 1 − δ.When γ^-1/2 is sufficiently large, such as O(||X||_F), and ||α|| = Ω(γ||y||), the runtime is dimension-independent.Source: §6.6 · p. 44

Algorithms

• The framework gives two Hamiltonian-simulation algorithms: one for low-rank H and another for arbitrary H, solving Problem 6.19 from SQ(H) and SQ(b).The goal is to output sampling and query access to an approximation of e^{iH}b with error ε and success probability at least 1−δ.Source: §6.7 · p. 45
• For low-rank H, Corollary 6.20 applies when ε < min(0.5, σ), where σ is the minimum singular value; for arbitrary H, Corollary 6.21 applies when ε < min(0.5, ∥H∥^3).The two regimes use different smoothness bounds for cosine and sinc functions, with the minimum-singular-value condition supporting the low-rank case and x<1 bounds supporting arbitrary H.Source: §6.7 · pp. 45–46

Runtime

• After rescaling the target error to ε∥H∥, the arbitrary-H runtime is dimensionless, whereas the alternative corollary has worse ∥H∥ scaling despite being faster when ∥H∥=1.This comparison concerns runtime dependence on the Hamiltonian norm rather than input dimension.Source: §6.7 · p. 45

Method

• The algorithm decomposes a generic function into even and odd parts, approximating each through H†H while preserving derivative-based Lipschitz bounds.Specifically, f(H) is represented as fa(H†H) + fb(H†H)H, enabling the use of the low-rank matrix-function approximation theorem.Source: §6.7 · p. 45

Extensions and related work

• For nonsparse H, a modified construction can smoothly threshold singular values below σ, while the result generalizes Ref. [RWC+20] beyond its sparse H and b setting.Ref. [RWC+20] obtains essentially the same result in the easier sparse regime, where row subsampling makes RR† dimension-independent; the present framework exposes the resulting tradeoff.Source: §6.7 · p. 48

Problem formulation

• The target is ε-feasibility for Hermitian constraint matrices satisfying −I ⪯ A^(i) ⪯ I, outputting either “infeasible” or an X ∈ S_ε when exact feasibility is possible.The formulation normalizes X to have trace 1, though this assumption can be relaxed.Source: §6.8 · p. 49

Main result

• The algorithm solves SDP ε-feasibility with success probability at least 1−δ while providing sampling and query access to a solution.The result assumes F ≥ max_j ||A^(j)||_F and F = Ω(1). Solving an SDP reduces to O(log(1/ε)) feasibility instances.Source: §6.8 · pp. 48–49

Comparison

• Compared with the prior quantum-inspired solver [CLLW20], the new algorithm handles a more general problem and greatly improves the runtime.Under the prior solver’s rank-at-most-r assumption, F ≤ √r, yielding the stated specialized complexity comparison.Source: §6.8 · p. 49

Method

• The solver applies the matrix multiplicative weights framework as a zero-sum game between proposing a feasible X and finding a violated constraint.At each round, a violating constraint j_t is identified when Tr[A^(j_t)X_t] > b_jt + ε, and the procedure updates the proposed solution.Source: §6.8 · p. 49

10 If no solution found, conclude that the SDP is infeasible and terminate the algorithm

• Trace estimation reduces to approximating Tr(e^H) and Tr(A(i)e^H), using an approximate eigendecomposition and norm-based sampling to obtain the required estimates.The proof uses Lemma 6.27 to reduce ratio estimation to additive estimates of the numerator and partition function, then applies eigenvalue transformation and trace estimation.Source: §10 · p. 52
• The trace-estimation procedure handles small-norm and large-norm regimes separately, directly computing H when advantageous and otherwise using spectral transformation with high-probability estimates.When the matrix norm is small, zero estimates can be acceptable; otherwise, Theorem 7.2 supplies a compact approximate eigendecomposition, with direct diagonalization used if its rank would exceed n.Source: §10 · pp. 52–53

6.9 Discriminant analysis

• The classical discriminant-analysis construction approximates the generalized eigenproblem for between- and within-class scatter matrices by sketching, matrix-function approximation, and eigendecomposition.It targets an approximate isometry and diagonal eigenvalue matrix for the truncated problem, without dequantizing the separate classification algorithm.Source: §6.9 · pp. 53–54
• The resulting eigenvalues satisfy |Dii − λi| ≲ ε∥B∥2/σ2, while the computed eigenvectors form an approximate isometry with the stated sampling access.The guarantee applies for ε < σ/∥B∥ and follows from approximating the relevant Hermitian positive semidefinite matrix and applying Weyl’s inequality.Source: §6.9 · pp. 54–56

Generic singular value transformation

• Theorem 7.1 extends the method to generic SVT, outputting a CUR decomposition of f(SV)(A) from SQϕ(A) and SQϕ(A†) when f(0)=0 and the derived functions satisfy Lipschitz conditions.The construction applies the main even-SVT result to g(A†A), then approximates the resulting matrix products using sampling.Source: §7 · pp. 56–57
• For strictly low-rank or relative-error settings, the generic-SVT runtime is independent of dimension; arbitrary Lipschitz functions are handled by truncating and linearly interpolating f near zero.The strictly low-rank condition uses the minimum singular value σ, while the general reduction sets σ=ε/ℓ and preserves a Lipschitz constant at most 2ℓ.Source: §7 · p. 57

Eigenvalue transformation

• For non-even f and Hermitian A, Theorem 7.2 computes a decomposition with diagonal D satisfying |D(i, i) + f(0) − f(λi)| ≤ ε for all i.Its factor NSA is an approximate isometry satisfying ∥(NSA)(NSA)† − I∥ ≤ (ε L∥A∥)3.Source: §7 · pp. 58–59
• The eigenvalue algorithm filters out small eigenvalues, computes a small truncated SVD and eigendecomposition, and transfers the resulting spectral estimates through the Lipschitz function f.Weyl’s inequality and the Lipschitz condition yield |f(λ̂_i)−f(λ_i)|≤ε, while the stated runtime depends on sampling, sketch dimensions, and small-matrix operations rather than directly on the ambient dimension.Source: §7 · pp. 59, 61, 62

• Given SQ(A), the construction produces B with ∥B − A†∥ ≤ ε∥A∥ with probability at least 1 − δ while enabling SQ_ϕ(B).The construction follows the argument from Remark 6.8 and rescales ε appropriately.Source: A Proof sketch for Remark 6.4 · p. 68
• A smooth step function applied around (ε∥A∥)^2 defines B := AR† t̄(CC†)R, whose sampled outer-product expansion provides SQ_ϕ(B) and SQ_ϕ(B†).This requires sampling and query access to the columns of AR†.Source: A Proof sketch for Remark 6.4 · pp. 68–69
• The required column access is obtained from a truncated singular-value construction, using approximate relations R†R ≈ A†A and CC† ≈ RR†.The relevant truncated component retains singular values at least ε∥A∥/2.Source: A Proof sketch for Remark 6.4 · p. 69
• Approximate orthonormality and the lower bound ∥Av∥ ≳ ε∥A∥ ensure that the constructed vectors have sufficient norm, while their entries remain queryable as linear combinations of rows of R.The proof uses ∥v∥ ≥ 1/2 and then approximates Av entrywise via an inner-product protocol.Source: A Proof sketch for Remark 6.4 · p. 69
• Choosing γ appropriately preserves both ∥B′ − A†∥ ≲ ε and the lower bound on u, after which SQ(ũ) follows from ũ(i) := 2∥A(i, ·)∥ and SQ(A).The dominating vector satisfies |ũ(i)| ≥ |u(i)|, completing access to SQ_ϕ(u).Source: A Proof sketch for Remark 6.4 · p. 69

Approximate isometries

• An α-approximate isometry can be replaced by an exact isometry with the same columnspace and operator-norm error at most α.The construction uses the singular value decomposition ˆX = UDV† and sets X = UV†.Source: B Deferred proofs · pp. 69–70

Matrix multiplication by subsampling

• Subsampling rows according to an oversampling distribution gives an unbiased estimator of X†Y, with concentration obtained from independent bounded differences via McDiarmid’s inequality.The estimator is X†S†SY, and the proof treats sampled indices as independent coordinates.Source: B Deferred proofs · pp. 70–72

Inner product estimation

• Inner products can be estimated within ε with probability at least 1−δ from SQϕ(u) and Q(v), using repeated sampling, medians, and Chebyshev and Hoeffding inequalities [Tan19, Proposition 4.2].The runtime is O(sq(u) + q(v)) times the number of samples used to create the estimator.Source: B Deferred proofs · pp. 72–73

Polynomial approximation

• Markov-Bernstein inequalities [BE95, 5.1.E.17.f] and Taylor expansions bound the rescaled polynomial and its derivative by quantities scaling as d^2 and d^4.The lemma applies to bounded degree-d parity-d polynomials on [−1,1].Source: B Deferred proofs · p. 73

Low-rank inversion

• The inversion corollary estimates b within ε(1+b) and outputs SQϕ(ˆα) with ∥ˆα−α∥≤εγ∥y∥ at probability at least 1−δ.When γ−1/2 is sufficiently large, such as O(∥X∥F), and ∥α∥ = Ω(γ∥y∥), the runtime is dimension-independent.Source: B Deferred proofs · p. 74

Partition-function perturbations

• Perturbations of Hermitian matrices’ partition functions are controlled by differentiating a trace expression, applying a trace-norm inequality, and using Grönwall’s inequality.The proof invokes the formula introduced by and also cited to [Bel97, Page 181].Source: B Deferred proofs · pp. 76–77