PaperlayerView exact revision on arXiv

Source-linked AI summary

Nonconvex Low-Rank Tensor Completion from Noisy Data

Changxiao Cai, Gen Li, H. Vincent Poor, Yuxin Chen

arXiv:1911.04436v2cs.LGcs.ITmath.ITmath.OCmath.STstat.MLstat.TH

TL;DR

The paper addresses noisy completion of low-rank tensors from highly incomplete observations, where prior methods trade computational scalability against statistical guarantees. It proposes a two-stage nonconvex method combining rough initialization with vanilla gradient descent and obtains near-optimal computation, sample complexity, and estimation accuracy under incoherence, conditioning, and constant-rank assumptions.

  • Problem

    Noisy low-rank tensor completion requires recovering tensors and factors from highly incomplete observations, while prior methods are either computationally expensive or statistically sub-optimal.

    Source: §1.1 · p. 3, §1.2 · p. 4

  • Method

    The paper uses a two-stage nonconvex algorithm consisting of rough initialization followed by vanilla gradient descent.

    Source: §2.2 · pp. 6, 8, §5.1.2 · p. 18

  • Results

    The method achieves nearly linear-time completion with near-optimal sample complexity and statistical accuracy, including entrywise error guarantees, for incoherent, well-conditioned constant-rank tensors.

    Source: §2.2 · pp. 8–9, §6 · p. 27

  • Takeaways & Limitations

    Low-rank tensor completion can be both computationally efficient and statistically accurate within the paper’s stated incoherent, well-conditioned, constant-rank regime.

    Source: §2.2 · p. 6, §6 · p. 27

    The theory has likely loose dependencies on rank and incoherence, and growing condition number can make initialization computationally burdensome.

    Source: §2.2 · p. 11, §5.1.2 · p. 18

Abstract

from arXiv · show

We study a noisy tensor completion problem of broad practical interest, namely, the reconstruction of a low-rank tensor from highly incomplete and randomly corrupted observations of its entries. While a variety of prior work has been dedicated to this problem, prior algorithms either are computationally too expensive for large-scale applications, or come with sub-optimal statistical guarantees. Focusing on "incoherent" and well-conditioned tensors of a constant CP rank, we propose a two-stage nonconvex algorithm -- (vanilla) gradient descent following a rough initialization -- that achieves the best of both worlds. Specifically, the proposed nonconvex algorithm faithfully completes the tensor and retrieves all individual tensor factors within nearly linear time, while at the same time enjoying near-optimal statistical guarantees (i.e. minimal sample complexity and optimal estimation accuracy). The estimation errors are evenly spread out across all entries, thus achieving optimal $\ell_{\infty}$ statistical accuracy. We have also discussed how to extend our approach to accommodate asymmetric tensors. The insight conveyed through our analysis of nonconvex optimization might have implications for other tensor estimation problems.

1 Introduction and motivation

The paper studies recovering low-rank tensors and their factors from sparse noisy entries, motivated by applications requiring multi-way structure. It targets the gap between computationally efficient tensor-completion algorithms and near-optimal statistical accuracy.

1.1 Tensor completion from noisy entries

  • Tensor completion supports applications including personalized medicine, medical imaging, seismic analysis, harmonic retrieval, customer-product preferences, and video in-painting.These applications motivate exploiting multi-way interactions when observations are sparse.Source: §1.1 · p. 3
  • Low-rank tensor completion reconstructs tensors and individual factors from highly incomplete, noisy observations under a small-rank model.The formal setup focuses on symmetric order-three tensors with randomly sampled entries and additive noise, while noting extensions to asymmetric tensors.Source: §1.1 · pp. 3–4

1.2 Computational and statistical challenges

  • Tensor completion is harder than matrix completion: existing polynomial-time methods require at least order rd3/2 samples, far above the model’s rd degrees of freedom.The paper frames this gap as a possible computational barrier away from information-theoretic sampling limits [BM16].Source: §1.2 · p. 4
  • Prior approaches include spectral, sum-of-squares, nonconvex, and unfolding-based convex methods, but they are generally too expensive or fail to achieve exact recovery as noise vanishes.The cited prior methods provide guarantees in parts of the relevant regime, yet do not jointly deliver scalable computation and optimal statistical performance.Source: §1.2 · p. 4
  • The paper asks whether low-rank tensor completion can achieve both linear-time computation and near-optimal statistical accuracy.Its proposed nonconvex algorithm is intended to address both questions simultaneously.Source: §1.2 · p. 4

