PaperlayerView exact revision on arXiv

Source-linked AI summary

Exact Low Tubal Rank Tensor Recovery from Gaussian Measurements

Canyi Lu, Jiashi Feng, Zhouchen Lin, Shuicheng Yan

arXiv:1806.02511v1stat.MLcs.LG

TL;DR

Low-rank tensor recovery needs measurement guarantees, but extending matrix recovery results to tensors is complicated by rank definitions and proof challenges. This paper represents TNN as an atomic norm and analyzes its Gaussian-width recovery bounds. It gives an order-optimal Gaussian measurement rate and a uniform-sampling completion guarantee.

  • Problem

    The paper seeks measurement bounds for recovering an underlying object from underdetermined linear measurements using a norm that promotes structural simplicity.

    Source: §1 · p. 1

  • Method

    The authors identify TNN as an atomic norm for a carefully chosen atomic set and use Gaussian-width analysis to derive recovery guarantees.

    Source: §3 · p. 5, §4 · p. 6

  • Results

    TNN minimization exactly recovers tubal-rank-r tensors with O(r(n1 + n2 − r)n3) Gaussian measurements, an order-optimal rate, and the paper also gives a uniform-sampling tensor completion guarantee.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The Gaussian recovery rate matches the degrees of freedom, while the completion sampling rate is order optimal up to a log factor.

    Source: §1 · p. 2

    The authors report that Zhang and Aeron [2017] use a different TNN definition and that their tensor-completion proofs contain errors.

    Source: §6.1 · p. 7

Abstract

from arXiv · show

The recent proposed Tensor Nuclear Norm (TNN) [Lu et al., 2016; 2018a] is an interesting convex penalty induced by the tensor SVD [Kilmer and Martin, 2011]. It plays a similar role as the matrix nuclear norm which is the convex surrogate of the matrix rank. Considering that the TNN based Tensor Robust PCA [Lu et al., 2018a] is an elegant extension of Robust PCA with a similar tight recovery bound, it is natural to solve other low rank tensor recovery problems extended from the matrix cases. However, the extensions and proofs are generally tedious. The general atomic norm provides a unified view of low-complexity structures induced norms, e.g., the $\ell_1$-norm and nuclear norm. The sharp estimates of the required number of generic measurements for exact recovery based on the atomic norm are known in the literature. In this work, with a careful choice of the atomic set, we prove that TNN is a special atomic norm. Then by computing the Gaussian width of certain cone which is necessary for the sharp estimate, we achieve a simple bound for guaranteed low tubal rank tensor recovery from Gaussian measurements. Specifically, we show that by solving a TNN minimization problem, the underlying tensor of size $n_1\times n_2\times n_3$ with tubal rank $r$ can be exactly recovered when the given number of Gaussian measurements is $O(r(n_1+n_2-r)n_3)$. It is order optimal when comparing with the degrees of freedom $r(n_1+n_2-r)n_3$. Beyond the Gaussian mapping, we also give the recovery guarantee of tensor completion based on the uniform random mapping by TNN minimization. Numerical experiments verify our theoretical results.

1 Introduction

Exact recovery from underdetermined measurements depends on the structure-promoting norm and measurement map, while tensor recovery poses unresolved challenges around rank definitions and measurement efficiency. This work establishes TNN-based guarantees for Gaussian measurements and tensor completion.

1 Introduction

  • Atomic norms unify convex recovery penalties, including the ℓ1-norm and nuclear norm, and their Gaussian-width analysis gives sharp generic measurement estimates.The Gaussian width of the tangent cone associated with the atomic norm ball is a key step.Source: §1 · pp. 1–2
  • Tensors have several rank definitions; CP rank is generally NP-hard to compute, and existing convex models for low Tucker-rank recovery require more measurements than the degrees of freedom.The introduction contrasts this with order-optimal nuclear-norm recovery for low-rank matrices.Source: §1 · p. 2
  • TNN is shown to be an atomic norm, yielding a TNN-minimization recovery guarantee for tubal-rank-r tensors from Gaussian measurements using O(r(n1 + n2 − r)n3) measurements.The rate is order optimal relative to the degrees of freedom r(n1 + n2 − r)n3.Source: §1 · p. 2
  • For uniform random sampling, TNN minimization recovers tubal-rank-r tensors with O(r min(n1, n2)n3 log^2(min(n1, n2)n3)) samples, order optimal up to a log factor.The introduction notes that Zhang and Aeron [2017] studied this problem but their proofs contain errors.Source: §1 · p. 2

