Exact Recovery of Tensor Robust Principal Component Analysis under Linear Transforms

Canyi Lu; Pan Zhou

arxiv: 1907.08288 · v1 · pith:ZS33UNMMnew · submitted 2019-07-16 · 💻 cs.LG · cs.CV· stat.ML

Exact Recovery of Tensor Robust Principal Component Analysis under Linear Transforms

Canyi Lu , Pan Zhou This is my paper

Pith reviewed 2026-05-24 20:51 UTC · model grok-4.3

classification 💻 cs.LG cs.CVstat.ML

keywords Tensor RPCAExact recoveryConvex optimizationLinear transformsTensor nuclear normIncoherence conditionsTensor SVD

0 comments

The pith

A convex program using a transform-dependent tensor nuclear norm exactly recovers the low-rank and sparse components of a tensor under incoherence conditions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper studies the tensor robust principal component analysis problem of separating a tensor into low-rank and sparse parts from their sum. It defines a new tensor nuclear norm that depends on a chosen linear transform and solves the separation via convex optimization that combines this norm with the l1-norm. The central result is that the program exactly recovers the components whenever they satisfy incoherence conditions relative to the transform. The model reduces to ordinary matrix robust PCA when the tensor is two-dimensional and extends an earlier Fourier-transform version of tensor RPCA. Experiments on synthetic tensors and image recovery tasks confirm the recovery guarantees.

Core claim

Under certain incoherence conditions, the convex program whose objective is a weighted combination of the new transform-dependent tensor nuclear norm and the l1-norm exactly recovers the underlying low-rank and sparse components.

What carries the argument

The transform-dependent tensor nuclear norm, obtained by applying the linear transform to the tensor, unfolding along one mode, and taking the sum of singular values of the resulting matrix.

If this is right

When the input tensor reduces to a matrix, the model and its recovery guarantee reduce exactly to the known matrix robust PCA result.
The framework includes the earlier discrete-Fourier-transform version of tensor RPCA as a special case, though the proof technique differs.
Numerical experiments on both synthetic data and real image recovery tasks verify the exact-recovery claim and show practical advantages over prior methods.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Different choices of linear transform can be matched to the structure of particular data sets to potentially improve recovery rates or speed.
The same norm construction could be substituted into other tensor problems such as completion or decomposition to obtain analogous convex programs.
If the linear transform admits a fast implementation, the overall method may become computationally cheaper than fixed-transform alternatives while retaining the exact-recovery property.

Load-bearing premise

The low-rank and sparse components must satisfy incoherence conditions with respect to the chosen linear transform.

What would settle it

A concrete tensor example in which the components satisfy the stated incoherence conditions yet the convex program fails to recover them exactly, or in which the conditions are violated yet exact recovery still occurs.

Figures

Figures reproduced from arXiv: 1907.08288 by Canyi Lu, Pan Zhou.

**Figure 1.** Figure 1: An illustration of the t-product under linear transform L. L has special properties. For example, the cost for computing L(A) is O(n1n2n3 log n3) for fast Fourier transform [25]. The t-product enjoys many similar properties as the matrixmatrix product. For example, the t-product is associative, i.e., A ∗L (B ∗L C) = (A ∗L B) ∗L C. Definition 2. (Tensor transpose) [28] Let L be any invertible linear transf… view at source ↗

**Figure 2.** Figure 2: An illustration of the t-SVD under linear transform L of a n1 × n2 × n3 sized tensor. Algorithm 2 T-SVD under linear transform L Input: A ∈ R n1×n2×n3 and invertible linear transform L. Output: T-SVD components U, S and V of A. 1. Compute A¯ = L(A). 2. Compute each frontal slice of U¯, S¯ and V¯ from A¯ by for i = 1, · · · , n3 do [U¯(i) ,S¯(i) ,V¯ (i) ] = SVD(A¯(i) ); end for 3. Compute U = L −1 (U¯), S =… view at source ↗

