Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering

Christina Lee Yu; Devavrat Shah

REVIEW 3 major objections 3 minor 30 references

Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering

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

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

Pith's one-line read A similarity-based collaborative filtering rule estimates a 3-order tensor from sparse random entries once each entry is observed with probability $p=\Omega(n^{-3/2+\kappa})$, nearly matching the conjectured computational lower bound.

desk verdict A real nearest-neighbor tensor estimator with near-optimal sample complexity, but the distance-concentration proof has an exponent mismatch that needs fixing before the main theorem can be taken as proven. read the letter →

arxiv 1908.01241 v4 pith:767N4CNP submitted 2019-08-03 cs.LG cs.DSstat.ML

Devavrat Shah , Christina Lee Yu This is my paper · ORCID

classification cs.LGcs.DSstat.ML

keywords tensorestimationcollaborativefilteringsparseobservationslow-rankmaximumentry-wiseerrorsamplecomplexitynearestneighborestimatorlatentvariablemodel

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 a simple iterative collaborative-filtering rule can estimate a 3-way tensor from very sparse random observations, with every entry error tending to zero. Specifically, it establishes that if each of the $n^3$ possible entries is observed independently with probability $p=\Omega(n^{-3/2+\kappa})$ for any arbitrarily small $\kappa>0$, then the proposed nearest-neighbor estimator achieves mean squared error and maximum entry-wise error decaying to $0$. That sample size nearly matches the conjectured computational lower bound of $\Omega(n^{3/2})$ for low-rank tensor estimation, and is far below the $O(n^2)$ rate of flattening-based matrix methods. The algorithm works by flattening the tensor into a bipartite graph, expanding neighborhoods with breadth-first search, estimating distances between coordinate indices from thresholded quadratic forms, and finally averaging observed entries from nearby coordinates. The paper also proves a robustness property: bounded observation noise or a bounded-rank approximation error degrades the final error only by a polynomial in that tolerance.

What carries the argument

The load-bearing object is a distance estimator built from breadth-first-search trees on a bipartite graph. The tensor is flattened into an $n\times\binom{n/2}{2}$ matrix; observed entries become weighted edges between coordinate vertices and pair vertices. For each coordinate $u$, the algorithm grows a BFS tree to depth $2t$ with $t=\lceil 1/(4\kappa)\rceil$, forming neighborhood vectors $N_{u,s}$ over single coordinates and $W_{u,s}$ over coordinate pairs, whose entries are products of edge weights along tree paths. The estimated distance between coordinates $u$ and $v$ is a normalized combination of thresholded quadratic forms $Z_{uv}$ built from fresh observations over pair indices outside both BFS neighborhoods. This quantity concentrates around the ideal distance $d(\theta_u,\theta_v)=\|\Lambda^{t+1}Q(e_u-e_v)\|_2^2$. The concentration proof is the heart of the paper: it bounds a martingale difference sequence built from the successive BFS layers, then a U-statistic over the remaining pair indices, obtaining $|d-\mathrm{dist}|=O(n^{-\kappa+\psi})$ with high probability. Once distances are reliable, the final estimate averages fresh observations $(a,b,c)$ whose coordinates are all within threshold $\eta=\Theta(n^{-(\kappa-\psi)})$ of the target coordinates, a step whose bias-variance tradeoff controls the error rates.

What would settle it

Take a rank-$r$ tensor with random orthonormal factors and no smooth latent representation, run the algorithm at $p=n^{-3/2+\kappa}$, and check whether the maximum entry-wise error still converges to $0$; the paper's assumptions predict the distance-concentration argument can fail. Concretely, one can measure the empirical distribution of the estimated distances against the ideal latent distances on synthetic data and look for a constant gap when $p=n^{-3/2}$.

Watch

Extended reading notes

Core claim

