Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

Cun Mu; Bo Huang; John Wright; Donald Goldfarb

Source-linked AI summary

Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

Cun Mu, Bo Huang, John Wright, Donald Goldfarb

arXiv:1307.5870v2Jul 22, 2013stat.MLcs.LG

TL;DR

The paper asks how to recover low-rank tensors from incomplete linear measurements when tensor rank and nuclear-norm formulations pose computational and sample-complexity challenges. It compares an intractable nonconvex baseline with the sum-of-nuclear-norms relaxation and introduces a square norm based on balanced reshaping. The square norm improves the convex sample complexity over SNN, while remaining suboptimal relative to the nonconvex model and theoretically limited to Gaussian measurements.

Problem
Low-rank tensor recovery from incomplete linear measurements is ill-posed, and the standard sum-of-nuclear-norms relaxation may require far more observations than the tensor’s intrinsic degrees of freedom.
Method
The paper compares a rank-based nonconvex baseline with convex relaxations and introduces a square norm by reshaping tensor unfoldings into more balanced low-rank matrices.
Results
The nonconvex model needs O(r^K + nrK) observations, SNN requires Ω(rn^(K-1)), and the square norm succeeds with O(r^floor(K/2)n^ceil(K/2)) Gaussian measurements.
Takeaways & Limitations
The square norm partially narrows the gap between tractable convex recovery and the nonconvex baseline, and simulations suggest it outperforms SNN for random-entry tensor completion.
Takeaways & Limitations
The theoretical guarantees concern Gaussian measurements, and the square norm remains suboptimal relative to the nonconvex model, leaving near-optimal convex relaxations open for K > 2.

Abstract

from arXiv · show

Recovering a low-rank tensor from incomplete information is a recurring problem in signal processing and machine learning. The most popular convex relaxation of this problem minimizes the sum of the nuclear norms of the unfoldings of the tensor. We show that this approach can be substantially suboptimal: reliably recovering a $K$-way tensor of length $n$ and Tucker rank $r$ from Gaussian measurements requires $Ω(r n^{K-1})$ observations. In contrast, a certain (intractable) nonconvex formulation needs only $O(r^K + nrK)$ observations. We introduce a very simple, new convex relaxation, which partially bridges this gap. Our new formulation succeeds with $O(r^{\lfloor K/2 \rfloor}n^{\lceil K/2 \rceil})$ observations. While these results pertain to Gaussian measurements, simulations strongly suggest that the new norm also outperforms the sum of nuclear norms for tensor completion from a random subset of entries. Our lower bound for the sum-of-nuclear-norms model follows from a new result on recovering signals with multiple sparse structures (e.g. sparse, low rank), which perhaps surprisingly demonstrates the significant suboptimality of the commonly used recovery approach via minimizing the sum of individual sparsity inducing norms (e.g. $l_1$, nuclear norm). Our new formulation for low-rank tensor recovery however opens the possibility in reducing the sample complexity by exploiting several structures jointly.

1 Introduction

Low-rank tensor recovery is an ill-posed inverse problem because tensors are high-dimensional, while tensor rank and nuclear-norm formulations introduce computational and statistical challenges. The paper compares tractable and intractable approaches and proposes a square norm with improved Gaussian-measurement guarantees.

Low-rank tensors provide lower-dimensional structure for estimating high-dimensional multi-indexed objects such as videos and hyperspectral datacubes.
Recovering a tensor from substantially fewer measurements than ambient dimension is generally ill-posed, motivating structural assumptions and convex recovery methods.
Tensor rank is computationally difficult: CP rank is NP-hard to compute, and the tensor nuclear norm is intractable.
The Tucker rank records the matrix ranks of the tensor’s mode-i unfoldings and can be computed efficiently using singular value decomposition.
The widely used sum-of-nuclear-norms approach replaces unfolding ranks with nuclear norms in a tractable convex recovery program.
(2r)^K + 2nrK + 1 Gaussian measurements suffice for the nonconvex model, whereas the square norm requires O(r^floor(K/2)n^ceil(K/2)) measurements.
The lower-bound analysis builds on general results showing that combining norms for multiple structures can remain substantially suboptimal.

2 Bounds for Non-Convex Recovery

The paper uses an intractable nonconvex rank-based model as a baseline and characterizes recovery through injectivity on a set of low-rank tensors. A covering-number argument yields a near-minimal measurement bound.