**Figure 3.** Figure 3: Correct recovery for varying rank and sparsity. In this test, sgn(S0) is random. Fraction of correct recoveries across 10 trials, as a function of rankt(L0) (x-axis) and sparsity of S0 (y-axis). Left: DCT is used as the linear transform L. Right: ROM is used as the linear transform L. rankt/n ρ s 0.1 0.2 0.3 0.4 0.5 0.5 0.4 0.3 0.2 0.1 (a) Coherent Signs, DCT rankt/n ρ s 0.1 0.2 0.3 0.4 0.5 0.5 0.4 0.3 0.2… view at source ↗

**Figure 4.** Figure 4: Correct recovery for varying rank and sparsity. In this test, S0 = PΩsgn(L0). Fraction of correct recoveries across 10 trials, as a function of rankt(L0) (x-axis) and sparsity of S0 (y-axis). Left: DCT is used as the linear transform L. Right: ROM is used as the linear transform L. is correct when the tubal rank of L0 is relatively low and the errors S0 is relatively sparse. More importantly, the results s… view at source ↗

**Figure 5.** Figure 5: Comparison of the PSNR values (up) and running time (bottom) of RPCA, SNN, TRPCA, our TRPCA-DCT and TRPCA-ROM for image denoising on 50 images. Best viewed in ×2 sized color pdf file. problem (27) is equivalent to arg min X τkX k∗ + 1 2 kX − Yk 2 F = arg min X 1 ` (τkX¯k∗ + 1 2 kX¯ − Y¯ k 2 F ) = arg min X 1 ` Xn3 i=1 (τkX¯(i) k∗ + 1 2 kX¯(i) − Y¯ (i) k 2 F ). (28) By Theorem 2.1 in [33], we know that the … view at source ↗

**Figure 6.** Figure 6: Performance comparison for image recovery on some sample images. (a) Original image; (b) observed image; (c)-(f) recovered images by RPCA, SNN, TRPCA, and our TRPCA-DCT, respectively. Best viewed in ×2 sized color pdf file. order tensors,” Linear Algebra and its Applications, vol. 435, no. 3, pp. 641–658, 2011. [22] Zemin Zhang, Gregory Ely, Shuchin Aeron, Ning Hao, and Misha Kilmer, “Novel methods for mul… view at source ↗

read the original abstract

This work studies the Tensor Robust Principal Component Analysis (TRPCA) problem, which aims to exactly recover the low-rank and sparse components from their sum. Our model is motivated by the recently proposed linear transforms based tensor-tensor product and tensor SVD. We define a new transforms depended tensor rank and the corresponding tensor nuclear norm. Then we solve the TRPCA problem by convex optimization whose objective is a weighted combination of the new tensor nuclear norm and the $\ell_1$-norm. In theory, we show that under certain incoherence conditions, the convex program exactly recovers the underlying low-rank and sparse components. It is of great interest that our new TRPCA model generalizes existing works. In particular, if the studied tensor reduces to a matrix, our TRPCA model reduces to the known matrix RPCA. Our new TRPCA which is allowed to use general linear transforms can be regarded as an extension of our former TRPCA work which uses the discrete Fourier transform. But their proof of the recovery guarantee is different. Numerical experiments verify our results and the application on image recovery demonstrates the superiority of our method.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This extends the prior DFT-based TRPCA to arbitrary linear transforms with a new tensor rank and nuclear norm, plus a recovery theorem that reduces to matrix RPCA.

read the letter

