On tensor completion via nuclear norm minimization

DOI10.1007/S10208-015-9269-5zbMATH Open1378.90066arXiv1405.1773OpenAlexW1885765327MaRDI QIDQ330103FDOQ330103

Ming Yuan, Cun-Hui Zhang

Publication date: 24 October 2016

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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 subdifferetial 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.

Full work available at URL: https://arxiv.org/abs/1405.1773

Recommendations

• Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
• On polynomial time methods for exact low-rank tensor completion
• Spectral algorithms for tensor completion
• scientific article
• Low-rank tensor completion by Riemannian optimization

zbMATH Keywords

concentration inequalitymatrix completiondual certificatetensor completionconvex optimization problemlow-rank tensornuclear norm minimizationsubfifferential

Mathematics Subject Classification ID

Convex programming (90C25) Approximation methods and heuristics in mathematical programming (90C59) Miscellaneous inequalities involving matrices (15A45)

Cites Work

• Tensor Decompositions and Applications
• Exact matrix completion via convex optimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Characterization of the subdifferential of some matrix norms
• User-friendly tail bounds for sums of random matrices
• Tensor completion and low-n-rank tensor recovery via convex optimization
• Most Tensor Problems Are NP-Hard
• Some limit theorems for empirical processes (with discussion)
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• A Simpler Approach to Matrix Completion
• Tensor Algebra and Multidimensional Harmonic Retrieval in Signal Processing for MIMO Radar
• Tensor-Based Formulation and Nuclear Norm Regularization for Multienergy Computed Tomography

Cited In (65)

• Title not available (Why is that?)
• Tensor completion via a generalized transformed tensor t-product decomposition without t-SVD
• Low tubal rank tensor recovery using the Bürer-Monteiro factorisation approach. Application to optical coherence tomography
• Dynamic Tensor Clustering
• Multilayer tensor factorization with applications to recommender systems
• Algebraic Methods for Tensor Data
• Title not available (Why is that?)
• Learning diagonal Gaussian mixture models and incomplete tensor decompositions
• Tensor completion by multi-rank via unitary transformation
• Title not available (Why is that?)
• On polynomial time methods for exact low-rank tensor completion
• Near-optimal sample complexity for convex tensor completion
• Scaled Coupled Norms and Coupled Higher-Order Tensor Completion
• Title not available (Why is that?)
• Tensor theta norms and low rank recovery
• An optimal statistical and computational framework for generalized tensor estimation
• The Fréchet derivative of the tensor t-function
• Low-rank approximation and completion of positive tensors
• Relations of the nuclear norm of a tensor and its matrix flattenings
• Inference for low-rank tensors -- no need to debias
• Efficient Construction of Tensor Ring Representations from Sampling
• Iterative methods based on soft thresholding of hierarchical tensors
• Continuity, differentiability and semismoothness of generalized tensor functions
• Further results on tensor nuclear norms
• Statistically optimal and computationally efficient low rank tensor completion from noisy entries
• Completely positive tensor recovery with minimal nuclear value
• Nonconvex tensor rank minimization and its applications to tensor recovery
• Symmetric Tensor Nuclear Norms
• Interpolatory tensorial reduced order models for parametric dynamical systems
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Biquadratic tensors, biquadratic decompositions, and norms of biquadratic tensors
• Spectral norm and nuclear norm of a third order tensor
• An approximation method of CP rank for third-order tensor completion
• Fiber Sampling Approach to Canonical Polyadic Decomposition and Application to Tensor Completion
• Convergence bounds for empirical nonlinear least-squares
• A concise proof to the spectral and nuclear norm bounds through tensor partitions
• Reshaped tensor nuclear norms for higher order tensor completion
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• On the tensor spectral \(p\)-norm and its dual norm via partitions
• ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching
• Hankel Matrix Nuclear Norm Regularized Tensor Completion for $N$-dimensional Exponential Signals
• Factor Models for High-Dimensional Tensor Time Series
• Rank minimization on tensor ring: an efficient approach for tensor decomposition and completion
• The Geometry of Rank-One Tensor Completion
• Tensor Q-rank: new data dependent definition of tensor rank
• Learning with tree tensor networks: complexity estimates and model selection
• Highly entangled tensors
• $N$-Dimensional Tensor Completion for Nuclear Magnetic Resonance Relaxometry
• Cross: efficient low-rank tensor completion
• Block tensor train decomposition for missing data estimation
• Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion
• Hybrid Kronecker Product Decomposition and Approximation
• Bayesian Dynamic Tensor Regression
• Matrix completion from a computational statistics perspective
• A tensor train approach for internet traffic data completion
• Approximating Tensor Norms via Sphere Covering: Bridging the Gap between Primal and Dual
• Optimality conditions for Tucker low-rank tensor optimization
• Title not available (Why is that?)
• Deterministic Tensor Completion with Hypergraph Expanders
• Sample complexity bounds for the local convergence of least squares approximation
• Block structure-based covariance tensor decomposition for group identification in matrix variables
• LOCUS: a regularized blind source separation method with low-rank structure for investigating brain connectivity
• Partially Observed Dynamic Tensor Response Regression
• Exponential family tensor completion with auxiliary information
• Iterative tensor eigen rank minimization for low-rank tensor completion

This page was built for publication: On tensor completion via nuclear norm minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q330103)