The nonconvex formulation targets tensors consistent with the measurements while minimizing or jointly comparing the ranks of their unfoldings.
Because the model is not tractable, it serves as a baseline for evaluating how many generic measurements convex approaches require.
Recovery of every tensor with Tucker rank at most r follows when the measurement operator is injective on the relevant low-rank set, implied by null(G) ∩ T_2r = {0}.
(2r)^K + 2nrK + 1 Gaussian measurements suffice, with probability one, to recover every X_0 ∈ T_r.
The proof controls the covering number of the low-rank set by constructing nets for the Tucker core and factor matrices.

3 Convexification: Sum of Nuclear Norms?

The sum-of-nuclear-norms relaxation is a natural convex surrogate for unfolding ranks and has established recovery guarantees. However, the paper proves that its Gaussian-measurement requirement is essentially unavoidable and much larger than the tensor’s degrees of freedom.

The sum-of-nuclear-norms model replaces the unfolding ranks in the nonconvex formulation with nuclear norms and solves a convex optimization problem.
Crn^(K-1) Gaussian measurements suffice with high probability for recovering a tensor of Tucker rank (r,...,r) using equal nuclear-norm weights.
O(rn^(K-1)) measurements are also necessary for reliable recovery under the sum-of-nuclear-norms model.
The lower bound makes the existing upper guarantee essentially tight, despite generic tensors having at most r^K + nrK real degrees of freedom.
The bound extends the paper’s multi-structured recovery perspective, where combining individual structure-inducing norms can be far less effective than exploiting structures jointly.

Recovering objects with multiple structures

For objects carrying multiple low-dimensional structures, combining structure-inducing norms can perform little better than the best individual norm. A geometric analysis relates this limitation to the size of descent cones and yields recovery lower bounds.

Composite regularization: The composite recovery program minimizes a positive weighted sum of the individual structure-inducing norms subject to matching Gaussian measurements.The associated recovery question is whether x0 is the unique optimal solution.
Geometric analysis: Recovery succeeds exactly when the measurement null space intersects the descent cone only at zero; larger descent cones make recovery less likely.For Gaussian operators, the null space is a uniformly oriented random subspace, and statistical dimension quantifies the relevant cone size.
Geometric analysis: The combined regularizer’s subdifferential lies in a circular cone whose angle is the largest individual angle, while smaller angles correspond to larger descent cones.This provides the geometric explanation for why the combination can inherit the weakness of an individual structure.
Recovery threshold: For Gaussian measurements, a sharp recoverability transition occurs around the statistical dimension of the descent cone.The resulting lower bound requires the number of measurements to be proportional to κ, which is determined by the best individual structure.
Multiple structures: Combining structure-inducing norms for simultaneously structured objects is often not significantly more powerful than the best individual norm.The paper identifies this phenomenon for structures such as sparsity and low rank.

4 A Better Convexification: Square Norm

The square norm reshapes a tensor into a more balanced matrix while preserving low-rank structure, then applies matrix nuclear-norm recovery. This yields improved Gaussian-measurement guarantees over the sum-of-nuclear-norms model for many tensors.

Reshaping: The square reshaping produces a more balanced matrix while preserving low rank for tensors with either CP rank or Tucker rank.It generalizes standard matricization: selecting j = 1 recovers the usual mode-1 unfolding.
Square norm: The square norm is the nuclear norm of the balanced reshaping X^[floor(K/2)].Recovery uses this matrix nuclear norm as a convex relaxation.
Guarantees: For CP rank r, m ≥ Crn^ceil(K/2) measurements suffice for high-probability recovery.This guarantee applies to the square-norm program.
Guarantees: For Tucker rank (r, ..., r), m ≥ Cr^floor(K/2)n^ceil(K/2) measurements suffice with high probability.The bound follows from the low rank of the square reshaping and matrix nuclear-norm recovery results.
Comparison: Compared with Ω(rn^(K−1)) measurements for sum-of-nuclear-norms recovery, square reshaping improves sample complexity for small r and K ≥ 4.For constant r, the stated improvement factor is n^floor(K/2)−1.
Limitations: The square-norm guarantee has no improvement for K = 3 and remains suboptimal relative to the nonconvex model.For unbalanced tensors, square reshaping may provide no advantage over the sum-of-nuclear-norms model.

5 Simulation Results for Tensor Completion

The tensor-completion experiment compares the square-norm formulation with sum-of-nuclear-norms minimization on randomly generated 4-way tensors. Across tested tensor sizes and observation ratios, the square norm produces a larger region of correct recovery in simulations.