The core advance is replacing the fixed DFT with a general linear transform in the t-product framework, which leads to a transform-dependent tensor rank and nuclear norm. They then run the standard convex program (weighted nuclear norm plus l1) and claim exact recovery of low-rank plus sparse parts under incoherence conditions on those components. The proof is presented as different from their earlier DFT paper, and the matrix case falls out cleanly when the tensor collapses to two dimensions. That reduction is a nice sanity check and the claim is internally consistent with the t-product literature. Numerical experiments on synthetic data and image recovery are included to back the theory, and they report better results than the DFT version in the image task. The main limitation is that only the abstract is visible here, so the actual proof steps, the precise form of the incoherence conditions, and how sensitive the recovery is to the choice of transform cannot be checked. The experiments follow the usual pattern for this line of work without extensive ablations on transform selection. This is aimed at people already working on tensor RPCA or t-product methods in computer vision and machine learning. It is a straightforward but useful generalization of existing results, so it should go to peer review rather than desk reject.

Referee Report

0 major / 3 minor

Summary. The paper introduces a generalized Tensor Robust Principal Component Analysis (TRPCA) using arbitrary linear transforms within the tensor-tensor product framework. It defines a transform-dependent tensor rank and associated nuclear norm, then solves the TRPCA problem via convex optimization minimizing a weighted combination of this nuclear norm and the ℓ1 norm. The central claim is that, under suitable incoherence conditions with respect to the chosen transform, this program exactly recovers the underlying low-rank and sparse components. The model is shown to reduce to standard matrix RPCA when the input is a matrix and to extend prior DFT-based TRPCA, with supporting numerical experiments and an image recovery application.

Significance. If the recovery guarantee is correct, the work meaningfully extends the scope of TRPCA by permitting flexible linear transforms rather than restricting to the DFT, which may enable improved recovery performance through transform selection. The explicit reduction to the matrix RPCA case provides a useful consistency check, and the experimental results on image recovery offer practical evidence of utility. The theoretical guarantee under general transforms is a positive contribution to the t-product literature.

minor comments (3)

[Abstract] Abstract: the statement that the new proof is 'different' from the prior DFT-based TRPCA work would benefit from a one-sentence indication of the key technical distinction to help readers assess novelty.
Notation: the definition of the linear transform and the induced tensor nuclear norm should be cross-referenced to the relevant equation in the preliminaries section for readers new to the t-product setting.
[Numerical experiments] Experiments: the choice of linear transforms in the numerical section should be justified with a brief remark on why they satisfy the incoherence conditions used in the theory.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is a self-contained mathematical proof

full rationale

The paper states a convex recovery theorem for low-rank plus sparse tensors under a transform-dependent nuclear norm, with the guarantee resting on explicitly stated incoherence conditions w.r.t. an arbitrary linear transform. The argument reduces the tensor case to the known matrix RPCA when the tensor is a matrix and notes that the new proof differs from the authors' prior DFT-based TRPCA; neither reduction nor the cited prior work is used to define the new result. No parameter fitting, self-definitional loops, or load-bearing self-citation chains appear in the derivation chain.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The model rests on the existence and properties of the linear-transform tensor-tensor product and the associated SVD; the weight in the convex objective is a free parameter whose value is not derived from first principles in the abstract.

free parameters (1)

weight in nuclear-norm plus l1 objective
The objective is described as a weighted combination; the abstract does not specify how the weight is chosen or derived.

axioms (1)

standard math Existence and algebraic properties of the linear-transform tensor-tensor product and tensor SVD
The entire construction is motivated by and defined on top of this product.

pith-pipeline@v0.9.0 · 5722 in / 1038 out tokens · 25736 ms · 2026-05-24T20:51:10.921357+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

[1]

Robust principal component analysis?,