2 Algorithm and main results

This section presents a two-stage nonconvex tensor-completion method and establishes its theoretical guarantees under standard structural and noise assumptions, including extensions to broader settings. It also reports numerical evidence for the method’s convergence and recovery behavior and introduces notation used throughout the paper.

2.1 A two-stage nonconvex algorithm

  • The algorithm combines spectral initialization—subspace estimation followed by factor disentanglement—with vanilla gradient descent, whose gradient evaluation costs time proportional to reading the data.Initialization costs O(pd^3) for constant rank and condition number with p ≥ 1/d^2, yielding a linear-time procedure.Source: §2.1 · pp. 5–6

2.2 Main results

  • Under low rank, incoherence, well-conditionedness, and random sub-Gaussian noise, the method converges linearly without noise and reaches statistical accuracy in logarithmically many noisy iterations.The guarantees hold uniformly through t0 = d^5, and the iteration horizon can be replaced by d^c for any fixed c > 0.Source: §2.2 · pp. 6–8
  • The theory requires sample size above d^3/2 poly log d, attains near-optimal Euclidean accuracy, and provides entrywise error roughly d times smaller than the Euclidean bound.The entrywise guarantee implies that estimation errors are evenly spread across tensor entries and matches a lower bound up to logarithmic factors.Source: §2.2 · p. 9
  • Vanilla gradient descent needs neither explicit regularization nor sample splitting, while the theory tolerates noise components considerably larger than corresponding truth entries.The broader theorem allows rank below o(d^1/6), but rank and incoherence dependencies may be loose, and growing condition numbers can make initialization expensive.Source: §2.2 · pp. 9–11

2.3 Numerical experiments

  • Numerical experiments are introduced to corroborate the theory, with empirical success limited by the initialization stage’s probability 1 − δ and its random-restart vectors.The experiments motivate modifying initialization to improve empirical success rates.Source: §2.3 · p. 11
  • The proposed algorithm’s estimation errors decay geometrically fast in noiseless tensor completion.This is reported for relative Frobenius errors of the factor and tensor estimates, among other metrics.Source: §2.3 · p. 11
  • The proposed initialization algorithm outperforms the tensor power method in empirical exact-recovery success rates.Success is defined by relative ℓ2 error at most 0.01, evaluated over 100 independent Monte Carlo trials.Source: §2.3 · p. 11, Figure 1 · p. 12
  • Exact reconstruction is achieved when rank r is sufficiently small compared with d, with a plausible successful rank range larger than the theoretical requirement r = o(d1/6).The rank-dependence experiment uses p = rd−3/2 log2 d and averages success rates over 100 trials.Source: §2.3 · pp. 11–12, Figure 1 · p. 12
  • All three squared relative errors scale inversely proportional to SNR in noisy settings, consistent with the statistical guarantees.The plotted slope is roughly −1; the experiment uses d = 100, r = 4, and p = 0.1.Source: §2.3 · p. 12, Figure 1 · p. 12

2.4 Notation

  • The notation subsection defines matrix and tensor norms, slices, inner and vector products, tensor operator norms, unit spheres, and asymptotic comparison symbols.It introduces operator and Frobenius norms, eigenvalue and singular-value orderings, tensor contractions, and relations including O(·), ≲, ≳, ≍, o(·), ≪, and ≫.Source: §2.4 · p. 12

3 Initialization

The initialization uses a two-step procedure: spectral subspace estimation followed by factor disentanglement, with projection-based retrieval designed to control noise and avoid poor random starts.

3 Initialization

  • The initialization first estimates the factor subspace spectrally, then disentangles individual tensor factors from that subspace.The spectral estimate uses the top-r eigenspace of an off-diagonalized squared unfolding matrix, which suppresses diagonal influence.Source: §3 · p. 13, §3.1 · p. 13

3.2.1 Procedure

  • A reliable subspace estimate permits rough recovery of all individual factors up to permutation, unlike matrix recovery's rotational ambiguity.The procedure repeatedly retrieves one factor and prunes redundant estimates.Source: §3.2.1 · pp. 13–14
  • Each retrieval round projects a random direction into the estimated subspace, transforms the tensor into a matrix, and extracts a leading singular vector and coefficient.The projection is intended to amplify the signal relative to missing-data and noise perturbations.Source: §3.2.1 · pp. 13–14, §3.2.2 · p. 14

3.2.2 Intuition

  • When factors are nearly orthogonal, the projected matrix's leading singular vector is expected to approach the factor with the largest projected coefficient.This intuition explains both the coefficient choice and why repeated rounds can retrieve one factor at a time.Source: §3.2.2 · p. 14

