PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Low-rank Tensor Recovery: Models and Algorithms

Donald Goldfarb, Zhiwei Qin

arXiv:1311.6182v1stat.ML

TL;DR

The paper studies recovery of low-rank tensors from gross corruptions and missing values, addressing limitations of existing tensor-decomposition approaches. It develops convex constrained and Lagrangian models with ADAL and APG algorithms, plus a nonconvex alternative, and evaluates them on synthetic and real data. The reported results support the practical effectiveness of the framework, while convergence for the nonconvex algorithm is only weakly established and some models require parameter tuning or prior rank information.

  • Problem

    Robust tensor recovery must handle outliers, gross corruptions, and missing values while existing nonconvex approaches lack global optimality guarantees.

  • Method

    The paper proposes convex constrained and Lagrangian robust tensor-recovery models solved by ADAL and APG, together with an approximately solved nonconvex model.

  • Results

    The models and algorithms show empirical recovery and computational effectiveness on synthetic data and applications including 3D MRI, fluorescence EEM analysis, face representation, and web-game background reconstruction.

  • Takeaways & Limitations

    The convex optimization framework provides a practical approach to robust low-rank tensor recovery across multiple application settings.

  • Takeaways & Limitations

    The nonconvex algorithm has only a weak convergence guarantee, and the more general Singleton model requires more parameters and generally lacks known rank information beforehand.

Abstract

from arXiv · show

Robust tensor recovery plays an instrumental role in robustifying tensor decompositions for multilinear data analysis against outliers, gross corruptions and missing values and has a diverse array of applications. In this paper, we study the problem of robust low-rank tensor recovery in a convex optimization framework, drawing upon recent advances in robust Principal Component Analysis and tensor completion. We propose tailored optimization algorithms with global convergence guarantees for solving both the constrained and the Lagrangian formulations of the problem. These algorithms are based on the highly efficient alternating direction augmented Lagrangian and accelerated proximal gradient methods. We also propose a nonconvex model that can often improve the recovery results from the convex models. We investigate the empirical recoverability properties of the convex and nonconvex formulations and compare the computational performance of the algorithms on simulated data. We demonstrate through a number of real applications the practical effectiveness of this convex optimization framework for robust low-rank tensor recovery.

1. Introduction.

Tensor decomposition is valuable for multidimensional data but must address outliers, missing observations, and computational efficiency. The paper motivates robust low-rank tensor recovery through convex models, convergent algorithms, and a nonconvex alternative.

  • Challenges: Outliers, missing data, and computational efficiency are three major challenges for tensor decomposition.Least-squares-based CP and Tucker decompositions are vulnerable to outliers and gross corruptions, while existing nonconvex methods lack global optimality guarantees.
  • Problem formulation: Robust low-rank tensor recovery reconstructs the low-rank component underlying data affected by gross corruptions and missing values.The paper connects this goal to latent-factor structure and applications such as shadow or occlusion removal.
  • Contributions: The paper formulates robust tensor recovery as a convex optimization problem and develops ADAL and APG algorithms for constrained and Lagrangian formulations.The proposed algorithms are described as having global convergence guarantees.
  • Contributions: A nonconvex formulation is introduced that can potentially use more precise Tucker-rank information, alongside empirical recovery and computational evaluations.Experiments cover synthetic data and applications in 3D MRI, fluorescence EEM analysis, face representation, and web-game background reconstruction.
  • Related models: The tensor PCP model regularizes Tucker rank to exploit low-rank structure across all tensor dimensions rather than relying on one unfolding.The paper relates this construction to robust PCA, which decomposes observations into low-rank and sparse components using convex surrogates.

2. Higher-order RPCA (Robust Tensor Recovery).

Higher-order RPCA models a corrupted tensor as a low-rank component plus sparse errors, using convex tensor-rank surrogates. The paper develops ADAL and APG algorithms with convergence guarantees for Singleton and Mixture formulations.

  • Model: HoRPCA replaces tensor rank and error cardinality with convex surrogates to make robust tensor recovery tractable.The model decomposes the observation into a low-rank tensor and a sparse corruption tensor.
  • Singleton Model: The Singleton model regularizes the sum of nuclear norms of all mode-i unfoldings.Variable splitting introduces auxiliary variables so the unfolding-specific terms can be handled separately.
  • Singleton Model: ADAL alternates between unfolding variables and corruption variables, using singular value thresholding and shrinkage operators.The method has closed-form block updates and is applied to the Singleton formulation.
  • Convergence: The Singleton ADAL sequence converges to an optimal solution of the convex HoRPCA model.This follows from the generic ADAL convergence theorem for the corresponding convex problem.
  • Mixture Model: The Mixture model permits low-rank structure in selected modes and can outperform Singleton for tensors low-rank only in certain modes.Its variables are coupled, making efficient two-block ADAL updates difficult; the paper therefore proposes an inexact ADAL method with a global convergence guarantee.
  • Model Scope: The more general weighted Singleton model requires more parameters and usually lacks prior rank information, while HoRPCA outputs can support Tucker and CP decompositions.The Tucker factors come from unfolding SVDs, and CP decomposition can be applied to the recovered core tensor.