The central result, Theorem 4.1, assumes the true tensor has the form $F(u,v,w)=\sum_{k=1}^r \lambda_k q_k(\theta_u)q_k(\theta_v)q_k(\theta_w)$ with i.i.d. latent variables $\theta_u\sim U[0,1]$, bounded orthonormal eigenfunctions $q_k$, constant rank $r=\Theta(1)$, and an $L$-Lipschitz function $f$. Given independent Bernoulli observations with probability $p=n^{-3/2+\kappa}$, $\kappa\in(0,1/2)$, and per-entry noise with bounded variance, the algorithm's estimate satisfies MSE $=O(n^{-(\kappa-\psi)})$ and $\|F-\hat F\|_{\max}=O(n^{-(\kappa-\psi)/2})$ with probability $1-O(n^4\exp(-\Theta(n^{2\psi})))$, for any $\psi<\min(\kappa,3/8)$. In words, both average and worst-case entry errors vanish whenever sampling density exceeds $n^{-3/2}$ by an arbitrarily small polynomial factor. The proof shows the same threshold is exactly the connectivity threshold of the bipartite graph used to compute coordinate similarities, which the authors identify as the algorithmic reason behind the conjectured $\Omega(n^{3/2})$ computational lower bound. The robustness statement extends the conclusion to noisy tensors and to tensors that are only within $\varepsilon$ of finite rank: the final error then converges to $\mathrm{poly}(\varepsilon)$.

Load-bearing premise

The guarantee collapses if the tensor is not generated by a smooth latent-variable model of the specified form: the proof needs i.i.d. latent positions and a Lipschitz, finite-spectrum function to ensure that every coordinate has many near neighbors and that the ideal distance is well behaved, so the stated theorem does not cover an arbitrary low-rank tensor.

Editorial extensions

If this is right

Sample complexity nearly hits the conjectured efficient limit: $\Omega(n^{3/2+\kappa})$ observations suffice for consistent estimation, whereas flattening-based matrix methods need on the order of $n^2$ observations.
The guarantee is worst-case over entries, not just average-case: the maximum entry-wise error converges to $0$, so every coordinate of the estimate is reliable.
The estimator is robust: if observations carry noise bounded by $\varepsilon$, or the tensor is only $\varepsilon$-close to a finite-rank tensor, the final error degrades by only $\mathrm{poly}(\varepsilon)$.
The $n^{3/2}$ threshold has an algorithmic interpretation: it is the density at which the similarity graph becomes connected, giving a concrete reason why computationally efficient methods may not easily go below it.
The algorithm is parallelizable because similarity computations are pairwise, and the authors argue the construction extends to asymmetric tensors whose dimensions are proportional.

Reading between the lines

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

If the connectivity explanation is the real barrier, the same BFS-neighborhood construction should generalize to $d$-order tensors with sample complexity near $n^{d/2}$; the paper only states this as a heuristic, not a theorem.
The theorem's constant rank $r=\Theta(1)$ and orthonormal bounded eigenfunctions are likely the limiting conditions; testing the algorithm on overcomplete tensors with $r>n$ or on non-orthogonal factor dictionaries would show whether nearest-neighbor distances remain identifiable beyond the paper's model.
A practitioner would need to choose $\kappa$ and the threshold $\eta$ from data, but the theory assumes the sampling exponent is known; the paper gives no data-driven selection rule.
The robustness result could be turned into a model-selection tool: comparing estimation error across thresholds $\eta$ may reveal the effective smoothness scale or rank of the latent function, an extension the authors do not explore.

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.

Desk Editor's Note

read the letter

Colleague,

Quick take: this is a real result with a fixable hole in the proof. The authors extend the Borgs–Chayes–Lee–Shah iterative collaborative filtering idea to 3-tensors and show a nearest-neighbor scheme achieves max entrywise error and MSE going to zero at p = n^{-3/2+\kappa}, matching the SOS and spectral sample complexity. That is genuinely new for a similarity-based method, and the proof machinery—BFS neighborhood growth, martingale concentration, U-statistic bounds—is substantial and mostly careful.

The good parts first. The algorithm is simple and parallelizable; the main theorem gives max-entrywise guarantees in a regime where previous efficient methods used SOS or spectral ideas. The paper is forthright about the latent-variable model: bounded orthonormal eigenfunctions, constant rank, i.i.d. latent positions, Lipschitz f. It also spells out what is used where and what could plausibly be relaxed.