Emmanuel J Cand `es, Xiaodong Li, Yi Ma, and John Wright, “Robust principal component analysis?,” J. ACM, vol. 58, no. 3, 2011

work page 2011
[2]

Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization,

Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan, “Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition. IEEE, 2016

work page 2016
[3]

Tensor decompositions and applications,

Tamara G Kolda and Brett W Bader, “Tensor decompositions and applications,” SIAM Rev., vol. 51, no. 3, pp. 455–500, 2009

work page 2009
[4]

Multilinear analysis of image ensembles: Tensorfaces,

M Alex O Vasilescu and Demetri Terzopoulos, “Multilinear analysis of image ensembles: Tensorfaces,” in Proc. European Conf. Computer Vision, pp. 447–460. Springer, 2002

work page 2002
[5]

Tripler- ank: Ranking semantic web data by tensor decomposition,

Thomas Franz, Antje Schultz, Sergej Sizov, and Steffen Staab, “Tripler- ank: Ranking semantic web data by tensor decomposition,” in Int’l Semantic Web Conf., 2009, pp. 213–228

work page 2009
[6]

Parallel factor analysis in sensor array processing,

Nicholas D Sidiropoulos, Rasmus Bro, and Georgios B Giannakis, “Parallel factor analysis in sensor array processing,” IEEE Trans. Signal Processing, vol. 48, no. 8, pp. 2377–2388, 2000

work page 2000
[7]

A fully robust parafac method for analyzing ﬂuorescence data,

Sanne Engelen, Stina Frosch, and Bo M Jorgensen, “A fully robust parafac method for analyzing ﬂuorescence data,” J. Chemometrics, vol. 23, no. 3, pp. 124–131, 2009

work page 2009
[8]

Scalable tensor factorizations with missing data,

Evrim Acar, Tamara G. Kolda, Daniel M. Dunlavy, and Morten Mrup, “Scalable tensor factorizations with missing data,” in IEEE Int’l Conf. Data Mining, 2009, pp. 701–712

work page 2009
[9]

Robust video restoration by joint sparse and low rank matrix approximation,

Hui Ji, Sibin Huang, Zuowei Shen, and Yuhong Xu, “Robust video restoration by joint sparse and low rank matrix approximation,” SIAM J. Imaging Sciences , vol. 4, no. 4, pp. 1122–1142, 2011

work page 2011
[10]

RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images,

Yigang Peng, Arvind Ganesh, John Wright, Wenli Xu, and Yi Ma, “RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images,” IEEE Trans. Pattern Recognition and Machine Intelligence, vol. 34, no. 11, pp. 2233–2246, 2012

work page 2012
[11]

Most tensor problems are NP-hard,

Christopher J Hillar and Lek-Heng Lim, “Most tensor problems are NP-hard,” J. ACM, vol. 60, no. 6, pp. 45, 2013

work page 2013
[12]

Tensor completion for estimating missing values in visual data,

Ji Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye, “Tensor completion for estimating missing values in visual data,” IEEE Trans. Pattern Recognition and Machine Intelligence , vol. 35, no. 1, pp. 208– 220, 2013

work page 2013
[13]

Tensor completion and low-n-rank tensor recovery via convex optimization,

Silvia Gandy, Benjamin Recht, and Isao Yamada, “Tensor completion and low-n-rank tensor recovery via convex optimization,” Inverse Problems, vol. 27, no. 2, pp. 025010, 2011

work page 2011
[14]

Statistical performance of convex tensor decomposition,

Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, and Hisashi Kashima, “Statistical performance of convex tensor decomposition,” in Advances in Neural Information Processing Systems , 2011, pp. 972–980

work page 2011
[15]

Nuclear norm minimization and tensor completion in exploration seismology,

Nadia Kreimer and Mauricio D Sacchi, “Nuclear norm minimization and tensor completion in exploration seismology,” in Proc. IEEE Int’l Conf. Acoustics, Speech and Signal Processing , 2013, pp. 4275–4279

work page 2013
[16]

Tensor versus matrix completion: A comparison with application to spectral data,

Marco Signoretto, R Van De Plas, B De Moor, and Johan A K Suykens, “Tensor versus matrix completion: A comparison with application to spectral data,” IEEE Signal Processing Letters , vol. 18, no. 7, pp. 403– 406, 2011

work page 2011
[17]

Square deal: Lower bounds and improved relaxations for tensor recovery,

Cun Mu, Bo Huang, John Wright, and Donald Goldfarb, “Square deal: Lower bounds and improved relaxations for tensor recovery,” in Proc. Int’l Conf. Machine Learning , 2014, pp. 73–81

work page 2014
[18]

Provable models for robust low-rank tensor completion,

Bo Huang, Cun Mu, Donald Goldfarb, and John Wright, “Provable models for robust low-rank tensor completion,” Paciﬁc J. Optimization, vol. 11, no. 2, pp. 339–364, 2015

work page 2015
[19]

Exact matrix completion via convex optimization,

Emmanuel J Cand `es and Benjamin Recht, “Exact matrix completion via convex optimization,” Foundations of Computational mathematics , vol. 9, no. 6, pp. 717–772, 2009