3. Constrained Nonconvex Model.

The constrained model imposes explicit Tucker-rank bounds while separating sparse corruptions from the observed tensor. ADAL solves the resulting nonconvex subproblems through variable splitting and truncated-SVD projections, but only weak convergence is established.

  • Model: The constrained model minimizes sparse corruption subject to data consistency and rank(X(i)) ≤ r_i for every mode.It explicitly constrains the Tucker rank of the recovered tensor.
  • Algorithm: Variable splitting introduces auxiliary variables X_i, yielding ADAL subproblems with closed-form global optimal solutions.The split formulation separates the rank-constrained matrix variables from the corruption variable.
  • Algorithm: Each X_i update projects an unfolded auxiliary matrix onto matrices of rank at most r_i.The global minimizer is obtained through the Eckart-Young truncated-SVD construction.
  • Extensions: The algorithm extends to partial observations through variable splitting and yields a robust Tucker-decomposition procedure for sparse gross corruptions.The method can also provide an alternative to ALS for Tucker decomposition.
  • Convergence: When the iterates converge, they converge to a KKT point, but convergence of the iterates themselves is not proved.Experiments provide strong indication of convergence, while the available result remains weak because it is conditional.
  • Limitations: The constrained formulation requires prior information about the ranks of the tensor unfoldings.HoRPCA-S or HoRPCA-M can first reveal approximate ranks before constrained post-processing.

4. Experiments.

Experiments show that recovery depends strongly on model choice, observation and corruption levels, Tucker-rank specification, and whether tensors are low-rank across all modes. The constrained nonconvex model can improve recovery with accurate ranks, while ADAL-based methods generally offer better speed and recovery than FISTA-based methods.

  • Convex Models: HoRPCA-S achieved significantly higher recovery accuracy than the other tested algorithms, with phase-transition thresholds near 35% observations for 10% corruption and 70% for 25% corruption.The phase transition was not observed similarly for HoRPCA-SP.
  • Convex Models: With full observations, HoRPCA-S could almost exactly recover tensors below 25% corruption, whereas HoRPCA-SP’s threshold was 15%.The Mixture model was considerably more susceptible to increasing corruption fractions.
  • Nonconvex Model: For HoRPCA-S, higher Tucker rank sums reduced corruption tolerance, while additional observations improved recovery only across a narrow transition interval.For example, the rank-(2,5,5) tensor transitioned between zero tolerance and maximum tolerance from 50% to 65% observations.
  • Comparative Results: HoRPCA-S was the only method reported to achieve exact recovery with partial observations, while the Mixture model was a reasonable alternative when rank information was unavailable and data were fully observed.The Singleton model performed best among convex models when tensors were low-rank in all modes; the Mixture model performed best when they were low-rank in only some modes.
  • Computational Performance: ADAL-based algorithms were several times faster than FISTA-based algorithms and usually achieved lower recovery error, while Lagrangian formulations were generally inferior to constrained versions.The performance gap was especially visible with partial observations, where consistency errors produced artifacts.
  • Nonconvex Model: HoRPCA-C achieved near-exact recovery with 20% observations and up to 40% corruption when the Tucker rank was correctly specified.Over-estimating the rank increased iterations, while under-estimating it damaged recovery performance.
  • Real Applications: On real data, Mixture models recovered MRI details better under gross corruption, whereas the nonconvex model retained more detail but also included more noise.With scattering and outliers, HoRPCA reduced adverse effects only tangibly because four outliers substantially changed the global properties of the small dataset.
  • Real Applications: In image reconstruction, the constrained nonconvex model gave the best noise removal and shadow reduction, while HoRPCA-S was much faster and outperformed RPCA in estimating missing pixels in game data.HoRPCA-S also recovered the table pixels almost perfectly in the 20%-observation comparison.

min

The appendix establishes convergence properties for the iterates generated by Algorithm 2.3 and connects their limit points to the KKT conditions of the optimization problem.

  • Optimality: The appendix identifies (X̄∗, E∗) as an optimal solution to problem (2.7).The associated notation also includes an optimal Lagrange multiplier and the transformed variable U∗.
  • Convergence properties: Under the stated proximal-gradient step-size condition, the sequence of iterates has a convergent subsequence.The condition is 0 < η < 1/N.
  • Convergence properties: Lemma A.1 states that successive iterates approach one another, remain in a compact region, and have a monotonically non-increasing distance to U∗.These properties imply convergence of the relevant distance sequence.
  • Optimality: Any limit point of the generated sequence satisfies the KKT conditions for problem (A.1).The proof uses the optimality conditions of the two subproblems in (A.2).

