Pith. sign in

REVIEW 4 minor 88 references

Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements

T0 review · 0 major / 4 minor · reviewed 2026-08-08 · deepseek-v4-flash

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

Pith's one-line read The paper claims that $N \ge C r d$ symmetric rank-one measurements recover every order-$\ell$ tensor of symmetric rank at most $r$ with probability one, for any fixed $\ell$ and any log-concave distribution, making the sample complexity…

desk verdict The reader's main objection to the covering argument does not hold up; the paper is essentially sound and deserves serious review. read the letter →

arxiv 2502.05134 v1 pith:YDTI7VSM submitted 2025-02-07 math.ST cs.ITmath.ITmath.PRstat.MLstat.TH

Eren C. K{i}z{i}ldağ This is my paper · ORCID
classification math.STcs.ITmath.ITmath.PRstat.MLstat.TH MSC 15A6962H1262C20
keywords symmetricrank-onemeasurementslow-ranktensorrecoveryrankminimizationlog-concavedistributionsanti-concentrationorthogonalpolynomialssamplecomplexitytwo-layerpolynomialnetworks
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 claims that the sample complexity of recovering an order-$\ell$ tensor from symmetric rank-one measurements is $\Theta(rd)$: with $N \ge C r d$ measurements for any constant $C > 2\ell^2$, symmetric rank minimization uniquely recovers every tensor of symmetric rank at most $r$, assuming only that the measurement vectors have entries drawn independently from any log-concave distribution. A matching lower bound shows that any estimator needs roughly $\tilde{\Omega}(d r^{0.98})$ measurements, so the upper bound is optimal up to a sub-polynomial factor in $r$. The result matters because this measurement model is exactly the teacher-student model for two-layer neural networks with polynomial activation $t^\ell$, so the theorem says such networks are identifiable from $\Theta(rd)$ samples without any norm constraints on the weights. It also exposes a sharp contrast with unstructured empirical risk minimization, which requires about $d^\ell$ samples.

What carries the argument

The argument is carried by the symmetric rank minimization program (7), whose analysis reduces to a geometric statement about the unit sphere $\zeta_S(2r)$ of tensors with symmetric rank at most $2r$: with probability one, no nonzero tensor in this sphere vanishes on all $N$ measurement tensors. The proof bounds the covering number of $\zeta_S(2r)$ by embedding it into the larger CP-rank sphere $\zeta_{CP}(2r)$ and using a covering-number bound for CP-rank tensors. It then controls the probability that a fixed candidate tensor is near-orthogonal to all measurements with an anti-concentration inequality for the degree-$\ell$ polynomial $\langle T, X^{\otimes \ell}\rangle$ of a log-concave random vector, and supplies the required second-moment lower bound through an orthogonal-polynomial expansion of the measurement polynomial. A union bound over the net, with $N$ chosen so that the net-entropy term is dominated by the anti-concentration exponent, makes the failure probability tend to zero as the net mesh goes to zero.

What would settle it

For $T=e_1\otimes e_2\otimes e_3-e_2\otimes e_1\otimes e_3$, the calculation $\mathbb{E}\langle T, X^{\otimes 3}\rangle^2=0$ for any iid product distribution shows the second-moment bound cannot hold on all CP-rank-2 points, so the proof must demonstrate that an $\epsilon$-net of $\zeta_S(2r)$ of the claimed cardinality can be chosen with bounded symmetric rank; exhibiting a net of that size forced to contain such a point would falsify the argument.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 2.1: for fixed order $\ell$, any log-concave distribution $D$, and any $C>2\ell^2$, the symmetric rank minimization program (7) recovers every order-$\ell$ tensor $T^*$ with $\mathrm{rank}_S(T^*)\le r$ from $N\ge C r d$ measurements $Y_i=\langle T^*, X_i^{\otimes \ell}\rangle$ with probability one. The proof works by showing that with such $N$ there is no nonzero unit-Frobenius-norm tensor of symmetric rank at most $2r$ that is orthogonal to all measurement tensors, and the same argument gives identifiability of two-layer polynomial networks of width $r$. A companion lower bound, proved with a packing bound and a standard entropy-based information-theoretic inequality, shows that every estimator fails once $N = O(d r^{0.98}/(\log r + \ell\log(Bd)))$, so the $rd$ rate is essentially the information-theoretic limit.