work page 2009
[20]

A new convex relaxation for tensor completion,

Bernardino Romera-Paredes and Massimiliano Pontil, “A new convex relaxation for tensor completion,” in Advances in Neural Information Processing Systems, 2013, pp. 2967–2975

work page 2013
[21]

6: Performance comparison for image recovery on some sample images

Misha E Kilmer and Carla D Martin, “Factorization strategies for third- 9 (a) (b) (c) (d) (e) (f) Fig. 6: Performance comparison for image recovery on some sample images. (a) Original image; (b) observed image; (c)-(f) recovered images by RPCA, SNN, TRPCA, and our TRPCA-DCT, respectively. Best viewed in ×2 sized color pdf ﬁle. order tensors,” Linear Algeb...

work page 2011
[22]

Novel methods for multilinear data completion and de-noising based on tensor-SVD,

Zemin Zhang, Gregory Ely, Shuchin Aeron, Ning Hao, and Misha Kilmer, “Novel methods for multilinear data completion and de-noising based on tensor-SVD,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition. IEEE, 2014, pp. 3842–3849

work page 2014
[23]

Tensor- based formulation and nuclear norm regularization for multienergy computed tomography,

Oguz Semerci, Ning Hao, Misha E Kilmer, and Eric L Miller, “Tensor- based formulation and nuclear norm regularization for multienergy computed tomography,” IEEE Trans. Image Processing , vol. 23, no. 4, pp. 1678–1693, 2014

work page 2014
[24]

Exact low tubal rank tensor recovery from Gaussian measurements,

Canyi Lu, Jiashi Feng, Zhouchen Lin, and Shuicheng Yan, “Exact low tubal rank tensor recovery from Gaussian measurements,” in Int’l Joint Conf. Artiﬁcial Intelligence , 2018

work page 2018
[25]

Tensor robust principal component analysis with a new tensor nuclear norm,

Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan, “Tensor robust principal component analysis with a new tensor nuclear norm,” IEEE Trans. Pattern Recognition and Machine Intelligence, 2019

work page 2019
[26]

Incoherence-optimal matrix completion,

Yudong Chen, “Incoherence-optimal matrix completion,” IEEE Trans. Information Theory, vol. 61, no. 5, pp. 2909–2923, May 2015

work page 2015
[27]

Exact tensor completion using t- SVD,

Zemin Zhang and Shuchin Aeron, “Exact tensor completion using t- SVD,” IEEE Trans. Signal Processing , vol. 65, no. 6, pp. 1511–1526, 2017

work page 2017
[28]

Tensor–tensor products with invertible linear transforms,

Eric Kernfeld, Misha Kilmer, and Shuchin Aeron, “Tensor–tensor products with invertible linear transforms,” Linear Algebra and its Applications, vol. 485, pp. 545–570, 2015

work page 2015
[29]

The power and arnoldi methods in an algebra of circulants,

David F Gleich, Chen Greif, and James M Varah, “The power and arnoldi methods in an algebra of circulants,” Numerical Linear Algebra with Applications, vol. 20, no. 5, pp. 809–831, 2013

work page 2013
[30]

A uniﬁed alternating direction method of multipliers by majorization minimiza- tion,