Where it gets soft. There is an internal inconsistency in the distance-concentration part. Eq. (5.2) defines the ideal distance with an exponent \Lambda^{t+1}; Section 6.5, Eq. (6.25), writes it with \Lambda^{2t}; and the actual concentration lemmas (6.2 and 6.6) push \tilde N_{u,t} toward \Lambda^{2t} Q e_u, so the quadratic form in dist concentrates on \Lambda^{4t+2}, i.e., d_actual = ||\Lambda^{2t+1}Q(e_u-e_v)||^2. These are not the same object unless |\lambda_k|=1, which is not assumed. So Lemma 5.2 as written is not established. I think it is repairable: redefine d to be d_actual and adjust bias to |\lambda_r|^{-2t}\sqrt{\eta} and meas to |\lambda_1|^{-2t}\sqrt{\eta'} times the existing constants. Since t = ceil(1/4\kappa) is constant, all rates in Theorem 4.1 survive. But someone has to actually write out the corrected argument; right now the central proof has a gap.

Also, the metadata abstract advertises robustness to arbitrary bounded noise and approximate low-rank tensors. That is not proven in the body; the model assumes mean-zero noise with bounded entries and exactly finite spectrum. Either add the proof or tone down the abstract.

One reader concern I would push back on: the Lemma 6.7 conditional-independence point. Under the symmetric observation model, one observed triplet does create multiple edges, but the rows a in S_{u,t} or S_{v,t} are outside the set S used for the columns, so those extra edges land in columns (a,\beta) that are not in the S\times S summation. The independence claim across distinct columns looks defensible to me, though the authors should make that explicit.

Bottom line: worth a serious referee. The result is interesting and probably true in substance, but the distance concentration proof needs a corrected statement and constants. Send it to review with the expectation of heavy revision.

Referee Report

3 major / 3 minor

Summary. The paper studies estimation of a symmetric 3-way tensor from independent noisy observations of entries with probability p, in the sparse regime p = n^{-3/2+κ}. It proposes a similarity-based collaborative filtering algorithm: flatten the tensor to an n-by-Θ(n^2) matrix, build BFS trees in the bipartite graph of observed entries, compute a distance between coordinates from bilinear forms of the BFS neighborhood vectors, and estimate each entry by averaging nearby observed entries. The main result, Theorem 4.1, claims MSE O(n^{-(κ-ψ)}) and maximum entrywise error O(n^{-(κ-ψ)/2}) with high probability, under a latent-variable model with bounded orthonormal eigenfunctions, constant rank, and an L-Lipschitz link function. The proof is via a chain of concentration lemmas: BFS growth (Lemma 6.1), quadratic-form concentration (Lemmas 6.2–6.6), and a column-average concentration (Lemma 6.7), culminating in Lemma 5.2 asserting that the estimated distance is within O(n^{-(κ-ψ)}) of an ideal distance.

Significance. If Theorem 4.1 were established, the contribution would be substantial: an elementary, parallelizable nearest-neighbor algorithm with provable consistency at p = n^{-3/2+κ}, matching the conjectured computational sample-complexity barrier without SOS or spectral methods, and with proof techniques for asymmetric flattened-matrix bilinear forms that could be of independent interest. The paper is also honest about the model restrictions (latent variables, Lipschitz f, bounded orthonormal eigenfunctions, r = Θ(1)) and about the practical limitations of the algorithm. However, the central proof currently contains several inconsistencies that prevent the main claim from being considered proved; the issues appear repairable, but they require substantive work rather than copyediting.

major comments (3)

[§5.2, Eq. (5.2); §6.5, Eqs. (6.25)–(6.27); Lemmas 6.2 and 6.6] Lemma 6.2 shows Q\tilde N_{u,t} ≈ Λ^{2t}Qe_u, and Lemma 6.6 then shows that the bilinear form \tilde N_u^T Q^T Λ² Q \tilde N_v concentrates on e_u^T Q^T Λ^{4t+2}Q e_v. Consequently the quantity Z_{uv} in (6.27) concentrates on e_u^T Q^T Λ^{4t+2}Q e_v, so the distance concentrates on ‖Λ^{2t+1}Q(e_u−e_v)‖². This is not the ideal distance d defined in (5.2) as ‖Λ^{t+1}Q(e_u−e_v)‖², and it is not the expression in (6.25), whose displayed equality is also algebraically wrong (the right-hand side equals ‖Λ^t Q(e_u−e_v)‖², not ‖Λ^{2t}Q(e_u−e_v)‖²). In addition, (3.3) and (6.26) put a leading 1/(|V_B|p²) or 1/(\binom{|S|}{2}p²) in front of Z_{uu}+Z_{vv}−Z_{uv}−Z_{vu} although Z_{uv} already carries that normalization; with the printed definitions dist would be Θ(n^{−1+2κ}) too small. Because Lemma 5.2 is the bridge to Theorem 4.1 and no assumption forces |λ_k|=1, the proof of the main theorem is not established as written. The gap is plausibly repairable by defining the ideal distance as ‖Λ^{2t+1}Q(e_u−e_v)‖² and adjusting the constants in bias(η) and meas(η′) accordingly, but this needs to be done explicitly.
[§6.4, proof of Lemma 6.7] The proof claims that, conditioned on F(u,v,t,x,δ) and {θ_i}_{i∈[n]}, the variables T(α,β) are independent across columns except for the case of the exact same pair, and that any shared-coordinate correlation is only through the latent variables. Under the symmetric observation model of Section 2, this is not correct: an observed triplet (a,α,β) is represented in the flattened matrix both as M_B(a,(α,β)) and as M_B(α,(a,β)), so e.g. T(α,β) and T(a,β) (or T(α,β) and T(α,γ) through the rows γ and β) contain the same random variable. The variance computation that follows sums Var[T(α,β)] over columns and omits these cross-column covariances, so the Bernstein bound on the sum of \tilde T(α,β) is not justified. This is a load-bearing gap in Lemma 6.7 and hence in Lemma 5.2; it requires either a covariance calculation or a modification of the sampling/algorithm so that each observed triplet enters only one flattened entry.
[§6.4, truncation bias in Lemma 6.7] The proof bounds the bias introduced by the φ-threshold as O(n²(n^{−(1/2−κ)})^φ) and then concludes it is o(1). With φ = ⌈4/(1−2κ)⌉, at values of κ for which 4/(1−2κ) is an integer (e.g., κ = 1/4), this displayed bound is Θ(1), not o(1). The conclusion can be rescued by using the sharp growth bound from Lemma 6.1, |S_{u,t}∪S_{v,t}| = O(n^{2κt}) with t = ⌈1/(4κ)⌉, in place of the crude |S_{u,t}∪S_{v,t}| = O(n); but as written the argument does not prove the asserted o(1) uniformly in κ.

minor comments (3)

[Abstract and Introduction] The abstract and introduction state the result as recovery of low-rank or finite-rank tensors. Theorem 4.1 is proved only for the latent-variable model of Section 2 with iid Uniform[0,1] latent variables, bounded orthonormal eigenfunctions, constant rank, and an L-Lipschitz link function. The paper acknowledges this limitation on page 4, but the high-level claims should be phrased to match the theorem.
[§6.5, Eq. (6.26)] The set S≡S_{u,s,t} in (6.26) uses an undefined subscript s; it should be S_{u,v,t} = [n]\(B_{u,2t}∪B_{v,2t}∪[n/2]) or similar.
[Lemma 6.2 statement] The explicit bound in Lemma 6.2 omits the dependence on the model constants B and on the eigenvalue factors that appear in the proof's variance summations; since these are constants this is cosmetic, but the statement should either include them or explicitly say constants are absorbed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all algorithm parameters are explicit analytic functions; the tensor-specific result is proved in-paper, and self-citations to [3] only supply the algorithmic template, not the conclusion.

full rationale

The derivation is self-contained: every algorithm parameter is an explicit function of n, p, kappa, and psi (t in Eq. (3.1), phi above Eq. (3.3), eta in Theorem 4.1), and no parameter is fitted to a subset of observations and then reported as a prediction. The ideal distance d in Eq. (5.2) is an analytic benchmark derived from the assumed spectral model, not an estimated quantity; the estimator dist is computed from M1 and the final estimate averages M2. Lemma 5.1 is stated and proved in the paper rather than merely imported, and the main concentration lemmas (6.2, 6.6, 6.7) are proved for the tensor BFS construction. The self-citation to [3] supplies the algorithmic template for iterative collaborative filtering and a sample-splitting remark, but the tensor-specific claim—recovery at p = Omega(n^{-3/2+kappa}) with explicit MSE and max-entry-wise rates—is established by the paper's own arguments and is not an input to those arguments. There is a possible internal inconsistency between the ideal distance of Eq. (5.2), which uses Lambda^{t+1}, and the quadratic form that Section 6 actually concentrates, which involves Lambda^{2t} or Lambda^{4t+2}; that is a proof gap or correctness risk, not circularity, because no equation is being used as its own conclusion and no fitted value is being relabeled as a prediction. Accordingly, the paper does not exhibit a self-definitional, fitted-input-called-prediction, or self-citation-load-bearing circularity.

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

The algorithm has no fitted constants. The only hand-chosen algorithmic parameter is η, set analytically to Θ(n^{-(κ-ψ)}); t and φ are explicit functions of p and n. All model parameters (r, L, B, λ_k) are inputs from the generative model, not learned by the algorithm. The proof relies on standard concentration inequalities.

free parameters (1)

η (averaging threshold) = Θ(n^{-(κ-ψ)}), constant unspecified
The algorithm's Step 5 threshold must be set to this order with a sufficiently large constant; the theorem does not specify the constant, but the proof requires η-Δ = Θ(η). This is an analytically chosen constant, not fitted to data.

assumptions (4)

domain assumption The true tensor is generated by a latent-variable model: F(u,v,w)=Σ_{k=1}^r λ_k q_k(θ_u)q_k(θ_v)q_k(θ_w), with θ_u i.i.d. Uniform[0,1], q_k orthonormal and bounded by B, r=Θ(1), and f L-Lipschitz.
This is the central modeling assumption (Section 2) that makes the ideal distance (Eq. 5.2) and Property 5.3 meaningful; without it the nearest-neighbor argument has no stated guarantee.
domain assumption The BFS tree is constructed with uniformly random tie-breaking among valid parent edges and must respect the no-repeat-coordinate constraint.
Step 3 of the algorithm; Lemmas 6.4 and 6.5 use the uniform parent distribution to obtain zero-mean martingale differences, and Lemma 6.1 uses the sparsity-pattern symmetry of the sampling process.
domain assumption Observation noise is independent, mean-zero, with variance uniformly bounded by σ², and the data tensor satisfies |M|≤1.
Equation (2.1) and the surrounding text; used in the Hoeffding and variance steps of Lemmas 5.1, 6.4, 6.5, and 6.7.
standard math Standard concentration tools (Bernstein's inequality, Hoeffding, U-statistic bounds, martingale difference concentration) are valid.
Used throughout Section 6; the paper cites [29] and [14] for these.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering." pith.science (2026). https://pith.science/paper/767N4CNP

@misc{pith2026190801241,
  author       = {Pith},
  title        = {Pith review of: Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/767N4CNP}},
  note         = {Machine review of arXiv:1908.01241}
}

abstract

Consider the task of estimating a 3-order $n \times n \times n$ tensor from noisy observations of randomly chosen entries in the sparse regime. We introduce a similarity based collaborative filtering algorithm for estimating a tensor from sparse observations and argue that it achieves sample complexity that nearly matches the conjectured computationally efficient lower bound on the sample complexity for the setting of low-rank tensors. Our algorithm uses the matrix obtained from the flattened tensor to compute similarity, and estimates the tensor entries using a nearest neighbor estimator. We prove that the algorithm recovers a finite rank tensor with maximum entry-wise error (MEE) and mean-squared-error (MSE) decaying to $0$ as long as each entry is observed independently with probability $p = \Omega(n^{-3/2 + \kappa})$ for any arbitrarily small $\kappa > 0$. More generally, we establish robustness of the estimator, showing that when arbitrary noise bounded by $\varepsilon \geq 0$ is added to each observation, the estimation error with respect to MEE and MSE degrades by $\text{poly}(\varepsilon)$. Consequently, even if the tensor may not have finite rank but can be approximated within $\varepsilon \geq 0$ by a finite rank tensor, then the estimation error converges to $\text{poly}(\varepsilon)$. Our analysis sheds insight into the conjectured sample complexity lower bound, showing that it matches the connectivity threshold of the graph used by our algorithm for estimating similarity between coordinates.

Figures

Figures reproduced from arXiv: 1908.01241 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 26 canonical work pages

[1]

Noisy tensor completion via the sum-of-squares hierarchy

Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory, 2016

work page 2016
[2]

A New Sampling Technique for Tensors

Srinadh Bhojanapalli and Sujay Sanghavi. A new sampling technique for tensors. arXiv preprint arXiv:1502.05023, 2015

work page Pith review arXiv 2015
[3]

Thy friend is my friend: Iterative collaborative ﬁltering for sparse matrix estimation

Christian Borgs, Jennifer Chayes, Christina E Lee, and Devavrat Shah. Thy friend is my friend: Iterative collaborative ﬁltering for sparse matrix estimation. In Advances in Neural Information Processing Systems, pages 4715–4726, 2017. Also available at ArXiv

work page 2017
[4]

Exact matrix completion via convex optimization

Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM , 55(6), 2009

work page 2009
[5]

Matrix completion with noise

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

work page 2010
[6]

The power of convex relaxation: Near-optimal matrix completion

Emmanuel J Cand` es and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory , 56(5):2053–2080, 2010

work page 2010
[7]

Matrix estimation by universal singular value thresholding

Sourav Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statistics, 43(1):177–214, 2015

work page 2015
[8]

Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

Yudong Chen and Martin J Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025 , 2015

arXiv 2015

Show all 30 references

[9]

Nuclear norm of higher-order tensors

Shmuel Friedland and Lek-Heng Lim. Nuclear norm of higher-order tensors. arXiv preprint arXiv:1410.6072, 2014

2014 arXiv
[10]

Tensor completion and low-n-rank tensor recovery via convex optimization

Silvia Gandy, Benjamin Recht, and Isao Yamada. Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27(2):025010, 2011

2011
[11]

Matrix completion has no spurious local minimum

Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems , pages 2973–2981, 2016

2016
[12]

Oki, and Douglas Terry

David Goldberg, David Nichols, Brian M. Oki, and Douglas Terry. Using collaborative ﬁltering to weave an information tapestry. Commun. ACM, 1992

1992
[13]

Understanding alternating minimization for matrix completion

Moritz Hardt. Understanding alternating minimization for matrix completion. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on , pages 651–660. IEEE, 2014

2014
[14]

Hoeﬀding

W. Hoeﬀding. Probability inequalities for sums of bounded random variables. Journal of American Statistical Association, 58:13–30, 1963

1963
[15]

Low-rank matrix completion using alternating minimization

Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-ﬁfth annual ACM symposium on Theory of computing, pages 665–674. ACM, 2013

2013
[16]

Provable tensor factorization with missing data

Prateek Jain and Sewoong Oh. Provable tensor factorization with missing data. In Advances in Neural Information Processing Systems , 2014. 35

2014
[17]

Matrix completion from a few entries

Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. IEEE Transactions on Information Theory , 56(6):2980–2998, 2010

2010
[18]

Matrix completion from noisy entries

Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from noisy entries. Journal of Machine Learning Research , 11(Jul):2057–2078, 2010

2010
[19]

Y. Li, D. Shah, D. Song, and C. L. Yu. Nearest neighbors for matrix estimation interpreted as blind regression for latent variable model. IEEE Transactions on Information Theory , 66(3):1760–1784, March 2020

2020
[20]

Tensor completion for estimating missing values in visual data

Ji Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye. Tensor completion for estimating missing values in visual data. IEEE transactions on pattern analysis and machine intelligence , 35(1):208–220, 2013

2013
[21]

Spectral regularization algorithms for learning large incomplete matrices

Rahul Mazumder, Trevor Hastie, and Robert Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of machine learning research, 11(Aug):2287–2322, 2010

2010
[22]

Spectral algorithms for tensor completion

Andrea Montanari and Nike Sun. Spectral algorithms for tensor completion. Communications on Pure and Applied Mathematics , 71(11):2381–2425, 2018

2018
[23]

Estimation of (near) low-rank matrices with noise and high-dimensional scaling

Sahand Negahban and Martin J Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling. The Annals of Statistics , pages 1069–1097, 2011

2011
[24]

Exact tensor completion with sum-of-squares

Aaron Potechin and David Steurer. Exact tensor completion with sum-of-squares. arXiv preprint arXiv:1702.06237, 2017

2017 arXiv
[25]

A simpler approach to matrix completion

Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12(Dec):3413–3430, 2011

2011
[26]

Guaranteed matrix completion via non-convex factorization

Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE Transactions on Information Theory , 62(11):6535–6579, 2016

2016
[27]

Estimation of low-rank tensors via convex optimization

Ryota Tomioka, Kohei Hayashi, and Hisashi Kashima. Estimation of low-rank tensors via convex optimization. arXiv preprint arXiv:1010.0789 , 2010

2010 arXiv
[28]

Statistical performance of convex tensor decomposition

Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, and Hisashi Kashima. Statistical performance of convex tensor decomposition. In Advances in Neural Information Processing Systems , pages 972–980, 2011

2011
[29]

High-dimensional statistics: A non-asymptotic viewpoint , volume 48

Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint , volume 48. Cambridge University Press, 2019

2019
[30]

On tensor completion via nuclear norm minimization

Ming Yuan and Cun-Hui Zhang. On tensor completion via nuclear norm minimization. Foun- dations of Computational Mathematics , 16(4):1031–1068, 2016. 36 A Useful Lemmas Lemma A.1. The following inequalities hold: (a) For any ρ≥ 2 and integer r≥ 1, r∑ s=1 ρs≤ 2ρr. (b) For any ρ≥...

2016

Pith tools

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

[1] [1]

Noisy tensor completion via the sum-of-squares hierarchy

Boaz Barak and Ankur Moitra. Noisy tensor completion via the sum-of-squares hierarchy. In Conference on Learning Theory, 2016

work page 2016

[2] [2]

A New Sampling Technique for Tensors

Srinadh Bhojanapalli and Sujay Sanghavi. A new sampling technique for tensors. arXiv preprint arXiv:1502.05023, 2015

work page Pith review arXiv 2015

[3] [3]

Thy friend is my friend: Iterative collaborative ﬁltering for sparse matrix estimation

Christian Borgs, Jennifer Chayes, Christina E Lee, and Devavrat Shah. Thy friend is my friend: Iterative collaborative ﬁltering for sparse matrix estimation. In Advances in Neural Information Processing Systems, pages 4715–4726, 2017. Also available at ArXiv

work page 2017

[4] [4]

Exact matrix completion via convex optimization

Emmanuel Candes and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM , 55(6), 2009

work page 2009

[5] [5]

Matrix completion with noise

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

work page 2010

[6] [6]

The power of convex relaxation: Near-optimal matrix completion

Emmanuel J Cand` es and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory , 56(5):2053–2080, 2010

work page 2010

[7] [7]

Matrix estimation by universal singular value thresholding

Sourav Chatterjee. Matrix estimation by universal singular value thresholding. The Annals of Statistics, 43(1):177–214, 2015

work page 2015

[8] [8]

Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

Yudong Chen and Martin J Wainwright. Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025 , 2015

arXiv 2015