Superfast 1-Norm Estimation

Soo Go; Victor Y. Pan

REVIEW 5 major objections 5 minor 40 references

Superfast 1-Norm Estimation

T0 review · 5 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A k-sparsified sign vector keeps LAPACK's 1-norm estimator accurate while cutting work to sublinear in n^2.

desk verdict A simple, honestly presented sparsification heuristic for 1-norm estimation with promising but narrow evidence; the accuracy comparison against LAPACK is missing. read the letter →

arxiv 2505.20528 v1 pith:Q5E6HFTC submitted 2025-05-26 math.NA cs.NA

Soo Go , Victor Y. Pan This is my paper · ORCID

classification math.NAcs.NA MSC 65F3565Y2068Q25

keywords 1-normestimationsublinearcostalgorithmsrandomizedsparsificationLAPACKnormestimatorcross-approximationlow-rankapproximationmatrixsuperfast

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims that the 1-norm of a dense n-by-n matrix can be estimated as accurately as the standard LAPACK estimator while reading far fewer than all $n^{2}$ entries. The trick is to run LAPACK's recursive estimator but k-sparsify every probe vector: keep k randomly chosen coordinates and zero out the rest before multiplying by the matrix. In tests on dense real-world matrices (image restoration, gravity, single-layer potential) and several synthetic classes, the estimates stayed within a small factor of the true norm for k as low as 1, 3, or 10 out of 1024 coordinates. Because the estimate is always the 1-norm of one column of the matrix, it is guaranteed to be a lower bound; accuracy means this lower bound is close. A sympathetic reader would care because 1-norm estimates underpin condition-number estimation, and sublinear cost would make them feasible for matrices too big to fit in memory.

What carries the argument

The load-bearing object is the k-sparsified sign vector \bar{w}: w = sign(u) is a vector of ±1 signs of the current candidate column, and k of its coordinates are chosen uniformly at random and kept while the rest are set to 0. The identity ||M e_j||_1 ≥ |x^T e_j| with x = M^T \bar{w} drives the search: the coordinate of x with maximum absolute value names the next column to try, and the next candidate's 1-norm is compared against the current one. Since the output is always ||M e_j||_1 for a single column, every estimate is a proven lower bound on ||M||_1. Two refinements carry the argument: a scaling factor α = n/k in the acceptance test, and initialization or refinement by maxvol 1, a rank-1 cross-approximation step that finds a row-column pair with large |m_{i,j}|.

What would settle it

Construct an n×n matrix whose first column has 1-norm 1 with a single large entry 1 in row 1 and zeros elsewhere, and whose remaining columns are small (for example, all entries 2ε). For k=1, the sparsified sign vector of any candidate column has probability about 1/n of keeping the one large coordinate; when it misses, x = M^T \bar{w} has its largest coordinate in a small column, and the algorithm can terminate after one iteration with an estimate near 2nε instead of 1. Repeating over random seeds should produce a large fraction of poor underestimates for large n.

Watch

Extended reading notes

Core claim

The central discovery is that randomized sparsification of the sign vector in LAPACK's 1-norm estimator preserves its accuracy on typical real-world matrices while reducing the per-iteration work from a full matrix-vector product to kn entry touches. The algorithm maintains a candidate column u = M e_j, forms w = sign(u), keeps k random coordinates of w to get \bar{w}, computes x = M^T \bar{w}, and moves to the column j with largest |x_j|. The move is accepted only if the new column's 1-norm strictly increases, so the search monotonically improves a lower bound and terminates in at most s iterations. The paper reports accuracy ratios (true norm over estimate) close to 1 across Shaw, Gravity, single-layer potential, fast-decay, slow-decay, Cauchy, single-small-singular-value, single-large-singular-value, and random matrices, for k = 1, 3, 10 with TOL = 10; incorporating cross-approximation steps (maxvol 1) further sharpens the estimates, in one case bringing Shaw from 1.1296 to 1.0000.

Load-bearing premise

The algorithm assumes that after randomly keeping only k coordinates of the sign vector, the resulting sparse vector still points toward a column whose 1-norm is close to the largest column 1-norm; for a matrix with its large-norm column concentrated in very few entries, the sparse sample can miss it and the search can lock onto a poor underestimate.

Editorial extensions

If this is right