Load-bearing premise

The argument assumes that every point in the approximating grid used to cover the unit sphere of low-rank tensors has a symmetric decomposition into few rank-one pieces; the paper proves the needed second-moment bound only for such tensors, but the covering bound it relies on does not guarantee the grid points are of that kind.

Editorial extensions

If this is right

  • The sample bound $N=\Theta(rd)$ is the right answer for this measurement model: recovery is possible at $C r d$ measurements for every log-concave distribution, and impossible for arbitrary estimators below roughly $d r^{0.98}$.
  • Two-layer polynomial networks with activation $t^\ell$ and width $r$ are information-theoretically identifiable from $\Theta(rd)$ input-label pairs, with no bounded-norm assumptions on the hidden weights.
  • Any consistent estimator, including computationally efficient ones, must ask for at least $\tilde{\Omega}(d r^{1-\gamma})$ measurements for any $\gamma>0$, providing a benchmark for future algorithms.
  • Unstructured empirical risk minimization is far less sample-efficient: at fewer than $\binom{d+\ell-1}{\ell}$ measurements it admits zero-training-error models with arbitrarily large generalization error.
  • The results are noiseless and information-theoretic, so they delineate the fundamental limits before computational tractability is imposed.

Reading between the lines

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

  • If the upper and lower bounds are both tight up to the $r^{0.02}$ gap, then the true minimax sample complexity is probably exactly $\Theta(rd)$; a natural test is whether the lower-bound exponent $0.98$ can be pushed to $1$.
  • The proof's dependence on $\ell^2$ is likely removable: the quadratic term comes from matching the covering entropy $2r\ell d \log(1/\epsilon)$ against the anti-concentration exponent $N/\ell$, so any sharper covering bound or anti-concentration estimate would reduce it.
  • Because the upper bound places no norm restrictions on the tensor, it suggests that in the noiseless teacher-student model weight magnitudes are irrelevant for identifiability; in noisy models, by contrast, weight scale should reappear through the signal-to-noise ratio.
  • A natural extension is to check whether a polynomial-time method, such as a convex relaxation of (7), can match $\Theta(rd)$; the information-theoretic threshold here provides the target.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. The paper studies the sample complexity of exactly recovering a low symmetric-rank tensor from symmetric rank-one measurements Y_i = <T*, X_i^⊗ℓ> with X_i having i.i.d. log-concave entries. The main result (Theorem 2.1) states that for fixed order ℓ and any log-concave D, N ≥ C r d with C > 2ℓ^2 measurement vectors suffice to recover every rank-≤r symmetric tensor via the symmetric rank minimization program (7), with probability one. The proof covers ζS(2r) by a net, applies Carbery–Wright anti-concentration with a lower bound on the second moment from an orthogonal-polynomial expansion, and takes ε→0. A converse (Theorem 2.5) gives an Ω(d r^{0.98}/log r) lower bound via Fano's inequality using a packing construction. Implications for two-layer polynomial networks are discussed (Theorem 2.2).

Significance. If correct, the result is a near-optimal Θ(rd) sample complexity for structured tensor recovery, improving on the Θ(d^ℓ) dimension of the symmetric tensor space, and it holds for the broad class of log-concave distributions without norm constraints on the underlying vectors. The proof is self-contained except for the external Carbery–Wright inequality and the ZK23 covering-number bound; no free parameters are fitted, and the lower bound is explicit. The potential concern that the ε-net points might not lie in ζS(2r) is resolved by Definition 4.1, which requires the net to be a subset of the set being covered; the CP-rank covering is used only for cardinality. The remaining issues are presentational.

