Pith. sign in

REVIEW 3 major objections 6 minor 63 references

On Trimming Tensor-structured Measurements and Efficient Low-rank Tensor Recovery

T0 review · 3 major / 6 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read Trimming a few measurement rows restores the geometry needed for low-rank tensor recovery.

desk verdict A useful, well-motivated paper whose central convergence claim for TrimTIHT is not yet closed: Theorem 8 controls only Delta_t, but the contraction factor also depends on rho_t, and the covering proof has a row-alignment gap. read the letter →

arxiv 2502.02843 v2 pith:4UTBCMKN submitted 2025-02-05 math.NA cs.NA

Shambhavi Suryanarayanan , Elizaveta Rebrova This is my paper · ORCID
classification math.NAcs.NA MSC 15A6965F1068W20
keywords low-ranktensorrecoveryiterativehardthresholdingface-splittingmeasurementsrestrictedisometrypropertyrowtrimmingKaczmarzmethodHOSVDrankCP
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

This paper establishes that the norm-preservation failure of memory-efficient tensor-structured measurements is not fatal to iterative low-rank recovery, provided the measurement rows are trimmed adaptively. For face-splitting measurements, it proves that no restricted-isometry-type guarantee can hold for low-rank tensors under any nontrivial compression, but that deleting the $k=\ln(8n^\phi)$ rows most aligned with a given tensor restores a pointwise bound $\sup_{\mathcal{X}\in S}|\|A_{\mathbf{x}}\mathbf{x}\|_2^2-1|\le\delta$ with essentially the same sample complexity as unstructured sub-Gaussian maps. The paper then converts this local geometry preservation into two iterative hard-thresholding algorithms, TrimTIHT and KaczTIHT, with convergence theorems and experiments on synthetic and video data. The paper argues that trimming turns a measurement class previously considered unusable for IHT-style recovery into one that is both memory-efficient and provably recoverable.

What carries the argument

Data-dependent row trimming: from a measurement matrix $A\in\mathbb{R}^{m\times n^d}$ and a vector $\mathbf{x}$, keep the $m-k$ rows with the smallest $|a_i^\top\mathbf{x}|$ and rescale them by $\sqrt{m/(m-k)}$. The load-bearing probabilistic tool is the trimmed-mean concentration bound: after deleting a logarithmic number of the largest squared alignments $\langle a_i,\mathbf{x}\rangle^2$, the trimmed empirical average concentrates with sub-Gaussian tails even though the individual terms are heavy-tailed. A covering-net argument over the HOSVD or CP low-rank sets then turns this pointwise concentration into the uniform sup bound of the main theorem. In the algorithms the same trimming is applied iteratively: TrimTIHT selects rows with the smallest residuals $|A\mathcal{X}^k-b|$, and KaczTIHT runs a reshuffled Kaczmarz pass inside each thresholding epoch.

What would settle it

Compute, for a fixed face-splitting Gaussian map on $\mathbb{R}^{20\times20\times20}$ with $m\approx4250$, the empirical supremum over a fine net of unit-norm HOSVD-rank-$(2,2,2)$ tensors of $|\|A_{\mathbf{x}}\mathbf{x}\|_2^2-1|$ after deleting $k=\ln(8n^\phi)$ rows; any net point exceeding $\delta=0.5$ would contradict the uniform bound of the main theorem. Alternatively, run TrimTIHT with a thresholding routine that achieves only the worst-case $\sqrt{d}$ accuracy and check whether the observed contraction factor exceeds the value predicted by the theorem.

Watch

Extended reading notes

Core claim

The central claim is that data-dependent row trimming restores the geometry that face-splitting measurements lack. Concretely, given a unit-norm low-rank tensor $\mathcal{X}$ with vectorization $\mathbf{x}$, remove the $k=\ln(8n^\phi)$ rows of $A$ whose inner products with $\mathbf{x}$ have the largest absolute value, rescale the remaining rows, and call the resulting matrix $A_{\mathbf{x}}$. The paper proves that with high probability this trimmed map satisfies the pointwise restricted-isometry-style inequality $|\|A_{\mathbf{x}}\mathbf{x}\|_2^2-1|\le\delta$ for all unit-norm tensors of a given HOSVD or CP rank, using $m\gtrsim\delta^{-2}(r^d+dnr)\ln(n/\delta)$ or $m\gtrsim\delta^{-2}dnr\ln(n/\delta)$ measurements respectively. It also proves a matching negative result: without trimming, for any $\alpha>0$ and any $m<n^{d(1-\alpha)}$, the probability that a rescaled face-splitting map satisfies TensorRIP over rank-1 tensors tends to zero. Together these results show that local, iterate-dependent geometry preservation can substitute for uniform TensorRIP in iterative recovery.