For a dense n×n matrix, the estimator touches at most (s+2)kn entries and (s+2)kn flops plus O(ns) auxiliary work, so for k s of size much smaller than n the total work is sublinear in n^2, making norm estimation feasible for matrices that do not fit in memory.
Because ||M||_1 = ||M^T||_∞, the same algorithms estimate the ∞-norm at the same sublinear cost.
The output is always a lower bound on ||M||_1, so the method can be combined with upper-bound devices to certify condition numbers from below.
Adding one maxvol 1 step before or during the search improves accuracy on matrices where the plain sparsified search is weaker, and costs only comparisons among visible entries.
The LRA-based p-norm estimator of Section 4.3 gives relative errors below 2.5 on the tested classes, offering a route to p-norm estimation for p ≥ 1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The empirical regularity suggests a formal conjecture: for matrices drawn from distributions with low spikiness or small coherence, a k-sparsified sign vector retains enough overlap with the maximal column that the search terminates near the true norm; quantifying this would turn the heuristic into a theorem.
The same sparsify-then-multiply trick could be applied to other recursive vector-matrix estimators, such as power iteration for the spectral norm, where sparse probes may yield cheaper eigenvalue estimates on incoherent data.
In practice, the choice of k could be made adaptive: run with k=1 and k=10 and accept the larger lower bound, giving a cheap sanity check for coherent cases.
A testable extension: apply Algorithm 2.2 to sparse or diagonally dominant matrices, where the heavy coordinates of the sign vector are predictable; the paper's Appendix A suggests sparse-structured inputs are exactly where the method should be stress-tested.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague, quick take: this is a genuinely simple idea for sublinear 1-norm estimation—randomly sparsify the sign vectors inside LAPACK's estimator—and the empirical results on the authors' test set are surprisingly good. Mean ratios of true norm to estimate are mostly between 1.00 and 1.16, and the algorithms are clearly described. The paper is also honest that there is no formal accuracy guarantee and that worst-case inputs defeat any sublinear algorithm (Appendix A). That's worth something.

What's new: the k-sparsified variants of LAPACK (Algs. 2.1, 2.2, 3.2) and the use of maxvol for initialization. The computational cost analysis is straightforward: reading O(kn) entries per matrix-vector product, so for small k the whole process is sublinear. Extensions to p-norms and rectangular matrices are plausible. I believe the authors' claim that no prior superfast norm estimators have been published; the connection between superfast LRA and norm estimation is a reasonable gap to fill.

The soft spots: the paper never reports LAPACK's own estimator on the same matrices, so the claim 'as accurate as LAPACK's' is unsubstantiated. It also doesn't report variability over the 1000 runs—only means—so we can't see if the algorithm occasionally returns a terrible underestimate. The test suite is narrow: three real-world matrices (all from Regularization Tools, all low numerical rank) plus synthetic classes, all 1024x1024. No code or data. And the key reference [13] for the LRA machinery is 'to appear,' which makes the extensions hard to check.

None of these are fatal. The core algorithm is simple enough that a competent numerical analyst can reproduce it from the paper, and the idea is plausible enough to deserve a proper look. I'd send this to a serious referee, but expect a request for the LAPACK baseline, a boxplot or min/max of the ratios, and a public implementation. If the authors can demonstrate on a broader corpus that the sparsified estimator stays within a few percent of LAPACK while reading far fewer entries, that's a practical result worth having.

For me: I'd bring it to a reading group discussion, but I wouldn't cite it in my own work until the missing evidence is in.

Referee Report

5 major / 5 minor

Summary. The paper proposes several heuristic algorithms for estimating the induced 1-norm of a matrix (and hence its infinity-norm) at sublinear cost. The main idea is to modify LAPACK's 1-norm estimator by randomly k-sparsifying the sign vectors before each multiplication by M or M^T, so that only O(kn) entries of the n-by-n matrix are read per iteration. Algorithm 2.1 implements the basic sparsified estimator, Algorithm 2.2 adds a scaling parameter alpha, Algorithm 3.2 incorporates maxvol-based cross-approximation steps, and Algorithm 4.1 estimates p-norms via low-rank approximation. The authors report operation counts and present numerical experiments on three 1024-by-1024 real-world dense matrices (Shaw, Gravity, SLP) and several synthetic matrix classes. Because every output is the 1-norm of an actual column of M, all estimates are lower bounds on the true 1-norm; the reported mean ratios ||M||_1/est are close to 1 for most tested classes. The paper explicitly acknowledges the absence of formal worst-case guarantees and gives a hard example family in Appendix A.