minor comments (4)
  1. [§4.3, Eq. (11)] The denominator in the Carbery–Wright bound is written as Ξ^{1/ℓ}, but since E[P(X)^2] ≥ Ξ implies sqrt(E[P^2]) ≥ Ξ^{1/2}, the correct factor is Ξ^{1/(2ℓ)}. This typo does not affect the ε-exponent that drives the conclusion, but the displayed inequality is inconsistent with Theorem 4.6.
  2. [§4.3, after Eq. (20)] The tail term P[max_i ||X_i||_2 > log^{1/ℓ}(1/ε)] is stated to vanish as ε→0 without proof. For log-concave D this follows from standard sub-exponential tail bounds; please include a short argument for completeness.
  3. [Abstract] The abstract contains a typo: 'Low-Ran k' should be 'Low-Rank'.
  4. [§4.3, Eq. (15)] The notation 'min_{T_hat ∈ ζ′}' is slightly imprecise: ζ′ is a finite set, and the minimum is over its elements. Rewriting as 'min_{T_hat ∈ ζ′}' is fine, but the subsequent union bound in (18) should be phrased with an explicit enumeration of the net points to avoid confusion with the covering-number exponential bound.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is self-contained, with external benchmarks supporting the covering and anti-concentration steps.

full rationale

No load-bearing circularity was found. The central recovery claim (Theorem 2.1) is derived through Proposition 3.1, whose proof uses three independent ingredients: (i) the covering-number estimate for ζS(2r) obtained in Lemma 4.5 from the external result [ZK23, Theorem 3.1] via the monotonicity Lemma 4.3; (ii) the Carbery–Wright anti-concentration bound [CW01, Theorem 8]; and (iii) the second-moment lower bound Proposition 4.7, proved from orthogonal polynomial theory with respect to the log-concave product measure. The potential concern that net points used in the union bound might not have bounded symmetric rank is resolved by the paper's own Definition 4.1, which requires an ε-net for ζS(2r) to be a subset of ζS(2r); hence every net point has symmetric rank at most 2r and Proposition 4.7 applies to each of them. Lemma 4.5 is used only to bound the cardinality |ζ'|, not to supply net points outside ζS(2r). The lower bound (Theorem 2.5) is based on an explicit packing construction (Proposition 2.4) and Fano's inequality, with no fitted parameters presented as predictions. The self-citations ([Kız22], [EGKZ20], [GKZ24]) appear only in motivational and related-work passages, not in the derivation of the main theorems. Minor presentation issues, such as the unexpanded tail term P[max_i ||X_i||_2 > log^{1/ℓ}(1/ε)] and a bracketing typo in the denominator of equation (11), are correctness/presentation concerns and do not amount to circularity. The derivation chain is therefore self-contained against external benchmarks.

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

No free parameters are fitted to data; the constants C and Ξ are analytic. The paper introduces no new physical or probabilistic entities. The assumptions are standard for the proof technique, except for the unstated net-point symmetric-rank property, which is the gap identified in the soundness score.

assumptions (5)
  • domain assumption The measurement vectors X_i have i.i.d. entries drawn from a log-concave distribution D with a density.
    Stated in Section 1 (Distributional Assumption). Needed for Carbery-Wright (Theorem 4.6) and for finiteness of moments used in orthogonal polynomial constructions.
  • standard math The Carbery-Wright inequality (Theorem 4.6) holds for P(X) = ⟨T, X^⊗ℓ⟩ with degree ℓ and log-concave X.
    Cited as [CW01, Theorem 8] and used in Sections 4.2-4.3 to control anti-concentration of the random polynomial measurements.
  • standard math The covering-number bound for CP-rank tensors in Theorem 4.4 (from [ZK23]) is correct and applies to ζ_CP(2r).
    Used in Lemma 4.5 to bound |ζ'|. The paper does not reproduce the proof, so the main result depends on this external preprint.
  • standard math The orthonormal polynomial family {P_α} is a basis for L²(D^⊗d) (Proposition 5.2).
    Invoked in the proof of Proposition 4.7 (Section 5) to expand ⟨T, X^⊗ℓ⟩; justified by reference to Lalley's notes and a Math StackExchange post.
  • ad hoc to paper The ε-net ζ' used in Section 4.3 can be chosen so every net point has bounded symmetric rank, so that Proposition 4.7 applies.
    Unstated in the proof: Lemma 4.5 only yields a covering via ζ_CP(2r), whose points need not have bounded symmetric rank. This is the identified load-bearing gap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements." pith.science (2026). https://pith.science/paper/YDTI7VSM

