Source-linked AI summary
Provable Tensor Factorization with Missing Data
Prateek Jain, Sewoong Oh
TL;DR
The paper studies how to exactly recover low-rank tensors when many entries are missing. It proposes an alternating-minimization method with provably good initialization and obtains exact recovery from O(n^{3/2} r^5 log^4 n) samples under standard assumptions.
Problem
The paper asks how many sampled entries are needed to efficiently and exactly reconstruct low-rank tensors with missing data.
Method
The method uses robust tensor power initialization followed by alternating minimization that iteratively refines all r components.
Results
O(r^5 n^{3/2}(log n)^4) samples suffice for arbitrarily small normalized error, and experiments indicate tight dimensional dependence up to poly-logarithmic factors.
Takeaways & Limitations
Recovery can succeed even when most tensor fibers are entirely unsampled, unlike matrix completion where every fiber requires at least one sample.
Takeaways & Limitations
The theoretical method is restricted to orthonormal tensor decompositions; extending the analysis to non-orthogonal CP models remains open.
Abstract
from arXiv · showhide
We study the problem of low-rank tensor factorization in the presence of missing data. We ask the following question: how many sampled entries do we need, to efficiently and exactly reconstruct a tensor with a low-rank orthogonal decomposition? We propose a novel alternating minimization based method which iteratively refines estimates of the singular vectors. We show that under certain standard assumptions, our method can recover a three-mode $n\times n\times n$ dimensional rank-$r$ tensor exactly from $O(n^{3/2} r^5 \log^4 n)$ randomly sampled entries. In the process of proving this result, we solve two challenging sub-problems for tensors with missing data. First, in the process of analyzing the initialization step, we prove a generalization of a celebrated result by Szemerédie et al. on the spectrum of random graphs. Next, we prove global convergence of alternating minimization with a good initialization. Simulations suggest that the dependence of the sample size on dimensionality $n$ is indeed tight.
1 Introduction
The paper studies exact completion and factorization of low-rank orthogonal tensors from randomly revealed entries, addressing missing-data settings where higher-order methods lack guarantees. It introduces alternating minimization with iterative component refinement and proves recovery under incoherence and orthogonality assumptions.
- Motivation: Higher-order tensor completion lacks the theoretical guarantees available for matrices and can suffer from local minima.The problem is also computationally difficult because tensor factorization is NP-hard in general.
- Problem formulation: The model is a symmetric third-order tensor with a small-rank orthonormal CP decomposition and incoherent unit-norm components.The techniques are stated to extend to non-symmetric and higher-order tensors.
- Algorithm: The algorithm initializes with Robust Tensor Power Method estimates and then iteratively refines all r components through alternating minimization.Refining all components contrasts with sequential deflation, where earlier estimates are not revisited.
- Main result: Theorem 1.1 guarantees a unique optimum and an estimate within ε after log2(4√r ∥T∥F/ε) iterations.The guarantee applies to rank-r symmetric tensors with orthogonal CP decompositions satisfying µ-incoherence.
- Main result: O(r^5 n^3/2 (log n)^4) samples suffice for arbitrarily small normalized error under constant incoherence and well-conditioned factors.The method uses O(r|Ω| log(r∥T∥F/ε)) operations after initialization, so complexity is nearly linear in the sample size when r ≪ n.
- Implications: Most tensor fibers may contain no samples while recovery remains possible, and simulations indicate tight dimensional dependence up to logarithmic factors.The empirical sample scaling is reported as r1/2 n3/2 log n for r = O(√n), while the theoretical rank dependence is loose.
2 Analysis of the Alternating Minimization Algorithm
The analysis combines robust tensor power initialization with alternating minimization to obtain geometric convergence for incoherent, well-conditioned orthogonal tensors. The resulting sample and computational guarantees support exact or arbitrarily accurate recovery under the paper’s assumptions.
- Proof strategy: The proof has two main components: analyzing initialization and proving alternating-minimization convergence from a sufficiently accurate starting point.These analyses are combined to prove the main recovery theorem.
- Initialization: (1/p)P_Ω(T) is shown to approximate T in spectral norm, enabling robust tensor power initialization from incomplete observations.The normalization compensates for missing entries before applying the robust power method.
- Initialization: O((σmax/σmin)^2 r^5 µ^6 (log n)^4) scaling in α suffices for robust tensor power initialization with high probability.The method uses O(log r + log log α) power-method iterations, while requiring multiple random initializations.
- Alternating minimization: Geometric decay of a distance function yields linear convergence of Algorithm 1 when the initial iterate is sufficiently close and remains incoherent.The required neighborhood is bounded by a condition involving r and the tensor’s minimum and maximum component weights.
- Alternating minimization: The fit error closely tracks normalized RMSE, making observed-entry fit a practical stopping criterion until machine precision.This relationship is reported for the estimate produced at each iteration.
- Algorithmic novelty: The algorithm jointly refines all r components rather than using sequential deflation, addressing interactions among estimates during alternating minimization.The analysis must bound errors from components held fixed while another component is updated.
- Convergence and complexity: O(log^2(4r^1/2∥T∥F/ε)) iterations suffice to reach error ε, while sample complexity increases by only a log(1/ε) factor because convergence is linear.Each alternating-minimization iteration requires O(r|Ω|) operations.
A Proof of Theorem 2.1 for Initialization Analysis
The initialization analysis bounds the deviation of the sampled tensor by separating light and heavy triples. Discretization, concentration inequalities, and random-hypergraph structure together establish the required spectral control.
- A Proof of Theorem 2.1 for Initialization Analysis: The proof reduces spectral-norm control to discretized vectors in eS_n1, eS_n2, and eS_n3, then applies a union bound.The discretized sets cover the relevant vector balls and are small enough for uniform probabilistic control.
- A Proof of Theorem 2.1 for Initialization Analysis: Light triples are bounded using concentration inequalities, while heavy triples are bounded using the discrepancy property of random tripartite hypergraphs.This split addresses the failure of direct concentration when vector entries exceed their typical O(1/√n) magnitude.
- A Proof of Theorem 2.1 for Initialization Analysis: The light-triple contribution is bounded by C T_max √(n1n2n3) p √ϵ, up to logarithmic terms from the discretization union bound.Chernoff concentration controls the deviation for each discretized triple of vectors.
- A Proof of Theorem 2.1 for Initialization Analysis: The resulting bounds establish the spectral estimate needed for Theorem 2.1.The proof combines the light- and heavy-triple estimates with Lemma A.1 using an appropriate constant discretization parameter.
- A Proof of Theorem 2.1 for Initialization Analysis: Choosing p = Θ(ϵ/n^1.5) makes the heavy-triple contribution dominant over the light-triple contribution in the relevant regime.The text notes that heavy triples can contribute Ω(1), exceeding the light contribution by a factor of √n under the alternative scaling.
A.2 Bounding the contribution of heavy triples
Heavy triples are controlled by decomposing vector entries into magnitude classes and applying bounded-degree and discrepancy properties of the sampling hypergraph. The resulting contribution is O(√ϵ(log n)^2) under the stated regime.
- A.2 Bounding the contribution of heavy triples: Each magnitude-class combination is bounded using either discrepancy or bounded-degree properties of the sampling hypergraph.The proof treats cases according to which structural property applies to the corresponding subsets.
- A.2 Bounding the contribution of heavy triples: A random tripartite hypergraph satisfies the bounded-degree and discrepancy properties with probability at least 1 − n^−5.The deterministic heavy-triple bound therefore applies to the random sampling pattern with high probability.
- A.2 Bounding the contribution of heavy triples: The heavy-triple contribution is analyzed by partitioning indices according to the magnitudes of the corresponding vector entries.The partition creates magnitude classes indexed by u, v, and w for the three tensor modes.
- A.2 Bounding the contribution of heavy triples: For ϵ ≥ log n, the heavy-triple contribution is O(√ϵ(log n)^2).The bound follows after handling the discrepancy cases and the bounded-degree subcases.
A.3 Proof of the bounded degree and discrepancy properties in Lemma A.3
The proof establishes bounded-degree and discrepancy properties for random tripartite hypergraphs through concentration inequalities and union bounds over nodes, pairs, and vertex subsets.
- A.3 Proof of the bounded degree and discrepancy properties in Lemma A.3: Bernstein-type concentration bounds control sums of sampling indicators and are combined with union bounds over subset choices.The probability allocation includes a 1/(n1n2n3) term to compensate for the union bound.
- A.3 Proof of the bounded degree and discrepancy properties in Lemma A.3: Union bounds over node pairs make the bounded-degree estimates hold uniformly with probability at least 1 − δ/2.The argument separately controls the relevant degree variables before combining the probability guarantees.
- A.3 Proof of the bounded degree and discrepancy properties in Lemma A.3: When at least two subsets are large, bounded degree yields the first discrepancy condition; smaller subsets require a separate concentration argument.The proof divides the discrepancy analysis according to the size of the smallest subsets.
- A.3 Proof of the bounded degree and discrepancy properties in Lemma A.3: For the small-threshold regime, e(A1,A2,A3) ≤ 4 ē(A1,A2,A3) holds with probability at least 1 − δ.For the complementary regime, the proof obtains a uniform bound involving t′ ē(A1,A2,A3).
A.4 Proof of Thresholding
The thresholding analysis defines a modified vector by clipping entries above the incoherence threshold while preserving controlled norm behavior.
- A.4 Proof of Thresholding: For a µ-incoherent unit vector, f_uℓ uses sign(uℓ(i)) µ/√n whenever |uℓ(i)| exceeds µ/√n.The construction thresholds large coordinates at the incoherence scale.
- A.4 Proof of Thresholding: The thresholded vectors satisfy 1 − α ≤ ||f_uℓ||_2 ≤ 1 under the stated approximation condition.The norm remains close to one after thresholding.
B.1 Main theorem for rank-two analysis
For a rank-2 orthonormal tensor with equal singular values, the analysis establishes linear convergence of Algorithm 1 under incoherence and sampling conditions.
- The analysis considers a rank-2 orthonormal tensor with equal singular values and µ-incoherent singular vectors.The singular values are fixed to one for simplicity.
- Theorem B.1 assumes the current estimates are 2µ-incoherent and requires p ≥ Cµ^3 log^2 n.Under these conditions, the theorem analyzes the iterative estimates produced by Algorithm 1.
- The update is expressed in vector form using diagonal matrices B, C, F, and G.The proof separates the resulting update error into individual terms.
- The error bounds hold with high probability, including probabilities at least 1 − 2/n^9 and 1 − 10/n^9.These bounds are combined with the distance assumption to obtain the desired result.
B.2 Technical lemmas for rank-two analysis
The technical lemmas control incoherence, sampling-dependent matrix terms, and error differences needed for the rank-two convergence proof.
- All iterates remain 2µ-incoherent, so incoherence increases by at most a global constant factor.This property enables effective bounds on the update errors.
- Lemma B.3 relates squared inner products of perturbed orthogonal vectors to the perturbation norms.It uses u = u∗ + du and v = v∗ + dv with bounded perturbations.
- Lemma B.4 bounds a coupled update-error difference by 8γ∥u2 − u∗_2∥2 with probability at least 1 − 4/n^9.The bound applies under Theorem B.1’s assumptions and a stated lower bound on p.
- The proof expands perturbed inner products and separates diagonal-matrix error terms into components involving du2.This decomposition handles terms whose individual magnitudes may be small but whose difference still requires control.
- Auxiliary lemmas impose incoherence and sampling conditions involving µ, γ, and logarithmic factors in n.These lemmas provide the probabilistic controls used for the diagonal matrices and update bounds.
- The vector-update analysis applies additional bounds for p ≥ Cµ^3(log^2 n)/(γ^2 n^3/2).The assumptions include bounded norms and incoherence for the vectors entering the estimates.
B.3 Proofs of Technical Lemmas
The technical-lemma proofs use Bernstein’s inequality and concentration bounds to control sampling-induced diagonal-matrix deviations.
- Bernstein’s inequality is repeatedly used to derive concentration bounds for the sampling-dependent quantities.The proofs invoke it directly in multiple technical-lemma arguments.
- Lemma B.8 bounds each diagonal entry using separate controls for B(i, i) and R(i, i).A union bound then converts the entrywise estimates into a norm bound.
B.4 Proof of Theorem 2.3 and general rank-r analysis of alternating minimization
The general rank-r analysis proves contraction of the alternating-minimization error under sufficiently accurate initialization, sampling, and controlled perturbations.
- The proof establishes an error bound for every component q of the normalized iterate ut+1.The argument is formulated in terms of the distance between current and target factors and singular values.
- The update for c uq is written as a vector update, whose error terms are then decomposed for separate control.This extends the rank-two proof strategy to the general rank-r setting.
- The sampling condition p ≥ (Cµ^3(log n)^2)/(γ^2 n^3/2) supports the high-probability bounds used in the update analysis.The cited bound holds with probability at least 1 − 2/n^10.
- Choosing γ relative to r and the singular-value ratio yields high-probability bounds for the general update.The proof records probabilities at least 1 − 1/n^8 and 1 − 3/n^8 for successive controls.
- The theorem’s first part follows by expressing the next-iterate distance as the maximum componentwise scaled distance.The second part follows directly from Lemma B.9.
B.5 Technical lemmas for general rank-r analysis
The technical lemmas combine update equations, bounds, and assumptions from Theorem 2.3 to establish high-probability intermediate results for the general rank-r analysis.
- B.5 Technical lemmas for general rank-r analysis: The lemmas analyze the update defined by (31) under the conditions of Theorem 2.3.The analysis uses the definitions of B, C, F_ℓ, and G_ℓ from (33).
- B.5 Technical lemmas for general rank-r analysis: The bounds use diagonal estimates for B, C, F_ℓ, and G_ℓ together with the distance bound in (43).These ingredients support the second inequality in one of the technical derivations.
- B.5 Technical lemmas for general rank-r analysis: One stated result holds with probability at least 1 − 4/n^9 under the assumptions on T and p from Theorem 2.3.Another displayed assumption gives probability at least 1 − 1/n^9 for the update analysis.
- B.5 Technical lemmas for general rank-r analysis: An expansion in (48) decomposes the relevant quantity into F_ℓ(i, i) and three terms D1(i, i), D2(i, i), and D3(i, i).The resulting expressions are combined with equations (45)–(47) and related bounds.
- B.5 Technical lemmas for general rank-r analysis: Several lemmas conclude by combining preceding inequalities, Lemmas B.7–B.8, and the triangular inequality.These steps complete the stated technical bounds.