Significance. Randomized sparsification for norm estimation is a simple and potentially useful idea. If the empirical behavior holds on a broader corpus, the algorithms would offer a superfast alternative to LAPACK's estimator for large matrices, with the attractive property that the estimates are always valid lower bounds. The cost analysis is straightforward, and the experimental results on the tested matrices are encouraging. The main limitations are that the paper provides no formal characterization of when the sparsified search works, the real-world test set is narrow, no direct comparison with LAPACK's own estimator is reported, and no code is provided. The paper is honest about the absence of proofs and about the hard-input examples in Appendix A, which is a strength; nevertheless, the broader claims in the abstract and Section 1.2 need to be calibrated to the evidence actually presented.

major comments (5)

[Section 1.2 and Section 5] The statement that the estimates are 'consistently as accurate as LAPACK's' is not supported by the reported experiments. Section 5.7 uses the LAPACK routine dlange only to compute the exact 1-norm, and no results from LAPACK's iterative 1-norm estimator (for example, ?lacon or its successor) are reported for Algorithms 2.1, 2.2, or 3.2. If the intended claim is parity with LAPACK, a direct baseline on the same matrices and the same 1000-run protocol is required; otherwise the sentence should be removed or rephrased as accuracy relative to the exact norm.
[Section 5.1, Tables 5.1-5.3] The real-world evidence is limited to three 1024-by-1024 dense matrices from a single toolbox (Shaw, Gravity, SLP), two of which are padded from 1000-by-1000 and all of which have low numerical rank. This is too narrow to support the unqualified 'real-world matrices' claim in the abstract. The paper should either qualify the claim to the tested classes or expand the corpus (for example, larger sizes, rectangular matrices, sparse or non-low-rank matrices, and matrices from other application domains), and should report variability over the 1000 runs, such as quantiles, minima, or worst-case ratios, since the tables report only means.
[Section 3.2] The sentence 'maxvol 1 outputs a column index j such that m||M e_j||_1 >= ||M||_1' is false in general. A 2-by-2 counterexample is M = [[1,0],[0,1000]]: with initial column j=1, maxvol 1 outputs i=1, j=1, giving ||M e_1||_1 = 1 while ||M||_1 = 1000, so m||M e_1||_1 = 2 < 1000. This claim motivates the maxvol-based initialization of Algorithm 3.2 and should be corrected, or the intended inequality should be stated precisely.
[Section 2.3] The complexity estimate omits the cost of computing u := M e_j at Stage 3 of the algorithms. Since e_j is 1-sparse, this multiplication reads n entries and costs n flops per iteration, so the total is (s+2)kn + sn entries and flops, not (s+2)kn as written. The asymptotic conclusion for s << n/k is unaffected, but the displayed cost formula is inaccurate.
[Abstract and Section 1.2] Because the selection of the next column is driven by a k-sparsified sign vector and no condition on the matrix is established, all three sparsified algorithms are heuristics. The paper says failure is limited to 'a narrow class of coherent inputs' but never defines coherence or narrowness, and Appendix A only shows the existence of hard instances. Please either define and characterize the purported failure class, even empirically, or rephrase the claims so that they apply only to the tested matrix classes.

minor comments (5)

[Figures 3-6, 8, 9] The captions do not explain what the plotted markers, ranges, and whiskers represent. Please state explicitly whether the figures show means, medians, quantiles, or all 1000 runs, and define the 'Accuracy' axis.
[Section 5.2] The sentence 'Figs. 3 and 4 show estimates for 1-norm of M within a factor of 2 in 2, 3, or 4 iterations' is unclear; it should be rephrased to describe what is actually plotted and what conclusion the reader should draw.
[Section 5.1] Shaw and Gravity are padded from 1000-by-1000 to 1024-by-1024; the text should specify whether the padding adds zero rows, zero columns, or both, because the padding structure affects the column norms and the behavior of the sparsified products.
[References] Reference [13] is cited as 'to appear' without a title or venue; it should be completed, or the citation should be replaced by a publicly available version.
[Appendix C] Algorithm C.1 depends on 'Alg. 2.2a', which is described in prose rather than as a numbered algorithm; a complete pseudocode listing of Alg. 2.2a would make the adaptive scaling procedure reproducible.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the estimates are exact 1-norms of actual columns of M compared against the true norm, and the self-citations are background material rather than load-bearing premises.