3.3 Other alternatives?

  • Randomly initialized gradient descent can be volatile because its expected progress depends quadratically on a potentially tiny truth correlation.The resulting variance may dominate the mean increment, while tensor power initialization faces analogous volatility and stringent perturbation requirements.Source: §3.3 · p. 15

4 Related work

Prior tensor-completion approaches trade statistical efficiency against computational cost: convex and sum-of-squares methods can be expensive or structurally inefficient, while nonconvex methods lack either optimal guarantees or near-linear complexity.

Related work

  • Unfolding-based convex relaxation can lose tensor structure and often has sample complexity that is sub-optimal relative to polynomial-time limits.The loss is especially severe for odd-order tensors.Source: §4 · p. 16
  • Tensor nuclear and atomic norm methods improve sample complexity but are computationally intractable, while sum-of-squares methods remain prohibitively expensive at large scale.The cited tensor nuclear norm and atomic norm computations, as well as high-level sum-of-squares relaxations, limit practical applicability.Source: §4 · p. 16
  • Existing nonconvex tensor-completion algorithms either lack optimal statistical guarantees or cost substantially more than a linear-time algorithm.Examples include iterative thresholding, alternating minimization, tensor SVD, manifold optimization, and block coordinate descent.Source: §4 · p. 16
  • The paper adapts ideas from nonconvex matrix recovery but requires more complex initialization and handles permutation rather than rotational ambiguity during local convergence.Leave-one-out analysis is the main theoretical tool supporting this tensor-specific treatment.Source: §4 · p. 16
  • The paper assumes non-adaptive uniform random sampling, whereas adaptive sampling may improve performance when the sampling mechanism is controllable.Fundamental criteria for perfect low-CP-rank completion are discussed separately in prior work.Source: §4 · p. 16
  • The proposed algorithmic ideas may also have implications for tensor decomposition, tensor factorization, regression, and sketching beyond completion.These connections are presented as potential implications rather than established results.Source: §4 · p. 17

5 Analysis

This section analyzes the initialization and convergence of vanilla gradient descent, establishing the conditions under which accurate initialization leads to statistically accurate solutions. It develops the supporting guarantees through subspace estimation, tensor-factor disentanglement, leave-one-out control, spectral gaps, magnitude estimation, and pruning.

5 Analysis

  • Under Theorem 2.8’s assumptions, the initialization meets vanilla gradient descent’s linear-convergence requirement, yielding the theorem from the analyses of convergence and initialization.The proof is organized around local convergence of gradient descent and statistical guarantees for the two initialization steps.Source: §5 · p. 17

5.1 Analysis for local convergence of GD

  • If initialization is reasonably accurate, vanilla gradient descent converges linearly to a solution with the desired statistical accuracy.The local-convergence argument relies on the noiseless loss behaving like a locally strongly convex and smooth function.Source: §5.1 · p. 17, §5.1.2 · p. 18

5.1.3 Leave-one-out gradient descent sequences

  • Leave-one-out gradient-descent sequences decouple each trajectory from sampling and noise at a coordinate subset, enabling control of every iterate’s rowwise closeness condition.This framework is motivated by low-rank matrix recovery analyses [MWCC17, CLL19] and removes randomness associated with locations involving coordinate m.Source: §5.1.3 · p. 18, §5.1.2 · p. 18

5.1.4 Key lemmas

  • The local-convergence proof is inductive: key hypotheses established at one iteration are shown to persist at the next with probability at least 1 −O(d−10).The initialization hypotheses hold with high probability up to a global permutation, after which the inductive lemmas establish the gradient-update conditions.Source: §5.1.4 · pp. 19–20

5.2.1 Key results

  • Algorithm 2 produces a reliable estimate of the subspace spanned by the true tensor factors under the stated sample-size, noise, and rank conditions.Lemma 5.7 quantifies proximity using both spectral norm and ∥· ∥2,∞, with the latter providing a stronger rowwise notion of closeness.Source: §5.2.1 · p. 21

5.2.2 Leave-one-out sequences for subspace estimation

  • Leave-one-out spectral-initialization sequences are independent of selected data and remain extremely close to the full subspace estimate, supporting subsequent statistical analysis.Their construction follows the leave-one-out principle and adapts the analysis of [CLC+20, Lemma 4].Source: §5.2.2 · pp. 21–22