Canyi Lu, Jiashi Feng, Shuicheng Yan, and Zhouchen Lin, “A uniﬁed alternating direction method of multipliers by majorization minimiza- tion,” IEEE Trans. Pattern Recognition and Machine Intelligence , vol. 40, no. 3, pp. 527–541, 2018

work page 2018
[31]

A database of human segmented natural images and its application to 10 evaluating segmentation algorithms and measuring ecological statistics,

David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik, “A database of human segmented natural images and its application to 10 evaluating segmentation algorithms and measuring ecological statistics,” in Proc. IEEE Int’l Conf. Computer Vision. IEEE, 2001, vol. 2, pp. 416– 423

work page 2001
[32]

An order- p tensor factorization with applications in imaging,

Carla D Martin, Richard Shafer, and Betsy LaRue, “An order- p tensor factorization with applications in imaging,” SIAM J. Scientiﬁc Computing, vol. 35, no. 1, pp. A474–A490, 2013

work page 2013
[33]

A singular value thresholding algorithm for matrix completion,

Jianfeng Cai, Emmanuel Cand `es, and Zuowei Shen, “A singular value thresholding algorithm for matrix completion,” SIAM J. Optimization , 2010. PLACE PHOTO HERE Canyi Lu is now a postdoctoral research associate in the Carnegie Mellon University. He received his Ph.D. degree from the National University of Singapore in 2017. His current research interests ...

work page 2010

[1] [1]

Robust principal component analysis?,

Emmanuel J Cand `es, Xiaodong Li, Yi Ma, and John Wright, “Robust principal component analysis?,” J. ACM, vol. 58, no. 3, 2011

work page 2011

[2] [2]

Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization,

Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan, “Tensor robust principal component analysis: Exact recovery of corrupted low-rank tensors via convex optimization,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition. IEEE, 2016

work page 2016

[3] [3]

Tensor decompositions and applications,

Tamara G Kolda and Brett W Bader, “Tensor decompositions and applications,” SIAM Rev., vol. 51, no. 3, pp. 455–500, 2009

work page 2009

[4] [4]

Multilinear analysis of image ensembles: Tensorfaces,

M Alex O Vasilescu and Demetri Terzopoulos, “Multilinear analysis of image ensembles: Tensorfaces,” in Proc. European Conf. Computer Vision, pp. 447–460. Springer, 2002

work page 2002

[5] [5]

Tripler- ank: Ranking semantic web data by tensor decomposition,

Thomas Franz, Antje Schultz, Sergej Sizov, and Steffen Staab, “Tripler- ank: Ranking semantic web data by tensor decomposition,” in Int’l Semantic Web Conf., 2009, pp. 213–228

work page 2009

[6] [6]

Parallel factor analysis in sensor array processing,

Nicholas D Sidiropoulos, Rasmus Bro, and Georgios B Giannakis, “Parallel factor analysis in sensor array processing,” IEEE Trans. Signal Processing, vol. 48, no. 8, pp. 2377–2388, 2000

work page 2000

[7] [7]

A fully robust parafac method for analyzing ﬂuorescence data,

Sanne Engelen, Stina Frosch, and Bo M Jorgensen, “A fully robust parafac method for analyzing ﬂuorescence data,” J. Chemometrics, vol. 23, no. 3, pp. 124–131, 2009

work page 2009

[8] [8]

Scalable tensor factorizations with missing data,

Evrim Acar, Tamara G. Kolda, Daniel M. Dunlavy, and Morten Mrup, “Scalable tensor factorizations with missing data,” in IEEE Int’l Conf. Data Mining, 2009, pp. 701–712

work page 2009

[9] [9]

Robust video restoration by joint sparse and low rank matrix approximation,

Hui Ji, Sibin Huang, Zuowei Shen, and Yuhong Xu, “Robust video restoration by joint sparse and low rank matrix approximation,” SIAM J. Imaging Sciences , vol. 4, no. 4, pp. 1122–1142, 2011

work page 2011

[10] [10]

RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images,