2 Notations and Preliminaries

The preliminaries establish the tensor operations and decompositions used to define tubal rank and TNN. They also connect these quantities to Fourier-domain matrix operations.

2 Notations and Preliminaries

  • The paper fixes notation for tensors, matrices, vectors, scalars, slices, tubes, and inner products before introducing its tensor operations.It denotes frontal slices as A(i) and tubes as A(i, j, :).Source: §2 · p. 2
  • For a tensor A, FFT and inverse FFT are applied along the third dimension; its block-circulant matrix can be block-diagonalized, with Fourier-transformed frontal slices forming the diagonal blocks.Source: §2 · pp. 2–3
  • The t-product and t-SVD provide the tensor multiplication and factorization framework used in the paper.The t-SVD factors a tensor using orthogonal tensors U and V and an f-diagonal tensor S; its illustration is Figure 1.Source: §2 · p. 3, Figure 1 · p. 3
  • The t-SVD defines tubal rank as the number of nonzero tensor singular values; a rank-r tensor has a skinny t-SVD with r columns in U and V.The paper uses the skinny t-SVD throughout.Source: §2 · p. 3
  • The TNN is the sum of tensor singular values and equals 1/n3 times the nuclear norm of the Fourier-transformed tensor.The paper states that its normalization factor 1/n3 is crucial to consistency between the model, theory, and optimization, and that TNN and the tensor spectral norm are dual norms.Source: §2 · p. 4

3 Tensor Nuclear Norm Is an Atomic Norm

The section formulates low-tubal-rank recovery as a convex program and identifies TNN as an atomic norm. This identification supplies the representation needed for the recovery analysis.

3 Tensor Nuclear Norm Is an Atomic Norm

  • Given observations y = Φ(M) of a tubal-rank-r tensor, the recovery goal is to recover M from the linear map's output.The proposed convex program minimizes TNN subject to matching the observations.Source: §3 · p. 4
  • Atomic-norm recovery theory provides sharp measurement estimates, and applying it to TNN requires an appropriate atomic set and a Gaussian-width calculation.The section identifies reformulating TNN as an atomic norm and computing Gaussian width as the key challenge.Source: §3 · p. 4
  • The authors construct an atomic set from tensors whose Fourier-domain representation has one nonzero rank-one, unit-Frobenius-norm slice.They define the tensor atoms from this set using the inverse Fourier transform along the third dimension.Source: §3 · p. 5
  • For the constructed set, the induced atomic norm is exactly TNN, and its convex hull is the unit TNN ball.The authors identify this equivalence as crucial to the low-rank tensor recovery guarantee.Source: §3 · p. 5

4 Low-rank Tensor Recovery from Gaussian Measurements

The section applies a Gaussian-width recovery bound to obtain exact low-tubal-rank recovery at a measurement count proportional to r(n1+n2-r)n3. Its guarantee is order-optimal against the stated degrees of freedom and includes the matrix case when n3=1.

4 Low-rank Tensor Recovery from Gaussian Measurements

  • The proof strategy estimates the atomic-norm tangent cone's Gaussian width to apply a sharp generic-measurement recovery bound.The tensor atomic set's width is the quantity estimated for the low-tubal-rank result.Source: §4 · p. 6
  • For Gaussian measurements, exact recovery holds when m ≥ 3r(n1+n2−r)n3 + 1.The recovered tensor is the unique optimum of program (3).Source: §4 · p. 6
  • The O(r(n1+n2−r)n3) rate also supports approximate recovery and matches the stated tubal-rank degrees of freedom.The degrees of freedom are at most r(n1+n2−r)n3.Source: §4 · p. 6
  • When n3=1, the model and guarantee reduce to low-rank matrix recovery with the nuclear norm; the tensor model is computable and order-optimal relative to cited tensor-rank guarantees.The cited comparisons are [Recht et al., 2010; Chandrasekaran et al., 2012] and [Mu et al., 2014].Source: §4 · p. 6

5 Exact Tensor Completion Guarantee

The completion guarantee considers independently observed entries under Bernoulli sampling, subject to tensor incoherence conditions. Under those conditions, the tensor is uniquely recovered with high probability at a sampling complexity stated to be tight against its degrees of freedom.

