Source-linked AI summary
On Tensor Completion via Nuclear Norm Minimization
Ming Yuan, Cun-Hui Zhang
TL;DR
Recovering low-rank tensors from partial observations is difficult because higher-order tensor decompositions are delicate, while unfolding tensors into matrices may not exploit their structure. The paper analyzes direct tensor nuclear norm minimization using new algebraic and probabilistic tools, and proves improved sample-size requirements for recovery. Its scope is centered primarily on third-order tensors, with higher-order extensions requiring more involved analysis.
Problem
Tensor completion lacks an equally straightforward extension of matrix-completion methods because higher-order tensor rank and decomposition are ambiguous, and matricization may be suboptimal.
Method
The paper directly minimizes a tensor nuclear norm subject to observed-entry constraints and develops tensor-specific subdifferential characterizations and concentration techniques.
Results
The direct approach has a smaller sample-size requirement than matricization; for nearly cubic tensors it is essentially r^1/2(d log d)^3/2 versus r(d log d)^2.
Takeaways & Limitations
The results demonstrate benefits from not treating tensors as matrices and provide techniques potentially useful for other tensor problems.
Takeaways & Limitations
The analysis focuses primarily on third-order tensors; higher-order extensions are possible in principle but become much more tedious and harder to describe.
Abstract
from arXiv · showhide
Many problems can be formulated as recovering a low-rank tensor. Although an increasingly common task, tensor recovery remains a challenging problem because of the delicacy associated with the decomposition of higher order tensors. To overcome these difficulties, existing approaches often proceed by unfolding tensors into matrices and then apply techniques for matrix completion. We show here that such matricization fails to exploit the tensor structure and may lead to suboptimal procedure. More specifically, we investigate a convex optimization approach to tensor completion by directly minimizing a tensor nuclear norm and prove that this leads to an improved sample size requirement. To establish our results, we develop a series of algebraic and probabilistic techniques such as characterization of subdifferetial for tensor nuclear norm and concentration inequalities for tensor martingales, which may be of independent interests and could be useful in other tensor related problems.
1 Introduction
Tensor completion seeks to recover large low-rank tensors from sampled entries, but extending matrix-completion ideas is difficult because higher-order tensor rank and decomposition are ambiguous. The paper studies direct tensor nuclear norm minimization and shows that it can require fewer samples than matricization-based approaches.
- Problem: Tensor completion recovers a large tensor from observed entries when the tensor has a low-rank structure.Applications include hyperspectral imaging, computed tomography, radar processing, audio classification, and text mining.
- Problem: Higher-order tensor completion is subtle because concepts such as rank and singular value decomposition become ambiguous.A common response is to unfold tensors into matrices and apply matrix nuclear norm methods.
- Existing approach: Matricization minimizes the sum of nuclear norms of the three mode unfoldings subject to matching the observed entries.The formulation uses the ranks r_j of the mode-j unfoldings in its sample-complexity analysis.
- Proposed approach: The proposed approach instead defines a tensor nuclear norm through duality with the tensor spectral norm and minimizes it under the observed-entry constraints.This is a convex program directly over third-order tensors.
- Result: For nearly cubic tensors, the direct method requires essentially r^1/2(d log d)^3/2 samples, compared with r(d log d)^2 for matricization.The improvement is emphasized when d is large and r is relatively small.
- Analysis: The tensor analysis develops new algebraic and probabilistic tools because standard matrix subdifferential and martingale-concentration techniques do not directly apply.The paper uses concentration bounds for sums of random tensors and different strategies for low-rank and sparse-support tensors.
2 Tensor
This section develops tensor-specific decomposition, projection, nuclear-norm subdifferential, and coherence tools needed for tensor completion analysis.
- Decomposition: Higher-order tensor decompositions may be nonunique, but the linear spaces spanned by factor-matrix columns are uniquely defined.These marginal spaces determine the Tucker ranks r1(X), r2(X), and r3(X).
- Decomposition and Projection: Marginal multiplication applies a matrix to one tensor coordinate, while tensor projections apply mode-specific projections to the factor matrices.For example, M ×1 X = [MA, B, C] and (P1 ⊗ P2 ⊗ P3)X = [P1A, P2B, P3C].
- Subdifferential: Tensor nuclear-norm analysis requires a subdifferential characterization because higher-order tensors lack a corresponding spectral decomposition.The paper introduces a relaxed sufficient characterization using tensor projections and a bounded orthogonal component.
- Subdifferential: The relaxed tensor subgradient condition restricts the orthogonal component to spectral norm at most 1/2, unlike the matrix condition’s bound of 1.The authors note that 1/2 could be improved but do not sharpen it because the existing constant suffices for their analysis.
- Coherence: The paper develops rank- and coherence-based bounds connecting tensor quantities such as α(X) with marginal-space structure and Tucker ranks.These bounds support the later recovery analysis under ordered Tucker ranks r1(X) ≤ r2(X) ≤ r3(X).
- Coherence: Tensor completion assumes low coherence, measured through the coherence of the three marginal spaces and an additional tensor coherence quantity α(X).The recovery setting considers tensors satisfying μ(T) ≤ μ0 and α(T) ≤ α0.
3 Exact Tensor Recovery
The section establishes exact tensor recovery through a tensor nuclear-norm program and a dual-certificate argument, then derives high-probability conditions under which recovery succeeds.
- 3.1 Recovery with a Dual Certificate: Exact recovery is formulated as solving a convex tensor nuclear-norm minimization problem from uniformly sampled entries.The sampling operator retains observed entries and zeros unobserved ones.
- 3.1 Recovery with a Dual Certificate: A dual certificate G supported on Ω, satisfying QT G = W and ∥QT ⊥G∥ < 1/2, certifies exact recovery.The certificate is constructed approximately using a strategy analogous to the matrix golfing scheme.
- 3.1 Recovery with a Dual Certificate: Invertibility of PΩ on the range of QT, together with the certificate conditions, forces any feasible perturbation to vanish and yields bT = T.The proof uses the relation between QT ∆ and QT ⊥∆ to conclude exact equality.
- 3.2 Construction of a Dual Certificate: The proof constructs an iid uniformly distributed sequence, partitions it into subsequences, and controls the resulting operators using probabilistic bounds.The construction supports the approximate dual certificate and its required spectral and maximum-norm estimates.
- 3.4 Proof of Theorem 1: Theorem 1 follows by choosing τ and verifying the concentration conditions for sufficiently large constants and dimensions.The proof reduces the stated theorem to bounds established through Lemmas 4–7.
4 Concentration Inequalities for Low Rank Tensors
This section develops concentration inequalities for low-rank tensors, handling dependent and iid tensor sequences through operator-based martingale and Bernstein arguments.
- Low-Rank Tensor Concentration: Lemma 5 treats concentration for a sequence of dependent tensors, whereas Lemma 6 treats a sequence of iid tensors.The distinction determines which probabilistic tools are applied.
- Low-Rank Tensor Concentration: The analysis defines martingale differences and applies a matrix martingale Bernstein inequality to random self-adjoint operators.The operators arise from sampled tensor entries and their conditional expectations.
- Low-Rank Tensor Concentration: The rank of QT is characterized through its decomposition into orthogonal projections, providing the effective dimension used in the concentration bounds.The resulting rank controls the variance and complexity terms in the estimates.
- Low-Rank Tensor Concentration: For low-rank tensors, Bernstein inequalities bound sampled tensor quantities under coherence and maximum-norm conditions.The proof uses iid scalar variables for one estimate and matrix Bernstein for another.
- Low-Rank Tensor Concentration: These bounds yield the required inequalities through a union-bound argument.The proof combines the scalar and operator concentration estimates.
5 Concentration Inequalities for Sparse Tensors
This section establishes concentration inequalities for sparse tensors by discretizing spectral-norm maximization, exploiting bounded support aspect ratio, and controlling entropy and random sums.
- Sparse Tensor Concentration: The sparse-tensor analysis bounds ∥RℓX∥ for iid sampled entries when X lies in the tangent space and has small maximum norm.The proof begins with symmetrization and reduces the problem to bounding random tensor spectral norms.
- Sparse Tensor Concentration: A thinning method discretizes unit-ball vectors into binary digitalized vectors with entries 0 or ±2^(-ℓ/2).This reduces continuous spectral-norm maximization to a finite collection of structured vectors.
- Sparse Tensor Concentration: The tensor spectral norm is reduced to maximization over discretized vectors and then decomposed according to entry magnitudes.Entropy bounds control the number of components in this decomposition.
- Sparse Tensor Concentration: The maximum aspect ratio of the support is the largest ℓ0 norm of its fibers, and uniformly sampled supports have a small aspect ratio with high probability.Lemma 10 supplies a probabilistic bound for the support aspect ratio.
- Sparse Tensor Concentration: The resulting bounds are applied under explicit parameter conditions to complete the sparse-tensor concentration argument.The final probability estimate is obtained after selecting parameters satisfying the stated inequalities.
6 Discussions
The discussion emphasizes the benefits of direct tensor nuclear-norm minimization and explains how the third-order analysis relates to higher-order tensors.
- 6 Discussions: The paper studies nuclear-norm minimization for large tensors with low Tucker ranks and reports benefits from not treating tensors as matrices.This contrasts direct tensor treatment with the popular matricization strategy.
- 6 Discussions: The analysis focuses primarily on third-order tensors, while extension to higher orders is possible but substantially more tedious and difficult to describe.A simpler strategy is outlined for higher-order tensors with similar sample-size requirements.
- 6 Discussions: For hypercubic higher-order tensors with bounded Tucker ranks, grouping modes produces a nearly cubic third-order tensor with bounded Tucker ranks.The resulting dimensions are d^⌊N/3⌋ or d^(⌊N/3⌋+1).
- 6 Discussions: The third-order reduction suggests a sample-size requirement that is preferable to nearly square matricization when N is odd.The matricization requirement is d^⌈N/2⌉polylog(d).