Visualization: Figure 2 encodes the fraction of correct recovery by brightness, from black for certain failure to white for certain success.
Experimental setup: The experiment generates 4-way tensors with a Tucker-style core and orthonormal factor matrices, then samples entries uniformly at random.Tensor size n ranges from 10 to 30, and the observation ratio ranges from 0.01 to 0.2; five instances are simulated for each pair.
Evaluation: A trial is successful when the relative Frobenius reconstruction error is at most 10^-2.
Observed result: The square-norm formulation produces a much larger white region than sum-of-nuclear-norms minimization.The simulations therefore suggest that the square norm outperforms the conventional model for tensor completion.

6 Conclusion

The paper establishes Gaussian-measurement guarantees for nonconvex and convex approaches to low-rank tensor recovery. The square-norm relaxation improves substantially over sum-of-nuclear-norms, but remains suboptimal relative to the nonconvex baseline and leaves near-optimal convex recovery open.

Theoretical guarantees: (2r)^K + 2nrK + 1 measurements suffice almost surely for recovery by the nonconvex model.Although computationally intractable, this model serves as a baseline for tractable convex approaches.
Theoretical guarantees: Ω(rn^(K−1)) Gaussian measurements are necessary for reliable recovery under the sum-of-nuclear-norms model.The lower bound comes from a result on recovery of objects with multiple structures.
Theoretical guarantees: O(r^⌊K/2⌋n^⌈K/2⌉) Gaussian measurements suffice for high-probability recovery under the square-norm model.
Conclusion: For K ≥ 4 and small r, the square-norm sample complexity is much better than the sum-of-nuclear-norms bound but remains suboptimal relative to the nonconvex model.
Open problems: Near-optimal convex relaxations for all K > 2 remain an open problem, and general methods for exploiting multiple structures jointly are unclear.

A Proofs for Section 2

The proofs for the nonconvex recovery results construct approximation nets for Tucker-decomposition components and use Gaussian measurement arguments to establish injectivity on a bounded-rank set.

Gaussian argument: For each fixed tensor in the set, Gaussian measurements are standard Gaussian random variables, enabling small-ball probability bounds.
Gaussian argument: The net argument concludes that sufficiently many measurements prevent the measurement map from vanishing on the bounded-rank set.
Net construction: The proof constructs a net for each Tucker-decomposition component and combines them into a compound net.
Net construction: The component classes include unit-Frobenius-norm cores and orthonormal factor matrices.
Net construction: The resulting compound net is shown to cover the relevant Tucker-decomposition set in Frobenius norm.

B Proofs for Section 3

The proofs for the sum-of-nuclear-norms results analyze geometric probabilities through intrinsic volumes and statistical dimension, linking null-space intersection to unique convex recovery.

Geometric probability: The argument applies concentration bounds involving the statistical dimension of the cone and the measurement dimension.
Intrinsic-volume analysis: The proof bounds tail probabilities of an intrinsic-volume random variable using interlacing relations.
Intrinsic-volume analysis: Separate inequalities handle even and odd dimensions when bounding the statistical dimension of circular cones.
Geometric probability: Unique optimal recovery is characterized by the event that the relevant cone intersects the measurement null space only at zero.

C Proofs for Section 4

The proofs establish tensor unfolding identities by vectorizing both sides and applying standard vectorization and Kronecker-product identities.

Equation (4.2) is verified by showing that the vectorization of its right-hand side equals vec(X^(1)).The proof uses the identity vec(a ◦ b) = b ⊗ a.
Equation (4.3) is verified by vectorizing its right-hand side and matching the resulting expression to the corresponding unfolding.The proof invokes vec(ABC) = (C* ⊗ A)vec(B).

D Algorithms for Section 5

This section describes an accelerated linearized Bregman implementation for the SNN model, using variable splitting and smoothing to obtain separable subproblems.

The SNN optimization problem is reformulated by introducing an auxiliary variable W and copies X_1, ..., X_K linked by X_i = W.This splitting makes the objective function separable.
The accelerated linearized Bregman algorithm solves convex problems with nonsmooth objectives and linear constraints through smoothing and an accelerated dual formulation.The algorithm first smooths the objective and then applies Nesterov acceleration to the unconstrained, Lipschitz-differentiable dual problem.
The smoothed split problem uses Y_i as dual variables for X_i = W and Z as the dual variable for the sampling constraint.Because the objective is separable, the resulting ALB subproblems are easy to solve individually.
For K = 4, the numerical experiment sets µ = 50∥X_0∥_F and τ = 1/(5µ), with larger µ values offering no empirically better recovery.The observed behavior is reported as consistent with cited theoretical results.
The implementation iterates over tensor modes and applies shrinkage to singular values of each unfolding before folding the result back into a tensor.This operation appears in line 4 of Algorithm 1 for the SNN model.