5.3.1 Main results and leave-one-out sequences

  • Theorem 5.9 shows that Algorithm 3 returns tensor-factor estimates reasonably close to the ground truth up to a global permutation under the stated sample-size and noise conditions.Theorem 5.10 further establishes corresponding guarantees for the individual leave-one-out factor estimates across coordinates.Source: §5.3.1 · pp. 22–23
  • With probability exceeding 1−δ, Algorithm 3 and Algorithm 6 produce initial estimates U0 and U0,(m) satisfying hypotheses (47) at t = 0.This holds for any arbitrarily small constant δ > 0 under Theorem 2.8 assumptions.Source: §5.3.1 · p. 24

5.3.2 Analysis

  • The proof identifies a trial with a sufficiently large spectral gap for each factor, then uses incoherence and random restarts to recover all factors without duplication.The leading singular vector is shown close to the true factor in both ℓ2 and ℓ∞ norms, while leave-one-out estimates provide entrywise control.Source: §5.3.2 · pp. 24, 26, 27
  • The analysis further shows that the estimated factor magnitudes are accurate and that pruning returns one rough estimate for each tensor factor.Lemma 5.16 controls the magnitude estimate, and Lemma 5.17 establishes the final permutation-matched outputs of Algorithms 3 and 6.Source: §5.3.2 · pp. 26–27

6 Discussion

The discussion highlights the method’s efficient, statistically accurate recovery under well-conditioned, incoherent, constant-rank assumptions, while identifying rank, initialization, and uncertainty quantification as open boundaries.

6 Discussion

  • Under well-conditioned, incoherent, constant-rank assumptions, the method completes tensors with optimal statistical accuracy in nearly linear time.The paper presents this as a result not previously shown in the prior literature.Source: §6 · p. 27
  • The paper leaves three main directions open: reducing rank dependence, handling the over-complete regime r > d, and developing uncertainty quantification.The current spectral initialization fails unless r < d, while confidence intervals for missing entries are left for future work.Source: §6 · p. 27

A Proofs for local convergence of GD

  • The convergence analysis decomposes the Hessian expression into terms, bounds each term separately, and combines upper bounds for αi with a union bound, obtaining probability exceeding 1 − O(d−10).Source: §A.1 · p. 28, §A.1.5 · p. 33

A.1.1 Bounding α4

  • The α4 bound uses Cauchy–Schwarz together with incoherence and conditioning constraints, including r ≪ d/µ and κ ≍ 1.These conditions support a lower bound on α4 in the proof of Lemma 5.1.Source: §A.1.1 · pp. 28–29

A.1.2 Bounding α1

  • The α1 and α2 analyses rely on concentration inequalities and sample-size conditions such as p ≫ µ^2r^2d^-2 log d to control their contributions.The proof repeatedly uses high-probability bounds and derives related estimates for α1 and α2.Source: §A.1.2 · pp. 30–31, §A.1.3 · p. 31

A.1.4 Bounding α3

  • For α3, symmetry, triangle inequalities, and entrywise bounds reduce the analysis to uniform control over tensor terms before the final union bound.The proof invokes an operator-norm comparison lemma and sampling conditions such as p ≳ d^-3/2 log^3 d.Source: §A.1.4 · pp. 31–32

A.3 Proof of Lemma 5.3

The proof of Lemma 5.3 controls the clean-gradient deviation and sampling-noise terms using leave-one-out independence and concentration inequalities, then combines them into a high-probability bound.

A.3 Proof of Lemma 5.3

  • The proof decomposes the gradient error into α1 and α2, treating the clean objective through the fundamental theorem of calculus around the global optimizer.The path Ut(τ) remains within the conditions needed for Lemma 5.1, enabling the clean-gradient bound.Source: §A.3 · pp. 33–34
  • Leave-one-out iterates make sampled noise contributions conditionally independent, allowing matrix Bernstein bounds for the resulting zero-mean terms.The proof separately controls β1 and β2, with β3 treated similarly and β4 shown smaller under the iterate assumptions.Source: §A.3 · pp. 35–36
  • Combining the componentwise estimates yields a uniform high-probability control over the gradient error across modes and rank components.The argument sums over m and s after establishing bounds that hold for arbitrary indices.Source: §A.3 · p. 36

A.4 Proof of Lemma 5.4

The proofs of Lemmas 5.4–5.6 extend the leave-one-out concentration analysis to additional iterate differences and combine the resulting bounds to establish the local convergence ingredients.