@misc{pith2026250205134,
  author       = {Pith},
  title        = {Pith review of: Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YDTI7VSM}},
  note         = {Machine review of arXiv:2502.05134}
}
read the original abstract

In this paper, we investigate the sample complexity of recovering tensors with low symmetric rank from symmetric rank-one measurements. This setting is particularly motivated by the study of higher-order interactions and the analysis of two-layer neural networks with polynomial activations (polynomial networks). Using a covering numbers argument, we analyze the performance of the symmetric rank minimization program and establish near-optimal sample complexity bounds when the underlying distribution is log-concave. Our measurement model involves random symmetric rank-one tensors, which lead to involved probability calculations. To address these challenges, we employ the Carbery-Wright inequality, a powerful tool for studying anti-concentration properties of random polynomials, and leverage orthogonal polynomials. Additionally, we provide a sample complexity lower bound based on Fano's inequality, and discuss broader implications of our results for two-layer polynomial networks.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

88 extracted references · 78 canonical work pages

  1. [1]

    16, 164001

    Alia Abbara, Antoine Baker, Florent Krzakala, and Lenka Zdeborov \'a , On the universality of noiseless linear estimation with respect to the measurement matrix, Journal of Physics A: Mathematical and Theoretical 53 (2020), no. 16, 164001

    2020

  2. [2]

    4, 944--966

    Talal Ahmed, Haroon Raja, and Waheed U Bajwa, Tensor regression using low-rank and sparse tucker decompositions, SIAM Journal on Mathematics of Data Science 2 (2020), no. 4, 944--966

    2020

  3. [3]

    Martin Argerami, Orthonormal basis for product l^2 space, Mathematics Stack Exchange, 2012, https://math.stackexchange.com/q/105486 (version: 2024-07-30)

    2012

  4. [4]

    Noga Alon and Joel H Spencer, The probabilistic method, John Wiley & Sons, 2016

    2016

  5. [5]

    Arnab Auddy, Dong Xia, and Ming Yuan, Tensor methods in high dimensional data analysis: Opportunities and challenges, arXiv preprint arXiv:2405.18412 (2024)

    work page Pith review arXiv 2024

  6. [6]

    Richter, Springer, 2006, pp

    Mark Bagnoli and Ted Bergstrom, Log-concave probability and its applications, Rationality and Equilibrium: A Symposium in Honor of Marcel K. Richter, Springer, 2006, pp. 217--241

    2006

  7. [7]

    3, 976--988

    Sergey G Bobkov and Gennadiy P Chistyakov, On concentration functions of random variables, Journal of Theoretical Probability 28 (2015), no. 3, 976--988

    2015

  8. [8]

    Kush Bhatia, Prateek Jain, Parameswaran Kamalaruban, and Purushottam Kar, Consistent robust regression, Advances in Neural Information Processing Systems 30 (2017)

    2017