Load-bearing premise

Both convergence theorems assume the hard-thresholding projection keeps every iterate close to the truth: after projecting, $\|U^k-\mathcal{X}^{k+1}_1\|_F^2\le(1+\xi)^2\|U^k-\mathcal{X}^*\|_F^2$ with a small $\xi$; the low-rank routines used in practice only guarantee a worst-case $\sqrt{d}$ factor, so if a single projection step lands far from the true tensor, the contraction factor can exceed 1 and the trimming guarantees no longer imply convergence.

Editorial extensions

If this is right

  • Face-splitting measurements can be used for iterative low-rank tensor recovery despite failing TensorRIP; plain TensorIHT's failure is not a property of the measurement class itself.
  • TrimTIHT recovers low HOSVD- and CP-rank tensors from face-splitting measurements in experiments at compression levels where TIHT diverges, including a real video tensor, while keeping the storage advantage of structured measurements.
  • KaczTIHT converges linearly under sub-Gaussian measurements with sample complexity $m\gtrsim\delta^{-2}((3r)^d+dnr)\ln(d)\ln^2 m$ for HOSVD rank and the analogous CP bound, provided the thresholding projection is quasi-optimal at every iterate.
  • The deterministic analysis of TrimTIHT reduces contraction to two local quantities, $\Delta_t$ and $\rho_t$; when the trimming theorem controls $\Delta_t$ for face-splitting maps, the contraction factor is favorable, and experiments show trimming also helps control $\rho_t$.

Reading between the lines

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

  • Editorial inference: the trimming mechanism is a generic robustifier for structured sketches; deleting the largest-alignment rows should benefit other iterative tensor methods with TensorRIP requirements, such as modewise least squares or tensor subspace embeddings, although the paper demonstrates it only for IHT variants.
  • Editorial inference: because trimming deletes rows with the largest residual magnitudes, it should also confer resilience to a few corrupted measurements; adding a few adversarial outliers to $b$ and comparing TrimTIHT with plain TIHT is a direct test the paper does not run.
  • Editorial inference: the theory leaves $\rho_t$, the norm preservation on the two-point span of consecutive residuals, uncontrolled in general; a numerical study reporting $\rho_t/\Delta_t$ as a function of trimming fraction would separate the effect of trimming from the effect of step-size choice.
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.

Referee Report

3 major / 6 minor

Summary. The paper addresses low-rank tensor recovery from memory-efficient face-splitting measurements, for which global TensorRIP is known to fail. It proves a formal failure result (Proposition 1), then proposes a data-dependent row-trimming strategy and claims a local, pointwise geometry-preservation guarantee (Theorem 8). Building on this, the authors introduce two iterative hard-thresholding algorithms, TrimTIHT and KaczTIHT, and provide convergence analyses: a deterministic contraction bound for TrimTIHT (Theorem 10) and a probabilistic bound for KaczTIHT under sub-Gaussian measurements (Theorem 11). Numerical experiments on synthetic tensors and a video tensor indicate that both methods outperform vanilla TIHT, especially for face-splitting measurements.

Significance. The proposed trimming idea is genuinely interesting: replacing a global RIP assumption by a per-iterate, data-dependent normalization could be a useful technique for structured measurement ensembles. The paper also gives a clean deterministic framework for analyzing IHT variants and includes reproducible code and experiments. However, the main theoretical bridge between the trimming guarantee and the convergence of TrimTIHT is not established: Theorem 8 controls the norm of the trimmed operator on the residual used for trimming, while Theorem 10's contraction factor depends on a different vector through rho_t. In addition, the proof of Theorem 8 contains a genuine gap in the covering argument. Thus, if the missing pieces can be supplied, the paper would be a solid contribution; as it stands, the central claims are only partially supported.