full rationale

The central claim is empirical: Algorithms 2.1, 2.2, and 3.2 output the quantity ||M e_j||_1 for some column index j, and the paper measures accuracy as the ratio ||M||_1 / estimate against the exact norm. Because every returned value is the 1-norm of a real column of M, the output cannot be forced by construction, and the comparison to the true norm is independent of any fitted parameter. The scaling parameter alpha in Algorithm 2.2 is fixed as the sparsification ratio n/k, and it affects only the stopping rule; it is not fed back into the estimate itself. Appendix C's adaptive search for alpha also does not change the fact that the output remains a genuine column norm, so no fitted input is being renamed as a prediction. The self-citations to [13] and [31-33] are used for low-rank approximation tools and Abridged SRHT matrices in the context of Algorithm 4.1, not as justification for the main sparsified 1-norm estimation claim, and the paper explicitly reports that the LRA-based route was inferior to the sparsified approach. No uniqueness theorem or ansatz is imported from the authors' prior work to force the choice of algorithm. The paper honestly concedes in Appendix A that no sublinear algorithm can work on all inputs, and in Section 1.2 that formal support for the real-world performance is an open challenge; these admissions are limitations on the empirical claim, not evidence of circularity. The main weakness is that the real-world accuracy claim rests on only three dense 1024-by-1024 test matrices and an uncharacterized sparsification heuristic, but that is a correctness or empirical-support concern, not a circularity concern under the stated rules.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central estimator has no formal derivation; it is an empirical heuristic. Its accuracy rests on unproven assumptions about input coherence and on hand-chosen parameters. The LRA-based variant additionally depends on the not-yet-published algorithms of reference [13].

free parameters (4)

k (sparsification parameter) = 1, 3, 10 in the tests
The number of coordinates kept when sparsifying vectors. It controls the entries touched per matrix-vector product (about kn) versus accuracy. Chosen by hand; no theory fixes it.
alpha (scaling factor in Algorithm 2.2) = n/k, e.g., 102.4 for n=1024, k=10; adaptively adjusted in Appendix C
Used only in the stopping condition of Algorithm 2.2 to compensate for the shrinkage of ||x||_1 after k-sparsification. The choice is heuristic and not derived; adaptive search tends to end near n/k.
TOL (maximum iterations) = 10 in all numerical tests
Controls the maximum number of update attempts before the algorithm is forced to stop. Larger TOL improves chances but raises cost; chosen by hand.
r (rank of LRA in Algorithm 4.1) = 8, 16, 32, 64 in the tests
Rank of the low-rank approximation used for p-norm estimation. Affects both cost and accuracy of the secondary LRA-based estimator.

assumptions (4)

domain assumption Random k-sparsification of sign vectors preserves enough information about column norms for typical real-world matrices.
Central heuristic in Secs. 2.1 and 2.2. No formal condition is given, and the paper concedes worst-case failure in Appendix A.
domain assumption LAPACK's 1-norm estimator is an accurate estimator of the true 1-norm.
The algorithms are modifications of the LAPACK estimator recalled in Sec. 1.6; they inherit the assumption that its sign-vector search locates near-maximal columns when the full vectors are used.
domain assumption Maxvol 1 (cross-approximation) finds a large entry of the matrix in few steps.
Algorithm 3.2 uses maxvol 1 to seed candidate columns. Its worst-case cost is O(mn) comparisons (Sec. 3.1), so superfast behavior relies on empirical performance, not a guarantee.
domain assumption The tested matrix classes are representative of real-world matrices.
Three real-world matrices (Shaw, Gravity, SLP) plus six synthetic families are used. The broad claim of consistent accuracy on real-world matrices extrapolates from this small sample.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Superfast 1-Norm Estimation." pith.science (2026). https://pith.science/paper/Q5E6HFTC

@misc{pith2026250520528,
  author       = {Pith},
  title        = {Pith review of: Superfast 1-Norm Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Q5E6HFTC}},
  note         = {Machine review of arXiv:2505.20528}
}