Show all 88 references
  1. [9]

    8, 1943--1948

    Sumanta Basu, Karl Kumbier, James B Brown, and Bin Yu, Iterative random forests to discover predictive and stable high-order interactions, Proceedings of the National Academy of Sciences 115 (2018), no. 8, 1943--1948

    2018

  2. [10]

    Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin, Deep learning: a statistical viewpoint, Acta numerica 30 (2021), 87--201

    2021

  3. [11]

    7, 4872--4894

    Jess Banks, Cristopher Moore, Roman Vershynin, Nicolas Verzelen, and Jiaming Xu, Information-theoretic bounds and phase transitions in clustering, sparse pca, and submatrix localization, IEEE Transactions on Information Theory 64 (2018), no. 7, 4872--4894

    2018

  4. [12]

    1, 294--311

    Christian F Beckmann and Stephen M Smith, Tensorial extensions of independent component analysis for multisubject fmri analysis, Neuroimage 25 (2005), no. 1, 294--311

    2005

  5. [13]

    Jacob Bien, Jonathan Taylor, and Robert Tibshirani, A lasso for hierarchical interactions, Annals of statistics 41 (2013), no. 3, 1111

    2013

  6. [14]

    1, 345--368

    Xuan Bi, Xiwei Tang, Yubai Yuan, Yanqing Zhang, and Annie Qu, Tensors in statistics, Annual review of statistics and its application 8 (2021), no. 1, 345--368

    2021

  7. [15]

    4, 1956--1982

    Jian-Feng Cai, Emmanuel J Cand \`e s, and Zuowei Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on optimization 20 (2010), no. 4, 1956--1982

    2010

  8. [16]

    3, 1254--1279

    Pierre Comon, Gene Golub, Lek-Heng Lim, and Bernard Mourrain, Symmetric tensors and symmetric tensor rank, SIAM Journal on Matrix Analysis and Applications 30 (2008), no. 3, 1254--1279

    2008

  9. [17]

    3, 1--37

    Emmanuel J Cand \`e s, Xiaodong Li, Yi Ma, and John Wright, Robust principal component analysis?, Journal of the ACM (JACM) 58 (2011), no. 3, 1--37

    2011

  10. [18]

    Pierre Comon, Lek-Heng Lim, Yang Qi, and Ke Ye, Topology of tensor ranks, Advances in Mathematics 367 (2020), 107128

    2020

  11. [19]

    Jian-Feng Cai, Lizhang Miao, Yang Wang, and Yin Xian, Provable near-optimal low-multilinear-rank tensor recovery, arXiv preprint arXiv:2007.08904 (2020)

    2020 arXiv

  12. [20]

    6, 925--936

    Emmanuel J Candes and Yaniv Plan, Matrix completion with noise, Proceedings of the IEEE 98 (2010), no. 6, 925--936

    2010

  13. [21]

    6, 111--119

    Emmanuel Candes and Benjamin Recht, Exact matrix completion via convex optimization, Communications of the ACM 55 (2012), no. 6, 111--119

    2012

  14. [22]

    2, 489--509

    Emmanuel J Cand \`e s, Justin Romberg, and Terence Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on information theory 52 (2006), no. 2, 489--509

    2006

  15. [23]

    12, 4203--4215

    Emmanuel J Candes and Terence Tao, Decoding by linear programming, IEEE transactions on information theory 51 (2005), no. 12, 4203--4215

    2005

  16. [24]

    Richard Caron and Tim Traynor, The zero set of a polynomial, WSMR Report (2005), 05--02

    2005

  17. [25]

    Thomas M Cover and Joy A Thomas, Elements of information theory, Wiley-Interscience, 2006

    2006

  18. [26]

    3, 233--248

    Anthony Carbery and James Wright, Distributional and L ^q norm inequalities for polynomials over convex bodies in R ^n , Mathematical research letters 8 (2001), no. 3, 233--248

    2001

  19. [27]

    711--727

    Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart, Learning multivariate log-concave distributions, Conference on Learning Theory, PMLR, 2017, pp. 711--727

    2017

  20. [28]

    1329--1338

    Simon Du and Jason Lee, On the power of over-parametrization in neural networks with quadratic activation, International conference on machine learning, PMLR, 2018, pp. 1329--1338

    2018

  21. [29]

    Tommaso d'Orsi, Chih-Hung Liu, Rajai Nasser, Gleb Novikov, David Steurer, and Stefan Tiegel, Consistent estimation for pca and sparse regression with oblivious outliers, Advances in Neural Information Processing Systems 34 (2021), 25427--25438

    2021

  22. [30]

    2297--2306

    Tommaso d’Orsi, Gleb Novikov, and David Steurer, Consistent regression when oblivious outliers overwhelm, International Conference on Machine Learning, PMLR, 2021, pp. 2297--2306

    2021

  23. [31]

    demystifying the overparametrization phenomena, arXiv preprint arXiv:2003.10523 (2020)

    Matt Emschwiller, David Gamarnik, Eren C K z lda g , and Ilias Zadik, Neural networks and polynomial regression. demystifying the overparametrization phenomena, arXiv preprint arXiv:2003.10523 (2020)

    2020 arXiv

  24. [32]

    2, 309--314

    Yonina C Eldar, Deanna Needell, and Yaniv Plan, Uniqueness conditions for low-rank matrix recovery, Applied and Computational Harmonic Analysis 33 (2012), no. 2, 309--314

    2012

  25. [33]

    Sebastian Goldt, Madhu Advani, Andrew M Saxe, Florent Krzakala, and Lenka Zdeborov \'a , Dynamics of stochastic gradient descent for two-layer neural networks in the teacher-student setup, Advances in neural information processing systems 32 (2019)

    2019

  26. [34]

    3, 504--522

    Edgar N Gilbert, A comparison of signalling alphabets, The Bell system technical journal 31 (1952), no. 3, 504--522

    1952

  27. [35]

    David Gamarnik, Eren C K z lda g , and Ilias Zadik, Stationary points of a shallow neural network with quadratic activations and the global optimality of the gradient descent algorithm, Mathematics of Operations Research (2024)

    2024

  28. [36]

    22, 7452--7468

    Rachel Grotheer, Shuang Li, Anna Ma, Deanna Needell, and Jing Qin, Iterative hard thresholding for low cp-rank tensor models, Linear and Multilinear Algebra 70 (2022), no. 22, 7452--7468

    2022

  29. [37]

    1, 29--40

    Navid Ghadermarzy, Yaniv Plan, and Ozgur Yilmaz, Learning tensors from partial binary measurements, IEEE Transactions on Signal Processing 67 (2018), no. 1, 29--40

    2018

  30. [38]

    2, 473--504

    Noah Golowich, Alexander Rakhlin, and Ohad Shamir, Size-independent sample complexity of neural networks, Information and Inference: A Journal of the IMA 9 (2020), no. 2, 473--504

    2020

  31. [39]

    451--460

    Johan H stad, Tensor rank is np-complete, Automata, Languages and Programming: 16th International Colloquium Stresa, Italy, July 11--15, 1989 Proceedings 16, Springer, 1989, pp. 451--460

    1989

  32. [40]

    4, 644--654

    , Tensor rank is np-complete, Journal of algorithms 11 (1990), no. 4, 644--654

    1990

  33. [41]

    Roger A Horn and Charles R Johnson, Matrix analysis, Cambridge University Press, 2012

    2012

  34. [42]

    6, 1--39

    Christopher J Hillar and Lek-Heng Lim, Most tensor problems are np-hard, Journal of the ACM (JACM) 60 (2013), no. 6, 1--39

    2013

  35. [43]

    1, 85--94

    Hung Hung, Yu-Ting Lin, Penweng Chen, Chen-Chien Wang, Su-Yun Huang, and Jung-Ying Tzeng, Detection of gene--gene interactions using multistage sparse and low-rank regression, Biometrics 72 (2016), no. 1, 85--94

    2016

  36. [44]

    1319--1330

    Botao Hao, Anru R Zhang, and Guang Cheng, Sparse and low-rank tensor estimation via cubic sketchings, International conference on artificial intelligence and statistics, PMLR, 2020, pp. 1319--1330

    2020

  37. [45]

    1, 387--400

    Shirin Jalali, Toward theoretically founded learning-based compressed sensing, IEEE Transactions on Information Theory 66 (2019), no. 1, 387--400

    2019

  38. [46]

    5, 2933--2953

    Shirin Jalali and H Vincent Poor, Universal compressed sensing for almost lossless recovery, IEEE Transactions on Information Theory 63 (2017), no. 5, 2933--2953

    2017

  39. [47]

    3, 455--500

    Tamara G Kolda and Brett W Bader, Tensor decompositions and applications, SIAM review 51 (2009), no. 3, 455--500

    2009

  40. [48]

    thesis, Massachusetts Institute of Technology, 2022

    Eren C K z lda g , Algorithms and algorithmic barriers in high-dimensional statistics and random combinatorial structures, Ph.D. thesis, Massachusetts Institute of Technology, 2022

    2022

  41. [49]

    Boaz Klartag and VD Milman, Geometry of log-concave functions and measures, Geometriae Dedicata 112 (2005), 169--182

    2005

  42. [50]

    6, 2980--2998

    Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh, Matrix completion from a few entries, IEEE transactions on information theory 56 (2010), no. 6, 2980--2998

    2010

  43. [51]

    Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira, Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio, ISAAC Congress (International Society for Analysis, its Applications and Computation), Springer, 2019, pp. 1--50

    2019

  44. [52]

    Steven Lalley, Orthogonal Polynomials , https://galton.uchicago.edu/ lalley/Courses/386/OrthogonalPolynomials.pdf

  45. [53]

    Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir, On the computational efficiency of training neural networks, Advances in neural information processing systems 27 (2014)

    2014

  46. [54]

    3, 307--358

    L \'a szl \'o Lov \'a sz and Santosh Vempala, The geometry of logconcave functions and sampling algorithms, Random Structures & Algorithms 30 (2007), no. 3, 307--358

    2007

  47. [55]

    1, 18274--18321

    Yuetian Luo and Anru R Zhang, Low-rank tensor estimation via riemannian gauss-newton: Statistical optimality and second-order convergence, The Journal of Machine Learning Research 24 (2023), no. 1, 18274--18321

    2023

  48. [56]

    3655--3663

    Simon Martin, Francis Bach, and Giulio Biroli, On the impact of overparameterization on the training of a shallow neural network in high dimensions, International Conference on Artificial Intelligence and Statistics, PMLR, 2024, pp. 3655--3663

    2024

  49. [57]

    Cun Mu, Bo Huang, John Wright, and Donald Goldfarb, Square deal: Lower bounds and improved relaxations for tensor recovery, International conference on machine learning, PMLR, 2014, pp. 73--81

    2014

  50. [58]

    3, 920--930

    Nima Mesgarani, Malcolm Slaney, and SA Shamma, Content-based audio classification based on multiscale spectro-temporal features, IEEE Transactions on Speech and Audio processing 14 (2006), no. 3, 920--930

    2006

  51. [59]

    11, 5693--5705

    Dimitri Nion and Nicholas D Sidiropoulos, Tensor algebra and multidimensional harmonic retrieval in signal processing for mimo radar, IEEE Transactions on Signal Processing 58 (2010), no. 11, 5693--5705

    2010

  52. [60]

    1376--1401

    Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro, Norm-based capacity control in neural networks, Conference on learning theory, PMLR, 2015, pp. 1376--1401

    2015

  53. [61]

    Ankit Pensia, Varun Jog, and Po-Ling Loh, Robust regression with covariate filtering: Heavy tails and adversarial contamination, Journal of the American Statistical Association (2024), 1--12

    2024

  54. [62]

    1836--1840

    Erwin Riegler, David Stotz, and Helmut B \"o lcskei, Information-theoretic limits of matrix completion, 2015 IEEE International Symposium on Information Theory (ISIT), IEEE, 2015, pp. 1836--1840

    2015

  55. [63]

    Holger Rauhut, Reinhold Schneider, and Z eljka Stojanac, Low rank tensor recovery via iterative hard thresholding, Linear Algebra and its Applications 523 (2017), 220--262

    2017

  56. [64]

    Samworth, Recent Progress in Log-Concave Density Estimation , Statistical Science 33 (2018), no

    Richard J. Samworth, Recent Progress in Log-Concave Density Estimation , Statistical Science 33 (2018), no. 4, 493 -- 509

    2018

  57. [65]

    2892--2897

    Arun Sai Suggala, Kush Bhatia, Pradeep Ravikumar, and Prateek Jain, Adaptive hard thresholding for near-optimal consistent robust regression, Conference on Learning Theory, PMLR, 2019, pp. 2892--2897

    2019

  58. [66]

    2, 742--769

    Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee, Theoretical insights into the optimization landscape of over-parameterized shallow neural networks, IEEE Transactions on Information Theory 65 (2018), no. 2, 742--769

    2018

  59. [67]

    11, 757--760

    Nicholas D Sidiropoulos and Anastasios Kyrillidis, Multi-way compressed sensing for sparse low-rank tensors, IEEE Signal Processing Letters 19 (2012), no. 11, 757--760

    2012

  60. [68]

    Stefano Sarao Mannelli, Eric Vanden-Eijnden, and Lenka Zdeborov \'a , Optimization and generalization of shallow neural networks with quadratic activation functions, Advances in Neural Information Processing Systems 33 (2020), 13445--13455

    2020

  61. [69]

    Parikshit Shah, Nikhil Rao, and Gongguo Tang, Optimal low-rank tensor recovery from separable measurements: Four contractions suffice, arXiv preprint arXiv:1505.04085 (2015)

    2015 arXiv

  62. [70]

    New York Acad

    Richard P Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci 576 (1989), no. 1, 500--535

    1989

  63. [71]

    23, American Mathematical Soc., 1939

    Gabor Szeg \"o , Orthogonal polynomials, vol. 23, American Mathematical Soc., 1939

    1939

  64. [72]

    4, 2018--2039

    Vincent YF Tan, Laura Balzano, and Stark C Draper, Rank minimization over finite fields: Fundamental limits and coding-theoretic interpretations, IEEE transactions on information theory 58 (2011), no. 4, 2018--2039

    2011

  65. [73]

    3, 468--474

    Erik GF Thomas, A polarization identity for multilinear maps, Indagationes Mathematicae 25 (2014), no. 3, 468--474

    2014

  66. [74]

    Nauk, SSSR 117 (1957), 739--741

    Rom Rubenovich Varshamov, Estimate of the number of signals in error correcting codes, Docklady Akad. Nauk, SSSR 117 (1957), 739--741

    1957

  67. [75]

    133, 1--34

    Luca Venturi, Afonso S Bandeira, and Joan Bruna, Spurious valleys in one-hidden-layer neural network optimization landscapes, Journal of Machine Learning Research 20 (2019), no. 133, 1--34

    2019

  68. [76]

    Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, arXiv preprint arXiv:1011.3027 (2010)

    2010 arXiv

  69. [77]

    47, Cambridge university press, 2018

    , High-dimensional probability: An introduction with applications in data science, vol. 47, Cambridge university press, 2018

    2018

  70. [78]

    Gal Vardi, Ohad Shamir, and Nati Srebro, The sample complexity of one-hidden-layer neural networks, Advances in Neural Information Processing Systems 35 (2022), 9139--9150

    2022

  71. [79]

    12, 5728--5741

    Martin J Wainwright, Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting, IEEE transactions on information theory 55 (2009), no. 12, 5728--5741

    2009

  72. [80]

    Guenther Walther, Inference and modeling with log-concave distributions , Statistical Science (2009), 319--327

    2009

  73. [81]

    8, 3721--3748

    Yihong Wu and Sergio Verd \'u , R \'e nyi information dimension: Fundamental limits of almost lossless analog compression , IEEE Transactions on Information Theory 56 (2010), no. 8, 3721--3748

    2010

  74. [82]

    6, 2967--2979

    Wei Wang, Martin J Wainwright, and Kannan Ramchandran, Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices, IEEE Transactions on Information Theory 56 (2010), no. 6, 2967--2979

    2010

  75. [83]

    2, 497--508

    Zhiqiang Xu, The minimal measurement number for low-rank matrix recovery, Applied and Computational Harmonic Analysis 44 (2018), no. 2, 497--508

    2018

  76. [84]

    10, 6753--6766

    Ming Yuan and Cun-Hui Zhang, Incoherent tensor norms and their applications in higher order tensor completion, IEEE Transactions on Information Theory 63 (2017), no. 10, 6753--6766

    2017

  77. [85]

    Zhengwu Zhang, Genevera I Allen, Hongtu Zhu, and David Dunson, Tensor network factorizations: Relationships between brain structural connectomes and traits, Neuroimage 197 (2019), 330--343

    2019

  78. [86]

    Yuchen Zhang, John Duchi, Michael I Jordan, and Martin J Wainwright, Information-theoretic lower bounds for distributed statistical estimation with communication constraints, Advances in Neural Information Processing Systems 26 (2013)

    2013

  79. [87]

    Yifan Zhang and Joe Kileel, Covering number of real algebraic varieties and beyond: Improved bounds and applications, arXiv e-prints (2023), arXiv--2311

    2023

  80. [88]

    502, 540--552

    Hua Zhou, Lexin Li, and Hongtu Zhu, Tensor regression with applications in neuroimaging data analysis, Journal of the American Statistical Association 108 (2013), no. 502, 540--552

    2013

Pith tools

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