5 Exact Tensor Completion Guarantee

  • The completion setup independently observes each tensor entry with probability p and seeks to recover M from the observed entries.The observed index set is denoted Ω∼Ber(p).Source: §5 · p. 6
  • Under Bernoulli sampling and the tensor incoherence conditions, M is the unique solution with probability at least 1−c1(n1+n2)^−c2.The theorem's sampling threshold is omitted from the supplied passage.Source: §5 · p. 7
  • The stated sampling complexity is O(rn(1)n3 log^2(n(1)n3)) and is described as tight against the degrees of freedom.Here n(1)=max(n1,n2), as defined in the supplied notation passage.Source: §5 · pp. 6–7

6 Experiments

Experiments test TNN recovery from Gaussian measurements and uniform random tensor completion on random tensors. Both show broad regimes of successful recovery, with small errors and correct recovered tubal ranks in the reported exact-recovery tests.

6 Experiments

  • The experiments use ADMM for both Gaussian recovery program (3) and tensor completion program (8), with Gaussian measurements implemented as a vectorized linear map.The matrix A has i.i.d. zero-mean Gaussian entries with variance 1/m.Source: §6 · p. 7, §6.1 · p. 7

6.1 Exact Recovery from Gaussian Measurements

  • Gaussian recovery on random tensors produced very small relative errors and correct tubal ranks using m = 3r(2n −r)n3 + 1 measurements.The tests used n = 10, 20, 30, n3 = 5, and r = 0.2n or 0.3n.Source: §6.1 · p. 8
  • For Gaussian measurements, a large phase-transition region showed correct recovery, and higher tubal rank required more measurements.The experiment varied m and r with n1 = n2 = 30 and n3 = 5.Source: §6.1 · p. 8

6.2 Exact Tensor Completion

  • Completion on random tensors produced relative errors below 10^-5 and correct tubal ranks, verifying the stated recovery guarantee.The experiment compares observed-entry counts with the degrees-of-freedom reference.Source: §6.2 · p. 8
  • For tensor completion, successful recovery occupied a large region across tubal ranks and sampling rates, with similar phase-transition plots for n = 40 and n = 50.Each (r, p) setting was tested on 10 instances; the recovery criterion was relative error at most 10^-3.Source: §6.2 · p. 8

7 Conclusion

The paper frames TNN as an atomic norm and derives exact recovery guarantees for low tubal rank tensors under Gaussian measurements and tensor completion. Experiments verify the theoretical results, while the completion guarantee also addresses errors in earlier proofs.

7 Conclusion

  • TNN is represented as an atomic norm associated with a chosen atomic set, enabling an optimal estimate of measurements for exact low tubal rank recovery from Gaussian measurements.The paper also gives an exact recovery guarantee for tensor completion.Source: §7 · p. 8
  • The tensor-completion guarantee addresses errors in the proofs of Zhang and Aeron (2017).The conclusion reports numerical experiments as verification of the theoretical results.Source: §7 · p. 8
  • Figure 3 reports tensor-completion recovery fractions across tubal rank and sampling rate for n = 40 and n = 50, based on 10 trials.The paper identifies further low tubal rank recovery results from existing work and nonconvex models as directions of interest.Source: Figure 3 · p. 9, §7 · p. 9

A.1 Tensor Completion for Image Inpainting

The image-inpainting experiment treats color images as three-way tensors and compares TNN completion with matrix and tensor baselines. TNN performs better than the other tensor methods, while tensor methods usually outperform independent per-channel matrix completion.

A.1 Tensor Completion for Image Inpainting

  • Each color image is represented as a 3-way tensor with its three channels as lateral slices, a construction that performs best in most tested cases.The authors note an alternative construction with the channel dimension last.Source: §A.1 · p. 10
  • The comparison uses 100 Berkeley Segmentation Dataset images, with 30% or 50% of entries observed, and evaluates recovery using PSNR, where higher values indicate better recovery.The methods are LRMC, LRTC, TMac, and TNN.Source: §A.1 · p. 11
  • TNN achieves better recovery performance than LRTC and TMac, while tensor methods usually perform much better than per-channel LRMC.The authors attribute the tensor methods' advantage over LRMC to their use of information across channels.Source: §A.1 · p. 11