major comments (3)
  1. [Section 4.2, Eqs. (17)-(19) and Remark 5] The convergence guarantee for TrimTIHT on face-splitting measurements is not established. The contraction factor in Theorem 10 depends on rho_t = ||A_t u_t||^2 / ||u_t||^2, where u_t = P_Omega_t(A_t^T A_t r_t) and Omega_t = span{r_t, r_{t+1}}. The trimming matrix A_t is chosen using r_t, but Theorem 8 only guarantees norm preservation for the specific vector r_t (i.e., it controls Delta_t, not rho_t). Since u_t is not the vector used for trimming and can be a different low-rank tensor, Proposition 1 shows that the untrimmed face-splitting map can have arbitrarily large norm distortion even on rank-one tensors, so nothing in the paper rules out rho_t >> 1. The paper's own Remark 5 concedes that rho_t is 'more challenging to control' and that only special cases and experiments support it. Consequently, Theorem 8 does not imply contraction of the TrimTIHT iteration on the main structured measurement model; the claimed connection between the local geometry-preservation result and the algorithm's convergence is missing.
  2. [Section 3.3, proof of Theorem 8] The proof of Theorem 8 contains a load-bearing gap in the covering argument. The text bounds ||A^x x - A_hat{x} hat{x}||^2 by m ||A^x - A_hat{x}||_infty^2 epsilon^2, treating A^x and A_hat{x} as if their difference is a well-defined matrix. However, A^x and A_hat{x} are submatrices of A obtained by trimming rows according to x and hat{x} respectively, so their row index sets generally differ. The matrix difference is therefore not defined entrywise on the rows that are not common to both sets. The cited order-statistic inequality from [38] applies to sorted coordinate sequences, not to matrices with different row selections. The proof needs an additional argument controlling the contribution of the symmetric difference of the trimmed index sets; as written, the covering argument does not establish Theorem 8.
  3. [Theorem 10, Eq. (17)] The statement of Theorem 10 writes the residual bound as ||R_{t+1}|| <= ( 2 sqrt(1 - (2 - mu_t rho_t) mu_t Delta_t) + sqrt(2 xi_t + xi_t^2)(1 + mu_t ||A_t||_2 sqrt(Delta_t)) )^{t+1} ||R_0||. Since the factor in parentheses depends on t, raising it to the power t+1 is not justified; the correct expression should be a product over iterations of the per-step contraction factors. This is a correctness issue in the statement of the main convergence theorem and should be fixed.
minor comments (6)
  1. [Definition 3.1] The trimmed row is written as sqrt(m/(m-k)) a_{i_j}; it should be the row vector a_{i_j}^T or the description should be adjusted to match matrix notation.
  2. [Theorem 8 and surrounding text] The informal Theorem 1 in the introduction uses notation such as ||Ayy||^2 which should be ||A_y y||^2; the formal statement is clearer, but the informal version is confusing.
  3. [Proof of Theorem 8] In the reordering of trimmed rows, the line contains a typo: '|a_hat{x}_2 x|' should presumably be '|a_hat{x}_2 hat{x}|'.
  4. [Section 5.1] The parameter mtrim for TrimTIHT is selected by optimizing over a small set of values on the test instances; this is a free parameter in the experiments and should be reported more explicitly, for example with the selected values.
  5. [Theorem 11, proof] Several small notational slips appear in the proof, such as '||X - X *||' missing subscripts and inconsistent use of X versus Vec(X); these do not affect the argument but should be cleaned up.
  6. [Notation] The paper uses 'nd' to denote n^d without defining this shorthand; given that n^d is central to the results, this should be stated explicitly to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found: the trimming theorem derives from an external concentration result and covering arguments, while the recovery analyses are conditional on explicitly stated assumptions and external TensorRIP theorems.

full rationale

After walking the paper's derivation chain, I find no circular step in the sense of a prediction reducing to a fit or to a self-citation chain. Theorem 8's trimming guarantee is built from an external trimmed-mean concentration theorem ([56, Theorem 2.17]) applied to the squared row inner products of face-splitting measurements, combined with independent entropy/covering estimates from [33] and [62]; the proof does not presuppose the norm-preservation conclusion it derives. Lemma 2 is a direct probabilistic application of that external result, and the net argument in Theorem 8 extends it uniformly without fitting any data-dependent constant. The recovery analyses are conditional on explicitly stated approximation assumptions, such as Assumption 2 (Eq. 24), and on external TensorRIP results (Theorems 5 and 6), not on the paper's own outputs. The experimental choice of mtrim is tuned, but no theoretical result uses those tuned values, so there is no fitted input renamed as a prediction. The paper candidly acknowledges in Remark 5 that the quantity rho_t appearing in the TrimTIHT contraction factor is 'more challenging to control' and is only supported by special cases and experiments; that is an honest missing proof, i.e., a correctness risk, not a circular reduction. There are no load-bearing self-citations, no imported uniqueness theorem, and no ansatz smuggled in via citation. Proposition 1 is an independent construction showing that untrimmed face-splitting maps fail TensorRIP, and Theorem 8's positive trimming result is consequently not equivalent to its inputs by construction.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

The central theoretical results rely on standard concentration and covering tools plus explicit sub-Gaussian and thresholding assumptions. No new physical or model entity is introduced. The only user-chosen number in the algorithms is the trimming budget, tuned empirically in experiments; the theorems fix it as k=ln(8n^phi).

free parameters (1)
  • mtrim (TrimTIHT trimming budget) = 5 to 80, chosen by grid search over 5 random runs in Section 5.1
    Algorithm 1 requires the number of rows to keep; experiments tune it. The theorems instead use k=ln(8n^phi), so the theoretical results do not rely on the fitted value.