A.4 Proof of Lemma 5.4

  • Lemma 5.4 bounds leave-one-out matrix terms row by row using independence, Cauchy–Schwarz, matrix Bernstein inequalities, and union bounds.The resulting estimates require sample-size conditions involving µ, r, d, logarithmic factors, and κ ≍ 1.Source: §A.4 · pp. 36, 38, 39
  • The proof controls four error terms separately and combines them under the sample-size condition p ≫ µ^3r^2d^-2 log^3 d.This produces a high-probability bound for the leave-one-out quantities.Source: §A.4 · pp. 37, 40

A.5 Proof of Lemma 5.5

  • Lemma 5.5 identifies α1 as the dominant term while treating α2 as negligible under the rank and sampling assumptions.The proof combines triangle and Cauchy–Schwarz inequalities to obtain the required bound uniformly over modes.Source: §A.5 · pp. 41, 43, 45

A.6 Proof of Lemma 5.6

  • Lemmas 5.4 and 5.5 are combined with sufficiently large constant ratios to obtain the high-probability estimate required by Lemma 5.6.The final step is stated on an event with probability at least 1 − O(d^-10).Source: §A.6 · p. 45

B.1 Proof of Lemma 5.12

The proof of Lemma 5.12 analyzes Gaussian fluctuations through their covariance structure, decomposes the covariance into positive-definite components, and applies concentration and union bounds.

B.1 Proof of Lemma 5.12

  • The fluctuation vector γ⋆τ is conditionally zero-mean Gaussian, so the proof studies its covariance matrix to control its order statistics.The covariance is examined conditional on the sampling pattern and noise.Source: §B.1 · pp. 45–46
  • The covariance decomposes into two positive-definite components, enabling separate analysis of the corresponding independent Gaussian vectors.One component is shown diagonally dominant, while both covariance matrices are positive definite.Source: §B.1 · p. 46
  • Gaussian concentration and union bounds control the smaller component uniformly over τ, while standard order-statistics arguments handle the independent component.The proof uses conditions including L ≍ r^2κ^2 log^3/2 r, r ≪ d, and κ ≍ 1.Source: §B.1 · p. 47
  • Combining the componentwise bounds establishes the stated inequalities for the fluctuation quantities in Lemma 5.12.The final claims follow by combining the bounds for the two Gaussian components with the triangle inequality.Source: §B.1 · p. 47

B.2 Proof of Lemma 5.13

This appendix proves Lemma 5.13 by establishing perturbation bounds that keep the relevant empirical matrices close to their population counterparts. It combines operator-norm and auxiliary estimates under the stated conditions with singular-vector perturbation arguments to complete the proof.

B.2 Proof of Lemma 5.13

  • Small operator-norm perturbations make the spectrum of M τ close to that of M ⋆τ, and Wedin’s theorem then yields ℓ2 proximity of their leading singular vectors.The argument treats Cτ and F τ as perturbations and uses Weyl’s inequality together with the condition Eop ≪1.Source: §B.2 · pp. 47–49
  • The leading singular vector and singular-value gap of M ⋆τ are characterized from the ordered coefficients γ⋆τ, providing the separation required for the perturbation argument.The proof identifies the leading singular vector of M ⋆τ and lower-bounds the gap between its two largest singular values.Source: §B.2 · pp. 48–49

B.3.1 Controlling F τ

  • The spectral norm of F τ is controlled by separately bounding its constituent terms using Gaussian concentration, incoherence, and the sampling condition p ≳µd−2 log4 d.The bounds rely on controlling ℓ∞ and ℓ2 norms of θ⋆τ and on the condition Ese ≪1/√r log d.Source: §B.3.1 · pp. 49–50

B.3.2 Controlling Cτ

  • The spectral norm of Cτ is bounded directly from its definition under the incoherence, conditioning, and auxiliary lemma assumptions.This establishes the remaining perturbation control needed alongside the F τ bound.Source: §B.3.2 · p. 51

B.4.1 Controlling α3

  • Lemma B.2 bounds the three error components α1, α2, and α3, which together control the rowwise comparison needed in Lemma 5.14.The α3 bound uses incoherence and Wedin’s theorem; α2 uses conditional Gaussian concentration; α1 follows from Weyl’s inequality and the sample-size, rank, and noise conditions.Source: §B.4.1 · p. 52, §B.4.2 · p. 54, §B.4.3 · p. 55