Appendix B. Lagrangian Version of HoRPCA via FISTA: global convergence rate.

This appendix establishes global convergence for the FISTA treatment of the Lagrangian HoRPCA formulation. Lipschitz smoothness and decomposable regularization enable efficient proximal updates, while continuation can substantially accelerate convergence.

  • Problems (2.11) and (2.12) share a generic optimization form used for the FISTA analysis.
  • The loss gradient has Lipschitz constant N + 1 for both models, so FISTA requires no line search.The regularizer combines trace norms and the L1 norm, whose proximal operators are available in closed form.
  • FISTA achieves the optimal global convergence rate among first-order methods, measured by iteration complexity for target distance ǫ.
  • Continuation starts with a large λ∗ and decreases it toward the desired minimum, with λ1 expressed as rλ∗.
  • More than an order-of-magnitude speedup was observed over applying FISTA directly with a small λ∗.
  • The continuation scheme preserves the global convergence proof because λ∗ converges to a positive target value.

Appendix C. Proof of Lemma 3.1.

The appendix proves the conditions needed for a factorized limit point to satisfy the optimality conditions of the HoRPCA model. The argument treats zero and nonzero cases for key variables and uses algorithmic residual convergence.

  • Condition (3.7) is transformed into a more useful equivalent form as the first step of the proof.
  • The proof uses the monotonicity of Qµ and applies its inverse while enforcing foldi(UiVi) + E = B.
  • The algorithmic sequence converges to a limit point W∗, which satisfies condition (3.6) because the reconstruction residual tends to zero.
  • The proof then focuses on verifying condition (3.5) from the update relation in Line 5.
  • If E∗ = 0, the factorization conditions force the factor ranks to equal the Tucker rank of B, contradicting the assumptions.
  • When Λ∗i is nonzero, a factorization exists that satisfies condition (3.5).

D.1. Amino Acid Fluorescence Data.

The figure presents the original 10th and 20th frames of the Game data set.

  • The figure contains original frames from the Game data set.
  • The displayed frames are numbered 10 and 20.
  • The figure is organized as a comparison between two original time-indexed frames.

D.2. The (partial) YaleB Database.

The partial YaleB database is used as a tensor of grayscale face images spanning five people and varied illumination conditions, with each person represented by one pose and 40 illuminations.

  • The YaleB database contains face images captured across different poses and illumination angles.
  • The selected subset includes five people, each with 40 illuminations and one pose.
  • Each cropped image is a 64×56 grayscale image that is vectorized.
  • The resulting tensor has dimensions 3584×40×5, corresponding to vectorized images, illuminations, and people.
  • The dataset supports construction of ‘Tensor Faces’ from factors extracted using Tucker decomposition.

D.3. The Dorrit Data.

The Dorrit data comprise fluorescence measurements of synthetic four-analyte mixtures, while the game data comprise screen-captured RGB frames of a roach-protection game.

  • D.3. The Dorrit Data.: The Dorrit fluorescence dataset contains 27 landscapes from synthetic samples mixing hydroquinone, tryptophan, phenylalanine, and dopa at different concentrations.Measurements were acquired with a Perkin-Elmer LS50 B fluorescence spectrometer.
  • D.3. The Dorrit Data.: Each Dorrit sample records emission wavelengths from 251nm to 481nm at 2nm intervals and 18 excitation wavelengths.
  • D.4. The Game Data.: The game dataset contains 27 colored frames captured at one frame per second, forming an 86×130×3×27 tensor.The game objective is to protect food from emerging roaches by clicking them with a mouse-controlled sandal.

D.4. The Game Data.

The algorithm experiments use heuristic parameter tuning, continuation for Lagrangian models, and residual-based stopping criteria tailored to ADAL- and FISTA-based methods.

  • Parameter Set-up for Algorithms: HoRPCA-S, HoRPCA-M, and RPCA tune λ1, whereas HoRPCA-SP and HoRPCA-MP tune both λ1 and λ∗.The setup uses Imax and a heuristic based on r for selecting λ1.
  • Parameter Set-up for Algorithms: When corruptions exceeded a threshold, such as 20% for synthetic data, very small λ∗ and λ1 values often reduced recovery accuracy, requiring higher minimum λ∗ tuning.For Lagrangian models, λ∗ is theoretically decreased toward an approximately zero continuation value.
  • Parameter Set-up for Algorithms: The FISTA continuation scheme used a decreasing λ∗ factor η = 0.97 and a stopping tolerance δ =1e-5.
  • Stopping Criteria: ADAL-based algorithms stopped when maximum relative primal or dual residuals fell below 1e-3; FISTA-based algorithms required two relative criteria below 1e-4.The FISTA criteria were relative primal residual and relative difference between consecutive iterates.
Loading 1311.6182v1…