assumptions (6)
  • domain assumption Ai have i.i.d. mean-zero, variance-one, sub-Gaussian entries (Theorem 8, Prop 1).
    All local geometry guarantees for face-splitting measurements are proved under this distributional model; they do not extend to arbitrary deterministic measurement ensembles.
  • standard math Trimmed-mean concentration for non-negative heavy-tailed samples (Theorem 9 from [56]) applies to squared Kronecker inner products.
    Lemma 2 invokes this external result to bound the trimmed squared norm; the fourth-moment bound for the relevant random variables is checked via Khinchine.
  • standard math Covering-number bounds for HOSVD and CP low-rank tensors from [33,62].
    Used in Theorem 8 to pass from a finite set to the full low-rank set; the bounds are taken from literature.
  • standard math Concentration for Kronecker sub-Gaussian vectors (Prop 2 from [47]) bounds row norms.
    Used in Theorem 8's net argument to control max_i ||a_i||^2.
  • ad hoc to paper Low-rank approximation Tr satisfies quasi-optimality (Eq. 20, Assumption 2 Eq. 24).
    Convergence of TrimTIHT and KaczTIHT depends on the thresholding step not pushing the iterate too far from X*. This is not established for the HOOI and CP-ALS routines used in experiments.
  • standard math 1/sqrt(m) A satisfies TensorRIP for sub-Gaussian measurement matrices (Theorems 5-6).
    KaczTIHT's proof in Theorem 11 invokes this external result to control the gradient term I-(1/m)A^T A.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Trimming Tensor-structured Measurements and Efficient Low-rank Tensor Recovery." pith.science (2026). https://pith.science/paper/4UTBCMKN

@misc{pith2026250202843,
  author       = {Pith},
  title        = {Pith review of: On Trimming Tensor-structured Measurements and Efficient Low-rank Tensor Recovery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4UTBCMKN}},
  note         = {Machine review of arXiv:2502.02843}
}
read the original abstract

In this paper, we take a step towards developing efficient hard thresholding methods for low-rank tensor recovery from memory-efficient linear measurements with tensorial structure. Theoretical guarantees for many standard iterative low-rank recovery methods, such as iterative hard thresholding (IHT), are based on model assumptions on the measurement operator, like the restricted isometry property (RIP). However, tensor-structured random linear maps -- while memory-efficient and convenient to apply -- lack good restricted isometry properties; that is, they do not preserve the norms of low-rank tensors sufficiently well. To address this, we propose local trimming techniques that provably restore point-wise geometry-preservation properties of tensor-structured maps, making them comparable to those of unstructured sub-Gaussian measurements. Then, we propose two novel versions of tensor IHT algorithms: an adaptive gradient trimming algorithm and a randomized Kaczmarz-based IHT algorithm, that efficiently recover low-rank tensors from linear measurements. We provide initial theoretical guarantees for the proposed methods and present numerical experiments on real and synthetic data, highlighting their efficiency over the original TensorIHT for low HOSVD and CP-rank tensors.

Figures

Figures reproduced from arXiv: 2502.02843 by the authors.

