Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Foundations of Computational Mathematics
Published in: Foundations of Computational Mathematics 4/2016

01-08-2016

On Tensor Completion via Nuclear Norm Minimization

Authors: Ming Yuan, Cun-Hui Zhang

Published in: Foundations of Computational Mathematics | Issue 4/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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 subdifferential 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.
previous article Sharp MSE Bounds for Proximal Denoising

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
E.J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9, 717–772 (2008).
2.
E.J. Candès and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Transactions on Information Theory, 56(5), 2053–2080 (2009).
3.
S. Cohen and M. Collins, Tensor decomposition for fast parsing with latent-variable pcfgs, in Proceedings of NIPS 2012 (2012).
4.
S. Gandy, B. Recht and I. Yamada, Tensor completion and low-n-rank tensor recovery via convex optimization, Inverse Problems, 27(2), 025010 (2011).
5.
E. Giné and J. Zinn, Some limit theorems for empirical processes, The Annals of Probability, 12(4), 929–989 (1984).
6.
D. Gross, Recovering low-rank matrices from few coefficients in any basis, IEEE Transaction on Information Theory, 57, 1548–1566 (2011).
7.
C. Hillar and L.H. Lim, Most tensor problems are NP-hard, Journal of the ACM, 60(6), Art. 45 (2013).
8.
T.G. Kolda and B.W. Bader, Tensor decompositions and applications, SIAM Review, 51(3), 455–500 (2009).
9.
J.B. Kruskal, Rank, decomposition, and uniqueness for 3-way and N-way arrays, in “Multiway data analysis”, North-Holland, Amsterdam, pp. 7–18 (1989).
10.
N. Li and B. Li, Tensor completion for on-board compression of hyperspectral images, In Image Processing (ICIP), 2010 17th IEEE International Conference on, 517–520 (2010).
11.
J. Liu, P. Musialski, P. Wonka and J. Ye, Tensor completion for estimating missing values in visual data, In ICCV, 2114–2121 (2009).
12.
N. Mesgarani, M. Slaney and S. Shamma, Content-based audio classification based on multiscale spectro-temporal features, IEEE Transactions on Speech and Audio Processing, 14(3), 920–930 (2006).
13.
C. Mu, B. Huang, J. Wright and D. Goldfarb, Square deal: lower bounds and improved relaxations for tensor recovery, arXiv:​ 1307.​5870 (2013).
14.
B. Recht, A simpler approach to matrix completion, Journal of Machine Learning Research, 12, 3413–3430 (2011).
15.
O. Semerci, N. Hao, M. Kilmer and E. Miller, Tensor based formulation and nuclear norm regularizatin for multienergy computed tomography, IEEE Transactions on Image Processing, 23(4), 1678–1693 (2014).
16.
N.D. Sidiropoulos and N. Nion, Tensor algebra and multi-dimensional harmonic retrieval in signal processing for mimo radar, IEEE Trans. on Signal Processing, 58(11), 5693–5705 (2010).
17.
18.
M. Signoretto, R. Van de Plas, B. De Moor and J. Suykens, Tensor versus matrix completion: A comparison with application to spectral data, IEEE SPL, 18(7), 403–406 (2011).
19.
R. Tomioka, K. Hayashi and H. Kashima, Estimation of low-rank tensors via convex optimization, arXiv preprint arXiv:​1010.​0789 (2010).
20.
R. Tomioka, T. Suzuki, K. Hayashi and H. Kashima, Statistical performance of convex tensor decomposition, Advances in Neural Information Processing Systems (NIPS), 137 (2011).
21.
J. Tropp, User-friendly tail bounds for sums of random matrices, Foundations of Computational Mathematics, 12, 389–434 (2012).
22.
G. A. Watson, Characterization of the subdifferential of some matrix norms, Linear Algebra Appl., 170, 33–45 (1992).
Metadata
Title
On Tensor Completion via Nuclear Norm Minimization
Authors
Ming Yuan
Cun-Hui Zhang
Publication date
01-08-2016
Publisher
Springer US
Published in
Foundations of Computational Mathematics / Issue 4/2016
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI
https://doi.org/10.1007/s10208-015-9269-5

Other articles of this Issue 4/2016

Foundations of Computational Mathematics 4/2016 Go to the issue

OriginalPaper

Discrete Morse Theory for Computing Cellular Sheaf Cohomology

OriginalPaper

Tensor-Sparsity of Solutions to High-Dimensional Elliptic Partial Differential Equations

OriginalPaper

A Primal-Dual Formulation for Certifiable Computations in Schubert Calculus

OriginalPaper

Sharp MSE Bounds for Proximal Denoising

OriginalPaper

Integrators on Homogeneous Spaces: Isotropy Choice and Connections

Premium Partner

    Image Credits