read the original abstract

A matrix algorithm is said to be superfast (that is, runs at sublinear cost) if it involves much fewer scalars and flops than the input matrix has entries. Such algorithms have been extensively studied and widely applied in modern computations for matrices with low displacement rank and more recently for low-rank approximation of matrices, even though they are known to fail on worst-case inputs in the latter application. We devise novel superfast algorithms that consistently produce accurate 1-norm estimates for real-world matrices and discuss some promising extensions of our surprisingly simple techniques. With further testing and refinement, our algorithms can potentially be adopted in practical computations.

Figures

Figures reproduced from arXiv: 2505.20528 by the authors.

**Figure 2.** ) if X ∈ C m×k , Y ∈ C k×ℓ , Z ∈ C ℓ×n , r ≤ min{k, ℓ}, and E := M − XY Z ≈ 0 in context. (4.1) M = X Y Z + E [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Output errors of Alg. 2.1. 5.3 Test Results for Algorithm 2.2 We ran 1000 tests for Alg. 2.2 for α = n/k under the same setup as for Alg. 2.1. Figs. 5 and 6 show the test results. More refined data in [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Figures from the paper (6 more)

**Figure 4.** Figure 4: Number of iterations of Alg. 2.1. and the percent of the difference in average relative errors, ∆err =: 100 × errAlg2.1 − errAlg2.2 errAlg2.1 where err := mean − 1. These data show that both algorithms yield similar output accuracy. ' "& $( #$ ( !' (…

**Figure 5.** Figure 5: Output errors of Alg. 2.2. 5.4 Test Results for Algorithm 3.1 We ran 1000 tests for Alg. 3.1 for each type of input matrices. We measured output errors by the ratio |M| est where est denoted the estimated norm |M| of (3.2) returned by the algorithm. Figs. 7(a) and 7(b)…

**Figure 6.** Figure 6: Number of iterations of Alg. 2.2. Input Matrix k=1 k=3 k=10 Alg. 2.1 Alg. 2.2 ∆err% Alg. 2.1 Alg. 2.2 ∆err% Alg. 2.1 Alg. 2.2 ∆err% Shaw 1.1296 1.1407 -8.54 1.0422 1.0438 -3.93 1.0239 1.0276 -15.80 Gravity 1.0536 1.0553 -3.13 1.0300 1.0270 9.94 1.0248 1.0231 6.87 SLP 1…

**Figure 7.** Figure 7: Output errors and the number of C-A steps of Alg. 3.1 [PITH_FULL_IMAGE:figures/full_fig_p013_7.png]

**Figure 8.** Figure 8: Accuracy (error estimates) of Alg. 3.2. 5.7 Test Results for Algorithm 4.1 We performed 1000 tests of Alg. 4.1 and display the results for p = 1 and r = 8, 16, 32, 64. We computed rank-r approximation {X, Y, Z} of the input matrices by using their random sketches FM an…

**Figure 9.** Figure 9: Number of Iterations of Alg. 3.2. Input Matrix k=1 k=3 k=10 Alg. 2.1 Alg. 3.2 ∆err% Alg. 2.1 Alg. 3.2 ∆err% Alg. 2.1 Alg. 3.2 ∆err% Shaw 1.1296 1.0000 99.98 1.0422 1.0000 99.93 1.0239 1.0000 99.87 Gravity 1.0536 1.0508 5.22 1.0300 1.0282 5.85 1.0248 1.0247 0.49 SLP 1.0…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

40 extracted references · 30 canonical work pages

[13]

Pan, to appear

Soo Go, Qi Lian, V.Y. Pan, to appear

work page
[1]

Anderson, Z

E. Anderson, Z. Bai, C. H. Bischof, S. Blackford, J. W. Dem mel, J. J. Dongarra, J. J. Du Croz, A. Greenbaum, S. J. Hammarling, A. McKenney, D. C. Sorensen, LAPACK Users’ Guide, 3rd ed., SIAM, Philadelphia, PA, 1999. http://www.netlib.org/lapack/lug/lapack lug.html

work page 1999
[2]

DOI: 10.1007/s10444-024-10196-7

Kenneth Allen, Ming-Jun Lai, Zhaiming Shen, Maximal Vol ume Matrix Cross Approximation for Image Compression and Least Squares Solu tion, Advances in Computational Mathematics , 5, 2024. DOI: 10.1007/s10444-024-10196-7. Also arXiv:2309.1740, December, 2024. 18

work page arXiv 2024
[3]

Boyd, The power method for ℓp norms, Lin

David W. Boyd, The power method for ℓp norms, Lin. Algebra Appl., 9, 95–101, 1974

work page 1974
[4]

Bakshi, D

A. Bakshi, D. P. Woodruﬀ, Sublinear Time Low-Rank Approximation of Distance Ma- trices, Procs. 32nd Intern. Conf. Neural Information Processing Syste ms (NIPS’18), 3786–3796, Montr´ eal, Canada, 2018

work page 2018
[5]

Cohen, Nearly tight oblivious subspace embed dings by trace inequali- ties, 27th ACM-SIAM Symp

Michael B. Cohen, Nearly tight oblivious subspace embed dings by trace inequali- ties, 27th ACM-SIAM Symp. on Discrete Algorithms (SODA 2016) , 278 –287, 2016. doi:10.1137/1.9781611974331.ch21.8

work page doi:10.1137/1.9781611974331.ch21.8 2016
[6]

Shabarish Chenakkod, Micha/suppress l Derezinski, Xiaoyu Dong,Mark Rudelson, Optimal embedding dimension for sparse subspace embeddings, arXiv :2311.10680 (2023), re- vised June 2024

arXiv 2023
[7]

Epperly, Joel A

Yifan Chen, Ethan N. Epperly, Joel A. Tropp, Robert J. Web ber, Randomly pivoted Cholesky: Practical approximation of a kernel matrix with f ew entry evaluations, arXiv 2207.06503, December 2023

arXiv 2023

Show all 40 references

[8]

Coralia Cartis, Jan Fiala, Zhen Shao, Hashing embedding s of optimal dimension, with applications to linear least squares, arXiv:2105.118 15 (2021)

2021
[9]

K. L. Clarkson, D. P. Woodruﬀ, Numerical linear algebra in the streaming model, 41st Annual ACM Symposium on Theory of Computing, 205 - 214, 2009. https://doi.org/10.1145/1536414.1536445

2009
[10]

K. L. Clarkson, D. P. Woodruﬀ, Low-Rank Approximation an d Regression in In- put Sparsity Time, J. ACM , 63, 6 , Article 54 (January 2017), 45 pages. DOI: http://dx.doi.org/10.1145/3019134

2017 doi
[11]

J. D. Dixon, Estimating extremal eigenvalues and condi tion numbers of matrices. SIAM Journal on Numerical Analysis , 20(4), 812-814 (1983) https://doi.org/10.1137/0720053

1983 doi
[12]

G. H. Golub, C. F. Van Loan, Matrix Computations , The Johns Hopkins University Press, Baltimore, Maryland, 2013 (fourth edition)

2013
[14]

Goreinov, I

S. Goreinov, I. Oseledets, D. Savostyanov, E. Tyrtyshn ikov, N. Zamarashkin, How to Find a Good Submatrix, in Matrix Methods: Theory, Algorithms, Applications (ded- icated to the Memory of Gene Golub, edited by V. Olshevsky and E. Tyrtyshnikov), pages 247–256, World Scientiﬁc ...

2010
[15]

N. J. Higham, FORTRAN codes for estimating the one-norm of a real or complex matrix, with applications to condition estimation. ACM Trans. Math. Softw . 14, 4 , 381–396 (Dec. 1988). https://doi.org/10.1145/50063.214386

1988
[16]

N. J. Higham, Accuracy and Stability in Numerical Analysis , SIAM, Philadelphia, 2002 (second edition)

2002
[17]

Halko, P

N. Halko, P. G. Martinsson, J. A. Tropp,Finding Structu re with Randomness: Prob- abilistic Algorithms for Constructing Approximate Matrix Decompositions, SIAM Review, 53, 2 , 217-288, 2011. 19

2011
[18]

Nicholas J. Higham, Fran¸ coise Tisseur, A Block Algori thm for Matrix 1-Norm Es- timation, with an Application to 1-Norm Pseudospectra, SIAM Journal on Matrix Analysis and Applications, 21, 4 (2000) https://doi.org/10.1137/S0895479899356080

2000 doi
[19]

Jonathan Katz, Yehuda Lindell, Introduction to Modern Cryptography , CRC Press, Chapman and Hall Books, 2014 (third edition), June 24, 2025 ( fourth edition), 640 pages, 44 B/W Illustrations, ISBN 9781032496795

2014
[20]

Kapralov, H

M. Kapralov, H. Lawrence, M. Makarov, Cameron Musco, K. Sheth, Toeplitz Low- Rank Approximation with Sublinear Query Complexity, ACM-SIAM Symposium on Discrete Algorithms (SODA’23), 2023. doi.org/10.1137/1.9781611977554.ch159

2023 doi
[21]

Liberty, Accelerated Dense Random Projections, PhD Thesis, Yale Univ., 2009

E. Liberty, Accelerated Dense Random Projections, PhD Thesis, Yale Univ., 2009

2009
[22]

Linear Algebra Appl

Mikhail Lepilov, Jianlin Xia, Rank-structured Approx imation of Some Cauchy Ma- trices with Sublinear Complexity, Numer. Linear Algebra Appl. , 31, 1, January 2024. https://doi.org/10.1002/nla.2526

2024 doi
[23]

M. W. Mahoney, Randomized Algorithms for Matrices and D ata, Foundations and Trends in Machine Learning , NOW Publishers, 3, 2 , 2011. arXiv:1104.5557, 2011. (Abridged version in: Advances in Machine Learning and Data Mining for Astron- omy, edited by M. J. Way et al., pp. 647...

2011 arXiv
[24]

Martinsson, J

P.-G. Martinsson, J. A. Tropp. Randomized numerical li near algebra: Foundations and algorithms. Acta Numerica, 29, 403–572, 2020

2020
[25]

Cameron Musco, D. P. Woodruﬀ, Sublinear Time Low-Rank Ap proximation of Pos- itive Semideﬁnite Matrices, IEEE 58th Annual Symposium on Foundations of Com- puter Science (FOCS), 672–683, 2017

2017
[26]

Yuji Nakatsukasa, Fast and stable randomized low-rank matrix approximation, arXiv:2009.11392, Sept 2020

2009 arXiv
[27]

Probabilistic estimation of the rank-1 Cr oss-Approximation accuracy, arxiv:1706.10285, June 2017

A.I Osinsky. Probabilistic estimation of the rank-1 Cr oss-Approximation accuracy, arxiv:1706.10285, June 2017

2017 arXiv
[28]

Osinsky, N

A.I. Osinsky, N. L. Zamarashkin, Pseudo-skeleton Appr oximations with Better Ac- curacy Estimates, Linear Algebra and Its Applications , 537, 221-249, 2018

2018
[29]

Pan, Structured Matrices and Polynomials: Uniﬁed Superfast Alg orithms, Birkh¨ auser/Springer, Boston/New York (2001) doi: 10.1007/978-1-4612-0129-8

V.Y. Pan, Structured Matrices and Polynomials: Uniﬁed Superfast Alg orithms, Birkh¨ auser/Springer, Boston/New York (2001) doi: 10.1007/978-1-4612-0129-8

2001 doi
[30]

Pan, Transformations of Matrix Structures Work Ag ain, Linear Algebra and Its Applications, 465, 1-32, 2015

V.Y. Pan, Transformations of Matrix Structures Work Ag ain, Linear Algebra and Its Applications, 465, 1-32, 2015. doi: 10.1016/j.laa.2014.09.004

2015 doi
[31]

V. Y. Pan, Q. Luan, J. Svadlenka, L. Zhao, Primitive and C ynical Low Rank Ap- proximation, Preprocessing and Extensions, arXiv 1611.01 391, November 2016

2016
[32]

V. Y. Pan, Q. Luan, J. Svadlenka, L. Zhao, Superfast Accu rate Low Rank Approxi- mation, arXiv:1710.07946, October 2017

2017 arXiv
[33]

V. Y. Pan, Q. Luan, J. Svadlenka, L. Zhao, CUR Low Rank App roximation at Sublinear Cost, arXiv:1906.04112, June 2019. 20

1906 arXiv
[34]

Simoncini, Computational Methods for Linear Matrix Equations, SIAM Review, 58 (3) 377 – 441, 2016

V. Simoncini, Computational Methods for Linear Matrix Equations, SIAM Review, 58 (3) 377 – 441, 2016. doi:10.1137/130912839

2016 doi
[35]

G. W. Stewart, Matrix Algorithms, Vol. I: Basic Decompositions, SIAM, 1998

1998
[36]

Shi, D.P

X. Shi, D.P. Woodruﬀ, Sublinear time numerical linear al gebra for structured matri- ces, Procs. the AAAI Conference Artiﬁcial Intelligence , 33 (01) , 4918-4925, (2019) DOI: https://doi.org/10.1609/aaai.v33i01.33014918

2019 doi
[37]

Tropp, Robert J

Joel A. Tropp, Robert J. Webber, Randomized algorithms for low-rank matrix ap- proximation: Design, analysis, and applications, arXiv: 2 306.12418 (2023)

2023
[38]

J. A. Tropp, A. Yurtsever, M. Udell, V. Cevher, Practica l Sketching Algorithms for Low-rank Matrix Approximation, SIAM J. Matrix Anal. , 38, 4 , 1454-1485, 2017. Also arXiv:1609.00048, January 2018

2017 arXiv
[39]

J. A. Tropp, A. Yurtsever, M. Udell, V. Cevher, Streamin g Low-Rank Matrix Ap- proximation with an Application to Scientiﬁc Simulation,SIAM J. on Scientiﬁc Com- puting, 41, pp. A2430–A2463, 2019. Also arXiv:1902.08651, submitted Feb 2019

2019 arXiv
[40]

Udell, A

M. Udell, A. Townsend, Why are big data matrices approximately of low rank?, SIAM J. Math. Data Sci. , 1, 144-160, 2019. 21

2019

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [13]

Pan, to appear

Soo Go, Qi Lian, V.Y. Pan, to appear

work page

[2] [1]

Anderson, Z

E. Anderson, Z. Bai, C. H. Bischof, S. Blackford, J. W. Dem mel, J. J. Dongarra, J. J. Du Croz, A. Greenbaum, S. J. Hammarling, A. McKenney, D. C. Sorensen, LAPACK Users’ Guide, 3rd ed., SIAM, Philadelphia, PA, 1999. http://www.netlib.org/lapack/lug/lapack lug.html

work page 1999

[3] [2]

DOI: 10.1007/s10444-024-10196-7

Kenneth Allen, Ming-Jun Lai, Zhaiming Shen, Maximal Vol ume Matrix Cross Approximation for Image Compression and Least Squares Solu tion, Advances in Computational Mathematics , 5, 2024. DOI: 10.1007/s10444-024-10196-7. Also arXiv:2309.1740, December, 2024. 18

work page arXiv 2024

[4] [3]

Boyd, The power method for ℓp norms, Lin

David W. Boyd, The power method for ℓp norms, Lin. Algebra Appl., 9, 95–101, 1974

work page 1974

[5] [4]

Bakshi, D

A. Bakshi, D. P. Woodruﬀ, Sublinear Time Low-Rank Approximation of Distance Ma- trices, Procs. 32nd Intern. Conf. Neural Information Processing Syste ms (NIPS’18), 3786–3796, Montr´ eal, Canada, 2018

work page 2018

[6] [5]

Cohen, Nearly tight oblivious subspace embed dings by trace inequali- ties, 27th ACM-SIAM Symp

Michael B. Cohen, Nearly tight oblivious subspace embed dings by trace inequali- ties, 27th ACM-SIAM Symp. on Discrete Algorithms (SODA 2016) , 278 –287, 2016. doi:10.1137/1.9781611974331.ch21.8

work page doi:10.1137/1.9781611974331.ch21.8 2016

[7] [6]

Shabarish Chenakkod, Micha/suppress l Derezinski, Xiaoyu Dong,Mark Rudelson, Optimal embedding dimension for sparse subspace embeddings, arXiv :2311.10680 (2023), re- vised June 2024

arXiv 2023

[8] [7]

Epperly, Joel A

Yifan Chen, Ethan N. Epperly, Joel A. Tropp, Robert J. Web ber, Randomly pivoted Cholesky: Practical approximation of a kernel matrix with f ew entry evaluations, arXiv 2207.06503, December 2023

arXiv 2023