Figure 1
Figure 1. Effect of trimming in the recovery of HOSVD rank-(2,2,2) tensor in R 20×20×20 compressed to m = 4250 via the face-splitting product of sub-Gaussian measurements. As we can see from the plots, the observed residual error rate is better that what the theory suggests [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. Values of ρt and ∆t , such that αt < 1 for µ = 1, 0.75 and 0.5. For the smaller step sizes the range of acceptable parameters is bigger and also shifts to allow bigger distortion. Lemma 3. Let all quantities be as defined in the statement of Theorem 10, in particular, Ax∗ = b. For some x and y ∈ R n d , let ρ > 0 be such that (22) ∥At(x − y)∥ 2 2 ≤ ρ∥x − y∥ 2 2 . Then, for a function f(z) := ∥Atz − b∥ 2 2 /2, it hol… view at source ↗
Figure 3
Figure 3. Recovery from Gaussian measurements: Fraction of 50 artificially gener￾ated random tensors of a certain rank, recovered successfully using TIHT, TrimTIHT and KaczTIHT at different compression levels. The proposed methods require less measurements for successful recovery, especially for the higher ranks. 5.2. Recovery of Compressed Video Data. In this experiment, we apply our proposed methods to compress and recover … view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Recovery from Gaussian measurements: Relative error dynamic during the recovery with TIHT, KaczTIHT and TrimTIHT of the tensors of different low rank. KaczTIHT converges faster and to a lower error, especially for higher rank tensors, and TIHT starts diverging. The lin…
Figure 5
Figure 5. Figure 5: Recovery from face-splitting product of Gaussian measurements: Frac￾tion of 50 artificially generated random tensors of a certain rank, recovered success￾fully using TIHT, TrimTIHT and KaczTIHT from different levels of compression. The proposed methods enable successfu…
Figure 6
Figure 6. Figure 6: Recovery from face-splitting product of Gaussian measurements: Rela￾tive error dynamic during the recovery with KaczTIHT and TrimTIHT of the tensors of different low rank. KaczTIHT converges faster and to a lower error, especially for higher rank tensors. The lines cor…
Figure 7
Figure 7. Figure 7: (Left) Relative error of recovered Candle video dataset using KaczTIHT and TrimTIHT from Gaussian and face-splitting measurements. The tensor is of relatively high rank (9, 8, 5), the compression is to 30% of its size. TIHT method immediately diverges on the same setup…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

63 extracted references · 58 canonical work pages

  1. [38]

    Median-truncated nonconvex approach for phase retrieval with outliers

    Huishuai Zhang, Yuejie Chi, and Yingbin Liang. “Median-truncated nonconvex approach for phase retrieval with outliers”. In: IEEE Transactions on information Theory 64.11 (2018), pp. 7287–7310. 30 BIBLIOGRAPHY

    work page 2018

  2. [1]

    The approximation of one matrix by another of lower rank

    Carl Eckart and Gale Young. “The approximation of one matrix by another of lower rank”. In: Psychometrika 1.3 (1936), pp. 211–218

    1936

  3. [2]

    Angen¨ aherte Aufl¨ osung von Systemen linearer Gleichungen

    Stefan Kaczmarz. “Angen¨ aherte Aufl¨ osung von Systemen linearer Gleichungen”. In:Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat. (1937), pp. 355–357

    work page 1937

  4. [3]

    A multilinear singular value decomposition

    Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. “A multilinear singular value decomposition”. In: SIAM journal on Matrix Analysis and Applications 21.4 (2000), pp. 1253– 1278

    work page 2000

  5. [4]

    On the best rank-1 and rank-(r1, r2,..., rn) approximation of higher-order tensors

    Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle. “On the best rank-1 and rank-(r1, r2,..., rn) approximation of higher-order tensors”. In: SIAM journal on Matrix Analysis and Applications 21.4 (2000), pp. 1324–1342

    work page 2000

  6. [5]

    Construction and analysis of degenerate PARAF AC models

    Pentti Paatero. “Construction and analysis of degenerate PARAF AC models”. In: Journal of Chemometrics: A Journal of the Chemometrics Society 14.3 (2000), pp. 285–299

    work page 2000

  7. [6]

    Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information

    Emmanuel J Cand` es, Justin Romberg, and Terence Tao. “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information”. In: IEEE Trans- actions on information theory 52.2 (2006), pp. 489–509

    work page 2006

  8. [7]

    The restricted isometry property and its implications for compressed sensing

    Emmanuel J Candes. “The restricted isometry property and its implications for compressed sensing”. In: Comptes rendus. Mathematique 346.9-10 (2008), pp. 589–592

    work page 2008

Show all 63 references
  1. [8]

    The fast Johnson–Lindenstrauss transform and approximate nearest neighbors

    Nir Ailon and Bernard Chazelle. “The fast Johnson–Lindenstrauss transform and approximate nearest neighbors”. In: SIAM Journal on Computing 39.1 (2009), pp. 302–322

    2009

  2. [9]

    Tensor decompositions and applications

    Tamara G Kolda and Brett W Bader. “Tensor decompositions and applications”. In: SIAM review 51.3 (2009), pp. 455–500

    2009

  3. [10]

    A randomized Kaczmarz algorithm with expo- nential convergence

    Thomas Strohmer and Roman Vershynin. “A randomized Kaczmarz algorithm with expo- nential convergence”. In: Journal of Fourier Analysis and Applications 15.2 (2009), pp. 262– 278

    2009

  4. [11]

    A singular value thresholding al- gorithm for matrix completion

    Jian-Feng Cai, Emmanuel J Cand` es, and Zuowei Shen. “A singular value thresholding al- gorithm for matrix completion”. In: SIAM Journal on Optimization 20.4 (2010), pp. 1956– 1982

    2010

  5. [12]

    A sparse Johnson- Lindenstrauss trans- form

    Anirban Dasgupta, Ravi Kumar, and Tam´ as Sarl´ os. “A sparse Johnson- Lindenstrauss trans- form”. In: Proceedings of the forty-second ACM symposium on Theory of computing . 2010, pp. 341–350

    2010

  6. [13]

    Tensor completion for estimating missing values in visual data

    Ji Liu et al. “Tensor completion for estimating missing values in visual data”. In: IEEE transactions on pattern analysis and machine intelligence 35.1 (2012), pp. 208–220

    2012

  7. [14]

    A new truncation strategy for the higher-order singular value decomposition

    Nick Vannieuwenhoven, Raf Vandebril, and Karl Meerbergen. “A new truncation strategy for the higher-order singular value decomposition”. In: SIAM Journal on Scientific Computing 34.2 (2012), A1027–A1052

    2012

  8. [15]

    Normalized iterative hard thresholding for matrix completion

    Jared Tanner and Ke Wei. “Normalized iterative hard thresholding for matrix completion”. In: SIAM Journal on Scientific Computing 35.5 (2013), S104–S125

    2013

  9. [16]

    Sparser Johnson- Lindenstrauss transforms

    Daniel M Kane and Jelani Nelson. “Sparser Johnson- Lindenstrauss transforms”. In: Journal of the ACM (JACM) 61.1 (2014), pp. 1–23

    2014

  10. [17]

    ROP: Matrix recovery via rank-one projections

    T Tony Cai and Anru Zhang. “ROP: Matrix recovery via rank-one projections”. In: The Annals of Statistics (2015), pp. 102–138

    2015

  11. [18]

    Tensor decompositions for signal processing applications: From two- way to multiway component analysis

    Andrzej Cichocki et al. “Tensor decompositions for signal processing applications: From two- way to multiway component analysis”. In: IEEE signal processing magazine 32.2 (2015), pp. 145–163

    2015

  12. [19]

    Dimensionality reduction for k-means clustering and low rank ap- proximation

    Michael B Cohen et al. “Dimensionality reduction for k-means clustering and low rank ap- proximation”. In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015, pp. 163–172. BIBLIOGRAPHY 29

    2015

  13. [20]

    An iterative hard thresholding algorithm with improved convergence for low-rank tensor recovery

    Jos´ e Henrique de M Goulart and G´ erard Favier. “An iterative hard thresholding algorithm with improved convergence for low-rank tensor recovery”. In: 2015 23rd European Signal Processing Conference (EUSIPCO). IEEE. 2015, pp. 1701–1705

    2015

  14. [21]

    Modified distributed iterative hard thresh- olding

    Puxiao Han, Ruixin Niu, and Yonina C Eldar. “Modified distributed iterative hard thresh- olding”. In: 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE. 2015, pp. 3766–3770

    2015

  15. [22]

    Iterative hard thresholding based on ran- domized Kaczmarz method

    Zhuosheng Zhang, Yongchao Yu, and Shumin Zhao. “Iterative hard thresholding based on ran- domized Kaczmarz method”. In: Circuits, Systems, and Signal Processing 34 (2015), pp. 2065– 2075

    2015

  16. [23]

    Efficient matrix sensing using rank-1 gauss- ian measurements

    Kai Zhong, Prateek Jain, and Inderjit S Dhillon. “Efficient matrix sensing using rank-1 gauss- ian measurements”. In: Algorithmic Learning Theory: 26th International Conference, ALT 2015, Banff, AB, Canada, October 4-6, 2015, Proceedings 26 . Springer. 2015, pp. 3–18

    2015

  17. [24]

    Parallel tensor compression for large- scale scientific data

    Woody Austin, Grey Ballard, and Tamara G Kolda. “Parallel tensor compression for large- scale scientific data”. In: 2016 IEEE international parallel and distributed processing sympo- sium (IPDPS) . IEEE. 2016, pp. 912–922

    2016

  18. [25]

    Kaczmarz method for solving quadratic equations

    Yuejie Chi and Yue M Lu. “Kaczmarz method for solving quadratic equations”. In: IEEE Signal Processing Letters 23.9 (2016), pp. 1183–1187

    2016

  19. [26]

    Conjugate gradient acceleration of iteratively re-weighted least squares methods

    Massimo Fornasier et al. “Conjugate gradient acceleration of iteratively re-weighted least squares methods”. In: Computational Optimization and Applications 65 (2016), pp. 205–259

    2016

  20. [27]

    Support tensor machines for classification of hyperspectral remote sensing imagery

    Xian Guo et al. “Support tensor machines for classification of hyperspectral remote sensing imagery”. In: IEEE Transactions on Geoscience and Remote Sensing 54.6 (2016), pp. 3248– 3264

    2016

  21. [28]

    Tensors for data mining and data fusion: Models, applications, and scalable algorithms

    Evangelos E Papalexakis, Christos Faloutsos, and Nicholas D Sidiropoulos. “Tensors for data mining and data fusion: Models, applications, and scalable algorithms”. In:ACM Transactions on Intelligent Systems and Technology (TIST) 8.2 (2016), pp. 1–44

    2016

  22. [29]

    Guarantees of Riemannian optimization for low rank matrix recovery

    Ke Wei et al. “Guarantees of Riemannian optimization for low rank matrix recovery”. In: SIAM Journal on Matrix Analysis and Applications 37.3 (2016), pp. 1198–1222

    2016

  23. [30]

    Exact tensor completion using t-SVD

    Zemin Zhang and Shuchin Aeron. “Exact tensor completion using t-SVD”. In: IEEE Trans- actions on Signal Processing 65.6 (2016), pp. 1511–1526

    2016

  24. [31]

    Linked component analysis from matrices to high-order tensors: Applica- tions to biomedical data

    Guoxu Zhou et al. “Linked component analysis from matrices to high-order tensors: Applica- tions to biomedical data”. In: Proceedings of the IEEE 104.2 (2016), pp. 310–331

    2016

  25. [32]

    Tensor decompositions and data fusion in epileptic electroencephalog- raphy and functional magnetic resonance imaging data

    Borb´ ala Hunyadi et al. “Tensor decompositions and data fusion in epileptic electroencephalog- raphy and functional magnetic resonance imaging data”. In: Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 7.1 (2017), e1197

    2017

  26. [33]

    Low rank tensor recovery via iterative hard thresholding

    Holger Rauhut, Reinhold Schneider, and ˇZeljka Stojanac. “Low rank tensor recovery via iterative hard thresholding”. In: Linear Algebra and its Applications 523 (2017), pp. 220–262

    2017

  27. [34]

    Tensor decomposition for signal processing and machine learn- ing

    Nicholas D Sidiropoulos et al. “Tensor decomposition for signal processing and machine learn- ing”. In: IEEE Transactions on signal processing 65.13 (2017), pp. 3551–3582

    2017

  28. [35]

    A practical randomized CP tensor decomposition

    Casey Battaglino, Grey Ballard, and Tamara G Kolda. “A practical randomized CP tensor decomposition”. In: SIAM Journal on Matrix Analysis and Applications 39.2 (2018), pp. 876– 901

    2018

  29. [36]

    High-dimensional probability: An introduction with applications in data science

    Roman Vershynin. High-dimensional probability: An introduction with applications in data science. Vol. 47. Cambridge University Press, 2018

    2018

  30. [37]

    Sketched ridge regression: Opti- mization perspective, statistical perspective, and model averaging

    Shusen Wang, Alex Gittens, and Michael W Mahoney. “Sketched ridge regression: Opti- mization perspective, statistical perspective, and model averaging”. In: Journal of Machine Learning Research 18.218 (2018), pp. 1–50

    2018

  31. [39]

    Almost optimal tensor sketch

    Thomas D Ahle and Jakob BT Knudsen. “Almost optimal tensor sketch”. In: arXiv preprint arXiv:1909.01821 (2019)

    2019 arXiv

  32. [40]

    TTHRESH: Tensor compres- sion for multidimensional visual data

    Rafael Ballester-Ripoll, Peter Lindstrom, and Renato Pajarola. “TTHRESH: Tensor compres- sion for multidimensional visual data”. In: IEEE transactions on visualization and computer graphics 26.9 (2019), pp. 2891–2903

    2019

  33. [41]

    Iterative hard thresholding for low-rank recovery from rank-one projections

    Simon Foucart and Srinivas Subramanian. “Iterative hard thresholding for low-rank recovery from rank-one projections”. In: Linear Algebra and its Applications 572 (2019), pp. 117–134

    2019

  34. [42]

    Tensorly: Tensor learning in python

    Jean Kossaifi et al. “Tensorly: Tensor learning in python”. In: Journal of Machine Learning Research 20.26 (2019), pp. 1–6

    2019

  35. [43]

    Relative error tensor low rank approxima- tion

    Zhao Song, David P Woodruff, and Peilin Zhong. “Relative error tensor low rank approxima- tion”. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM. 2019, pp. 2772–2789

    2019

  36. [44]

    Oblivious sketching of high-degree polynomial kernels

    Thomas D Ahle et al. “Oblivious sketching of high-degree polynomial kernels”. In: Proceed- ings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM. 2020, pp. 141–160

    2020

  37. [45]

    Stochastic iterative hard thresholding for low-Tucker-rank tensor recovery

    Rachel Grotheer et al. “Stochastic iterative hard thresholding for low-Tucker-rank tensor recovery”. In: 2020 Information Theory and Applications Workshop (ITA). IEEE. 2020, pp. 1– 5

    2020

  38. [46]

    On recoverability of randomly compressed tensors with low CP rank

    Shahana Ibrahim, Xiao Fu, and Xingguo Li. “On recoverability of randomly compressed tensors with low CP rank”. In: IEEE Signal Processing Letters 27 (2020), pp. 1125–1129

    2020

  39. [47]

    Concentration inequalities for random tensors

    Roman Vershynin. “Concentration inequalities for random tensors”. In: Bernoulli 26 (2020), pp. 3139–3162

    2020

  40. [48]

    Regularized Kaczmarz algorithms for tensor recovery

    Xuemei Chen and Jing Qin. “Regularized Kaczmarz algorithms for tensor recovery”. In: SIAM Journal on Imaging Sciences 14.4 (2021), pp. 1439–1471

    2021

  41. [49]

    Lower memory oblivious (tensor) subspace embeddings with fewer ran- dom bits: modewise methods for least squares

    Mark A Iwen et al. “Lower memory oblivious (tensor) subspace embeddings with fewer ran- dom bits: modewise methods for least squares”. In: SIAM Journal on Matrix Analysis and Applications 42.1 (2021), pp. 376–416

    2021

  42. [50]

    Faster Johnson–Lindenstrauss transforms via Kronecker products

    Ruhui Jin, Tamara G Kolda, and Rachel Ward. “Faster Johnson–Lindenstrauss transforms via Kronecker products”. In: Information and Inference: A Journal of the IMA 10.4 (2021), pp. 1533–1562

    2021

  43. [51]

    Tensor random projection for low memory dimension reduction

    Yiming Sun et al. “Tensor random projection for low memory dimension reduction”. In: arXiv preprint arXiv:2105.00105 (2021)

    2021 arXiv

  44. [52]

    Iterative hard thresholding with adaptive regu- larization: Sparser solutions without sacrificing runtime

    Kyriakos Axiotis and Maxim Sviridenko. “Iterative hard thresholding with adaptive regu- larization: Sparser solutions without sacrificing runtime”. In: International Conference on Machine Learning. PMLR. 2022, pp. 1175–1197

    2022

  45. [53]

    On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations

    Lu Cheng et al. “On block accelerations of quantile randomized Kaczmarz for corrupted systems of linear equations”. In: Inverse Problems 39.2 (2022), p. 024002

    2022

  46. [54]

    Quantile-based iterative methods for corrupted systems of linear equa- tions

    Jamie Haddock et al. “Quantile-based iterative methods for corrupted systems of linear equa- tions”. In: SIAM Journal on Matrix Analysis and Applications 43.2 (2022), pp. 605–637

    2022

  47. [55]

    Near-isometric properties of Kronecker-structured random tensor embeddings

    Qijia Jiang. “Near-isometric properties of Kronecker-structured random tensor embeddings”. In: Advances in Neural Information Processing Systems 35 (2022), pp. 10191–10202

    2022

  48. [56]

    Optimal statistical estimation: sub-Gaussian properties, heavy- tailed data, and robust-ness

    Zoraida Fern´ andez Rico. “Optimal statistical estimation: sub-Gaussian properties, heavy- tailed data, and robust-ness”. PhD thesis. Instituto de Matem´ atica Pura e Aplicada (IMPA), 2022

    2022

  49. [57]

    Iterative singular tube hard thresholding algorithms for tensor recov- ery

    Rachel Grotheer et al. “Iterative singular tube hard thresholding algorithms for tensor recov- ery”. In: arXiv preprint arXiv:2304.04860 (2023)

    2023 arXiv

  50. [58]

    Fast and Low-Memory Compressive Sensing Algorithms for Low Tucker-Rank Tensor Approximation from Streamed Measurements

    Cullen Haselby et al. “Fast and Low-Memory Compressive Sensing Algorithms for Low Tucker-Rank Tensor Approximation from Streamed Measurements”. In:arXiv preprint arXiv:2308.13709 (2023). BIBLIOGRAPHY 31

    2023 arXiv

  51. [59]

    Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery

    Cullen A Haselby et al. “Modewise operators, the tensor restricted isometry property, and low-rank tensor recovery”. In: Applied and Computational Harmonic Analysis 66 (2023), pp. 161–192

    2023

  52. [60]

    Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints

    Halyun Jeong and Deanna Needell. “Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints”. In: arXiv preprint arXiv:2304.10123 (2023)

    2023 arXiv

  53. [61]

    Low-rank tensor estimation via Riemannian Gauss-Newton: Statistical optimality and second-order convergence

    Yuetian Luo and Anru R Zhang. “Low-rank tensor estimation via Riemannian Gauss-Newton: Statistical optimality and second-order convergence”. In: The Journal of Machine Learning Research 24.1 (2023), pp. 18274–18321

    2023

  54. [62]

    Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications

    Yifan Zhang and Joe Kileel. “Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications”. In: arXiv e-prints (2023), arXiv–2311

    2023

  55. [63]

    Tensor Decompositions for Data Science

    Grey Ballard and Tamara G Kolda. Tensor Decompositions for Data Science . Cambridge University Press, 2025

    2025

Pith tools

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