Yigang Peng, Arvind Ganesh, John Wright, Wenli Xu, and Yi Ma, “RASL: Robust alignment by sparse and low-rank decomposition for linearly correlated images,” IEEE Trans. Pattern Recognition and Machine Intelligence, vol. 34, no. 11, pp. 2233–2246, 2012

work page 2012

[11] [11]

Most tensor problems are NP-hard,

Christopher J Hillar and Lek-Heng Lim, “Most tensor problems are NP-hard,” J. ACM, vol. 60, no. 6, pp. 45, 2013

work page 2013

[12] [12]

Tensor completion for estimating missing values in visual data,

Ji Liu, Przemyslaw Musialski, Peter Wonka, and Jieping Ye, “Tensor completion for estimating missing values in visual data,” IEEE Trans. Pattern Recognition and Machine Intelligence , vol. 35, no. 1, pp. 208– 220, 2013

work page 2013

[13] [13]

Tensor completion and low-n-rank tensor recovery via convex optimization,

Silvia Gandy, Benjamin Recht, and Isao Yamada, “Tensor completion and low-n-rank tensor recovery via convex optimization,” Inverse Problems, vol. 27, no. 2, pp. 025010, 2011

work page 2011

[14] [14]

Statistical performance of convex tensor decomposition,

Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, and Hisashi Kashima, “Statistical performance of convex tensor decomposition,” in Advances in Neural Information Processing Systems , 2011, pp. 972–980

work page 2011

[15] [15]

Nuclear norm minimization and tensor completion in exploration seismology,

Nadia Kreimer and Mauricio D Sacchi, “Nuclear norm minimization and tensor completion in exploration seismology,” in Proc. IEEE Int’l Conf. Acoustics, Speech and Signal Processing , 2013, pp. 4275–4279

work page 2013

[16] [16]

Tensor versus matrix completion: A comparison with application to spectral data,

Marco Signoretto, R Van De Plas, B De Moor, and Johan A K Suykens, “Tensor versus matrix completion: A comparison with application to spectral data,” IEEE Signal Processing Letters , vol. 18, no. 7, pp. 403– 406, 2011

work page 2011

[17] [17]

Square deal: Lower bounds and improved relaxations for tensor recovery,

Cun Mu, Bo Huang, John Wright, and Donald Goldfarb, “Square deal: Lower bounds and improved relaxations for tensor recovery,” in Proc. Int’l Conf. Machine Learning , 2014, pp. 73–81

work page 2014

[18] [18]

Provable models for robust low-rank tensor completion,

Bo Huang, Cun Mu, Donald Goldfarb, and John Wright, “Provable models for robust low-rank tensor completion,” Paciﬁc J. Optimization, vol. 11, no. 2, pp. 339–364, 2015

work page 2015

[19] [19]

Exact matrix completion via convex optimization,