B.5 Proof of Lemma B.2

  • Under an independence simplification, the argument uses standard Gaussian concentration and matrix Bernstein inequalities, with probability exceeding 1 − O(d−10), and final control when p ≫µd−2 log5 d.Source: §B.5 · pp. 55–56
  • Under the sample-size and rank conditions, the preceding bounds are combined to advance the proof.Source: §B.5 · p. 56
  • The proof bounds the relevant operator expression using the definitions of M_τ and c_Mτ,(m), the operator norm, and the triangle inequality.Source: §B.5 · p. 56
  • For α_2, the argument combines (171) and (194) under the sample-size, noise, and rank conditions, then concludes using (204), (206), and (207).The proof also invokes Lemma 5.8 for a high-probability conclusion.Source: §B.5 · p. 57

B.6 Proof of Lemma 5.15

The proofs control successive perturbation terms using concentration, spectral perturbation bounds, and incoherence conditions. These bounds establish the lemma’s claims, align global signs, and combine controls for β1, β2, and β3.

B.6 Proof of Lemma 5.15

  • The proof bounds separate terms using Wedin’s theorem for β1 and β2, Weyl’s inequality for denominator terms, and Lemma B.3 for the numerator term.One bound holds as long as p ≫ μ²r²d⁻² log² d.Source: §B.6 · pp. 57–58

B.7 Proof of Lemma B.3

  • Lemma B.3 controls the numerator term by decomposing it into α1, α2, and remaining entries, then applying incoherence and Bernstein bounds.The resulting estimate is obtained by substituting the component bounds into the target inequality.Source: §B.6 · p. 58, §B.7 · pp. 60–61

B.8 Proof of Lemma 5.16

  • When Eproj ≪1 under the sample-size, noise, and rank condition, the proof concludes that the relevant global signs coincide.The proof decomposes the remaining claim into three terms and upper bounds them separately.Source: §B.8 · pp. 61–62

B.8.1 Controlling β1

  • β1 is controlled by expanding linear and quadratic terms in Δ1, with ∥Δ1∥2 ≲ Eproj and Eop ≪ 1 yielding the required bound.The final combination uses the sample-size, noise, and rank conditions to ensure Eproj ≪ 1.Source: §B.8.1 · p. 62

B.8.2 Controlling β2

  • β2 is bounded through symmetry, Lemma D.1, matricization-based spectral-norm control, and the condition Eproj ≪ 1.The proof explicitly uses that the tensor spectral norm is no larger than the spectral norm of its matricization.Source: §B.8.2 · p. 63

B.8.3 Controlling β3

  • β3 is bounded using incoherence, and combining the three component estimates completes the proof under μ ≤ d and the stated rank conditions.The final step aggregates the bounds from β1, β2, and β3.Source: §B.8.3 · p. 63, §B.8.4 · p. 63

B.9 Proof of Lemma 5.17

The proof ensures that pruning selects consistent trials and removes duplicate factor estimates. It then transfers the resulting factor and weight accuracy through a permutation alignment to establish Corollary 5.11.

B.9 Proof of Lemma 5.17

  • Prune() selects the pair with the largest spectral gap, so sufficient separation from the second-largest gap makes Algorithms 3 and 6 choose the same index τ.The leave-one-out perturbation must remain smaller than this spectral-gap separation.Source: §B.9 · p. 64
  • With high probability, the leave-one-out estimates correspond to the same trials and Gaussian vectors, yielding the uniform bounds in (69a), (69b), and (69c).This conclusion holds across all m ∈ [d] under the stated sample-size, noise, rank, and spectral-gap conditions.Source: §B.9 · p. 64
  • The pruning procedure removes duplicate factor estimates because incoherence separates factors that are close to the same estimate from distinct factors.Under μ ≪ d and Eproj ≪ 1, the argument secures an estimate for every tensor factor.Source: §B.9 · p. 64

B.10 Proof of Corollary 5.11

  • Corollary 5.11 follows by combining the preceding high-probability estimates with a permutation aligning the recovered and true factors.The proof uses κ ≍ 1 and δ ≪ 1 to transfer factor and weight comparisons.Source: §B.10 · p. 65

C Proof of Corollary 2.9

The proof of Corollary 2.9 transfers factor estimates into tensor reconstruction guarantees under permutation alignment. Auxiliary lemmas provide the probabilistic, incoherence, projection, and random-tensor bounds used throughout.