A.2 Tensor Completion for Video Recovery

TNN tensor completion achieves the best reported performance on most of the tested video sequences. The section represents grayscale videos as 3-way tensors and describes ADMM solvers for measurement recovery and tensor completion.

A.2 Tensor Completion for Video Recovery

  • The video test uses 15 grayscale sequences, their first 150 frames, and QCIF frames sized 144 × 176.Each video is constructed as a tensor M ∈ R^(h×f×w); entries are sampled at p = 0.5 for the comparison.Source: §A.2 · p. 11
  • TNN tensor completion achieves the best performance on the 15 tested video sequences.The comparison reports PSNR values in Table 3 and recovered frames in Figure 9.Source: §A.2 · p. 11, Table 3 · p. 14

B Optimization by ADMM

  • The ADMM solver for the measurement-recovery problem alternates X and Z updates, both of which have closed-form solutions.The X update computes the proximal operator of TNN.Source: B Optimization by ADMM · p. 12

5. Check the convergence conditions

  • For tensor completion, the model sets unknown entries of X to zero and updates X and E alternately by ADMM.The formulation uses πΩ to retain observed entries and zero entries outside Ω.Source: §5 · pp. 14–15

C Proof of Theorem 5

The proof uses Fourier-domain degrees of freedom to relate tubal rank to tensor complexity, then develops Gaussian bounds used in the recovery analysis. Its lemmas control projected random tensors through expectation estimates and Gaussian concentration.

C Proof of Theorem 5

  • A tubal-rank-r tensor has at most r(n1 + n2 − r)n3 degrees of freedom.The proof uses the invertibility of the discrete Fourier transform and the rank bound on each transformed frontal slice.Source: C Proof of Theorem 5 · p. 15

D Proof of Theorem 3

  • Theorem 3’s proof is organized around preliminary lemmas followed by a complete proof.The stated proof strategy first introduces lemmas in subsection D.1.Source: D Proof of Theorem 3 · p. 15

D.1 Some Lemmas

  • The Gaussian lemmas bound projected random-tensor terms using expectation estimates and Gaussian concentration.The proof establishes a Lipschitz bound for the projected operator before invoking Gaussian concentration.Source: §D.1 · pp. 15–16

D.2 Proof of Theorem 3

Theorem 3’s proof bounds the Gaussian width associated with the tensor nuclear norm geometry, yielding a bound proportional to r(n1 + n2 − r)n3. The completion lemmas separately establish high-probability sampling bounds under stated sampling-rate conditions.

D.2 Proof of Theorem 3

  • The Gaussian-width bound in the proof is at most 3n3r(n1 + n2 − r).The calculation starts from the normal cone at a rank-r tensor and uses projections onto its tangent space and orthogonal complement.Source: §D.2 · pp. 17–18

E Proof of Theorem 6

  • Theorem 6’s proof uses sampling concentration lemmas to control the tangent-space sampling operator with high probability.One stated condition is p ≥ c0ϵ^-2µr log(nn3)/(nn3), under which the operator deviation is bounded by ϵ.Source: §E.1 · pp. 19–20

E.1 Some Lemmas

  • The completion lemmas also bound sampling deviations for fixed tensors, including tensors in the tangent space, under stated lower bounds on p.The conditions include p ≥ c0µr log(nn3)/(nn3) and an ϵ-dependent version for a deviation bound.Source: §E.1 · pp. 20, 22, 23

E.2 Proof of Theorem 6

The proof establishes uniqueness for tensor completion by constructing a dual certificate with the required support and norm properties. It builds the certificate using the Golfing Scheme and concludes that M is the unique optimum.

E.2 Proof of Theorem 6

  • The uniqueness argument compares feasible tensors using a subgradient of the tensor nuclear norm and the dual certificate.The certificate’s support makes its inner product with the difference of feasible tensors vanish.Source: §E.2 · p. 23
  • The proof concludes that M is the unique optimum of the tensor completion program.The uniqueness argument invokes conditions on the sampling operator and a dual certificate.Source: §E.2 · p. 23
  • A dual certificate supported on the observed entries is constructed with the Golfing Scheme.The proof iteratively forms the certificate from independently sampled subsets and checks the required conditions.Source: §E.2 · p. 24

Related papers

Loading 1806.02511v1…