Emmanuel J Cand `es and Benjamin Recht, “Exact matrix completion via convex optimization,” Foundations of Computational mathematics , vol. 9, no. 6, pp. 717–772, 2009

work page 2009

[20] [20]

A new convex relaxation for tensor completion,

Bernardino Romera-Paredes and Massimiliano Pontil, “A new convex relaxation for tensor completion,” in Advances in Neural Information Processing Systems, 2013, pp. 2967–2975

work page 2013

[21] [21]

6: Performance comparison for image recovery on some sample images

Misha E Kilmer and Carla D Martin, “Factorization strategies for third- 9 (a) (b) (c) (d) (e) (f) Fig. 6: Performance comparison for image recovery on some sample images. (a) Original image; (b) observed image; (c)-(f) recovered images by RPCA, SNN, TRPCA, and our TRPCA-DCT, respectively. Best viewed in ×2 sized color pdf ﬁle. order tensors,” Linear Algeb...

work page 2011

[22] [22]

Novel methods for multilinear data completion and de-noising based on tensor-SVD,

Zemin Zhang, Gregory Ely, Shuchin Aeron, Ning Hao, and Misha Kilmer, “Novel methods for multilinear data completion and de-noising based on tensor-SVD,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition. IEEE, 2014, pp. 3842–3849

work page 2014

[23] [23]

Tensor- based formulation and nuclear norm regularization for multienergy computed tomography,

Oguz Semerci, Ning Hao, Misha E Kilmer, and Eric L Miller, “Tensor- based formulation and nuclear norm regularization for multienergy computed tomography,” IEEE Trans. Image Processing , vol. 23, no. 4, pp. 1678–1693, 2014

work page 2014

[24] [24]

Exact low tubal rank tensor recovery from Gaussian measurements,

Canyi Lu, Jiashi Feng, Zhouchen Lin, and Shuicheng Yan, “Exact low tubal rank tensor recovery from Gaussian measurements,” in Int’l Joint Conf. Artiﬁcial Intelligence , 2018

work page 2018

[25] [25]

Tensor robust principal component analysis with a new tensor nuclear norm,

Canyi Lu, Jiashi Feng, Yudong Chen, Wei Liu, Zhouchen Lin, and Shuicheng Yan, “Tensor robust principal component analysis with a new tensor nuclear norm,” IEEE Trans. Pattern Recognition and Machine Intelligence, 2019

work page 2019

[26] [26]

Incoherence-optimal matrix completion,

Yudong Chen, “Incoherence-optimal matrix completion,” IEEE Trans. Information Theory, vol. 61, no. 5, pp. 2909–2923, May 2015

work page 2015

[27] [27]

Exact tensor completion using t- SVD,

Zemin Zhang and Shuchin Aeron, “Exact tensor completion using t- SVD,” IEEE Trans. Signal Processing , vol. 65, no. 6, pp. 1511–1526, 2017

work page 2017

[28] [28]

Tensor–tensor products with invertible linear transforms,

Eric Kernfeld, Misha Kilmer, and Shuchin Aeron, “Tensor–tensor products with invertible linear transforms,” Linear Algebra and its Applications, vol. 485, pp. 545–570, 2015

work page 2015

[29] [29]

The power and arnoldi methods in an algebra of circulants,

David F Gleich, Chen Greif, and James M Varah, “The power and arnoldi methods in an algebra of circulants,” Numerical Linear Algebra with Applications, vol. 20, no. 5, pp. 809–831, 2013

work page 2013

[30] [30]

A uniﬁed alternating direction method of multipliers by majorization minimiza- tion,

Canyi Lu, Jiashi Feng, Shuicheng Yan, and Zhouchen Lin, “A uniﬁed alternating direction method of multipliers by majorization minimiza- tion,” IEEE Trans. Pattern Recognition and Machine Intelligence , vol. 40, no. 3, pp. 527–541, 2018

work page 2018

[31] [31]

A database of human segmented natural images and its application to 10 evaluating segmentation algorithms and measuring ecological statistics,

David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik, “A database of human segmented natural images and its application to 10 evaluating segmentation algorithms and measuring ecological statistics,” in Proc. IEEE Int’l Conf. Computer Vision. IEEE, 2001, vol. 2, pp. 416– 423

work page 2001

[32] [32]

An order- p tensor factorization with applications in imaging,

Carla D Martin, Richard Shafer, and Betsy LaRue, “An order- p tensor factorization with applications in imaging,” SIAM J. Scientiﬁc Computing, vol. 35, no. 1, pp. A474–A490, 2013

work page 2013

[33] [33]

A singular value thresholding algorithm for matrix completion,

Jianfeng Cai, Emmanuel Cand `es, and Zuowei Shen, “A singular value thresholding algorithm for matrix completion,” SIAM J. Optimization , 2010. PLACE PHOTO HERE Canyi Lu is now a postdoctoral research associate in the Carnegie Mellon University. He received his Ph.D. degree from the National University of Singapore in 2017. His current research interests ...

work page 2010