C Proof of Corollary 2.9

  • The factor-matching permutation remains unchanged over iterations once Theorem 2.8’s estimation accuracy holds, allowing a fixed alignment with U⋆.The proof then analyzes Euclidean and ℓ∞ reconstruction losses through perturbations Δ and Δs.Source: C Proof of Corollary 2.9 · pp. 65–67
  • The Euclidean-loss argument controls tensor perturbation terms using Frobenius bounds on Δ and the established lower bound on ∥T⋆∥F.The resulting estimates combine equations (236)–(238) under δ ≪ r^-1.Source: C Proof of Corollary 2.9 · p. 66
  • The ℓ∞-loss argument bounds the entrywise tensor perturbation by expanding rank-one terms and combining equations (240)–(242).The conclusion follows under 0 < δ ≪ r^-1 and the incoherence condition μ/d ≪ 1.Source: C Proof of Corollary 2.9 · pp. 65–67

D Auxiliary lemmas

  • The auxiliary section collects lemmas controlling Gaussian order statistics, subspace projections, Bernoulli sampling variables, and random tensor perturbations.These results are stated under explicit sampling, incoherence, rank, and probability conditions and are used in the main proofs.Source: D Auxiliary lemmas · p. 67, §D.1 · pp. 67–68

1. To begin with, the incoherence condition (8b) gives

  • The incoherence-based auxiliary bounds control inner products, row norms, and matrix norms of the factor-related matrices under rank and incoherence restrictions.The argument invokes conditions such as r ≤ d/μ and μ/d ≤ c1.Source: §1 · pp. 69–70, §3 · p. 70

D.3.1 Proof of Lemma D.2

This section develops the asymmetric-tensor extension and its supporting concentration-based analysis, including spectral initialization, regularized gradient descent, and bounds for factor and tensor recovery under independent sampling and sub-Gaussian noise.

D.3.1 Proof of Lemma D.2

  • The proof of Lemma D.2 uses the tensor spectral norm’s 1-Lipschitz property and concentration inequalities to obtain high-probability bounds.The argument combines mean control, Bernstein bounds, AM-GM, and Talagrand’s inequality for bounded independent entries.Source: §D.3.1 · pp. 70–72

D.3.2 Proof of Corollary D.3

  • Corollary D.3 applies Lemma D.2 to sampled tensors and handles unbounded noise through truncation, using symmetry to preserve zero mean.The resulting high-probability event completes the corollary’s claim.Source: §D.3.2 · pp. 72–73

D.4 Proof of Lemma D.4

  • Lemma D.4 controls a zero-mean random matrix with independent entries via truncated matrix Bernstein and matrix Bernstein inequalities.The conclusion holds under p ≳ d^-2 log^3 d and µ log^2 d ≲ d.Source: §D.4 · pp. 73–74

D.5 Proof of Lemma D.5

  • Lemma D.5 derives its Gaussian comparison bound using Gaussian tails, a union bound, and monotonicity of the interval-to-tail ratio f_ε(x).The proof concludes after selecting L and B sufficiently large and applying Gaussian concentration.Source: §D.5 · pp. 75–76

D.6 Proof of Lemma D.6

  • Lemma D.6 uses the assumption u0 lies in span(U) together with the Pythagorean theorem.These identities provide the geometric relation required by the lemma.Source: §D.6 · p. 76

D.7–D.8 Proofs

  • Lemmas D.7 and D.8 establish high-probability concentration bounds with Bernstein inequalities for sampled quantities under p ≳ d^-2 log d and p ≳ d^-2 log^2 d, respectively.Lemma D.8 uses independent sub-Gaussian noise and sub-exponential norms.Source: §D.7 · p. 77, §D.8 · p. 77

D.9–D.10 Proofs

  • Lemmas D.9 and D.10 control potentially unbounded random variables by truncation, then apply Bernstein inequalities and high-probability agreement between original and truncated variables.The D.9 bound requires p ≳ d^-2 log^2 d and µ log^2 d ≲ d; D.10 obtains probabilities of order 1 − O(d^-20).Source: §D.9 · p. 78, §D.10 · p. 79

E Extension to asymmetric tensors; E.1 Problem settings

  • The asymmetric extension generalizes the algorithm and analysis to rank-r tensors in R^{d1×d2×d3} with independently sampled entries and independent zero-mean sub-Gaussian corruption.It seeks faithful factor recovery modulo global permutation and signs, together with reliable tensor estimation, while accounting for global scaling ambiguity.Source: E Extension to asymmetric tensors · p. 79, §E.1 · pp. 79–80

E.2 Algorithms

  • The regularization term helps keep the sizes of U, V, and W close during optimization.This balancing device is motivated by techniques used in nonconvex rectangular matrix recovery [TBS+16, ZL16, CLL19].Source: §E.2 · p. 80
  • For asymmetric tensors, the algorithm combines spectral initialization with gradient descent minimizing the regularized loss in Algorithm 7.Algorithm 7 invokes Algorithms 8–9.Source: §E.2 · p. 80
  • Closed-form expressions for the gradients of g(U, V, W) are provided to facilitate implementation of the nonconvex gradient-descent procedure.The gradients are specified for each component index i and use the ×1, ×2, and ×3 operations defined earlier.Source: §E.2 · p. 80

E.3 Numerical experiments

Numerical experiments evaluate the proposed tensor-completion methods on synthetic noiseless and noisy data, asymmetric settings, and a simulated MRI tensor. The reported results show geometric convergence in synthetic experiments and favorable reconstruction performance on MRI data.

Asymmetric experiments

  • The methods are extended experimentally to asymmetric tensors through spectral initialization, factor retrieval, pruning, and gradient descent procedures.The asymmetric procedures estimate separate factor matrices for the three modes.Source: §E.3 · pp. 81–82

Synthetic experiments

  • The numerical setup generates Gaussian noise and defines SNR from the tensor signal and noise level.The algorithmic parameters include L = r^2, ϵth = 0.4, and t0 = 100.Source: §E.3 · p. 81
  • The experiments evaluate tensor and factor errors, including relative Euclidean and ℓ2,∞ errors for the reconstructed tensor.Factor estimates are evaluated up to global signs and permutations.Source: §E.3 · p. 81
  • Synthetic estimation errors decay geometrically in the noiseless case and continue doing so in the noisy case until reaching an error floor.The experiments use d1 = 100, d2 = 150, d3 = 200, r = 4, and p = 0.05 for Figure 2.Source: §E.3 · p. 81

MRI experiments

  • On simulated MRI data, the method reconstructs a low-rank tensor formed from the top 36 components, whose energy accounts for 85% of the original tensor.Table 2 reports relative ℓ2 and ℓ2,∞ reconstruction errors over varying sampling probabilities and SNRs.Source: §E.3 · p. 81
  • The MRI experiments report favorable low-rank tensor reconstruction performance and suggest applicability beyond the theorem assumptions.The data tensor has dimensions 181 × 217 × 181 and includes simulated noise.Source: §E.3 · pp. 81–82

E.4 Analysis ideas

The analysis explains the asymmetric extension through local geometry of a noiseless regularized loss and a two-stage initialization scheme. It identifies the conditions supporting local convergence and sketches how factor retrieval and concentration arguments establish the required initialization.

E.4 Analysis ideas

  • The incoherence parameters, dimensions, and condition number determine the assumptions used to analyze asymmetric tensor completion.The analysis defines µ, dmin, and dmax for this purpose.Source: §E.4 · p. 82
  • The asymmetric analysis has two core components: favorable local geometry of the noiseless loss and sufficiently accurate initial factor estimates.These components are intended to place gradient descent inside a locally strongly convex and smooth region.Source: §E.4 · pp. 82–83
  • The noiseless regularized loss is locally strongly convex and smooth when the stated sampling, rank, regularization, and neighborhood conditions hold.The regularization balances the sizes of the three tensor factors and is crucial for these local properties.Source: §E.4 · pp. 83–84
  • In the balanced regime d1 ≍ d2 ≍ d3 ≍ d with µ, r ≍ 1, the condition reduces to p ≫ d^-3/2 log^3 d, while gradient descent then converges linearly from a suitable initialization.The conclusion is presented as analogous to the symmetric case.Source: §E.4 · p. 84
  • Initialization first estimates the factor subspace, then retrieves individual factors using random contractions, spectral gaps, repeated restarts, and pruning.A sufficiently accurate subspace estimate enables factor estimates close to the ground truth in both ℓ2 and ℓ∞ norms.Source: §E.4 · pp. 84–85
  • The asymmetric extension is presented as an outline rather than a complete proof because the full argument is lengthy and involves more cumbersome notation.The paper states that the complete proof is omitted while identifying the steps needed to adapt the symmetric analysis.Source: §E.4 · pp. 83, 85

E.5 Proof of Lemma E.2

  • The proof bounds several error terms to establish the local geometric property with high probability under the asymmetric assumptions.The proof treats β1 as dominant and controls β2, β3, and β4 through concentration and perturbation arguments.Source: §E.5 · p. 86, Bounding β2 · p. 88, Bounding β4 · pp. 89–90
Loading 1911.04436v2…