Tensor completion in hierarchical tensor representations
From MaRDI portal
Abstract: Compressed sensing extends from the recovery of sparse vectors from undersampled measurements via efficient algorithms to the recovery of matrices of low rank from incomplete information. Here we consider a further extension to the reconstruction of tensors of low multi-linear rank in recently introduced hierarchical tensor formats from a small number of measurements. Hierarchical tensors are a flexible generalization of the well-known Tucker representation, which have the advantage that the number of degrees of freedom of a low rank tensor does not scale exponentially with the order of the tensor. While corresponding tensor decompositions can be computed efficiently via successive applications of (matrix) singular value decompositions, some important properties of the singular value decomposition do not extend from the matrix to the tensor case. This results in major computational and theoretical difficulties in designing and analyzing algorithms for low rank tensor recovery. For instance, a canonical analogue of the tensor nuclear norm is NP-hard to compute in general, which is in stark contrast to the matrix case. In this book chapter we consider versions of iterative hard thresholding schemes adapted to hierarchical tensor formats. A variant builds on methods from Riemannian optimization and uses a retraction mapping from the tangent space of the manifold of low rank tensors back to this manifold. We provide first partial convergence results based on a tensor version of the restricted isometry property (TRIP) of the measurement map. Moreover, an estimate of the number of measurements is provided that ensures the TRIP of a given tensor rank with high probability for Gaussian measurement maps.
Recommendations
- Low rank tensor recovery via iterative hard thresholding
- Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
- Iterative hard thresholding for low CP-rank tensor models
- Low-rank tensor recovery using sequentially optimal modal projections in iterative hard thresholding (SeMPIHT)
- On tensor completion via nuclear norm minimization
Cites work
- scientific article; zbMATH DE number 6474942 (Why is no real title available?)
- scientific article; zbMATH DE number 5968745 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- A Multilinear Singular Value Decomposition
- A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion
- A literature survey of low-rank tensor approximation techniques
- A mathematical introduction to compressive sensing
- A new scheme for the tensor representation
- A new tensor decomposition
- A simpler approach to matrix completion
- Algebraic wavelet transform via quantics tensor train decomposition
- Algorithms for Numerical Analysis in High Dimensions
- Approximation rates for the hierarchical tensor format in periodic Sobolev spaces
- Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
- Convergence results for projected line-search methods on varieties of low-rank matrices via Łojasiewicz inequality
- Dynamical approximation by hierarchical Tucker and tensor-train tensors
- Exact matrix completion via convex optimization
- Extraction of quantifiable information from complex systems
- From quantum to classical molecular dynamics: Reduced models and numerical analysis.
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Hierarchical Singular Value Decomposition of Tensors
- Iterative hard thresholding for compressed sensing
- Iterative thresholding for sparse approximations
- Low rank tensor recovery via iterative hard thresholding
- Low-rank matrix completion by Riemannian optimization
- Low-rank tensor completion by Riemannian optimization
- Most tensor problems are NP-hard
- Multivariate regression and machine learning with sums of separable functions
- Normalized iterative hard thresholding for matrix completion
- Numerical tensor calculus
- On local convergence of alternating schemes for optimization of convex problems in the tensor train format
- On manifolds of tensors of fixed TT-rank
- On minimal subspaces in tensor representations
- On the approximation of high-dimensional differential equations in the hierarchical Tucker format
- Optimization on the hierarchical Tucker manifold - applications to tensor completion
- Ranks derived from multilinear maps
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
- Tensor Decompositions and Applications
- Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
- Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
- Tensor rank is NP-complete
- Tensor spaces and numerical tensor calculus
- Tensor-train decomposition
- Tensorisation of vectors and their efficient convolution
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- The alternating linear scheme for tensor optimization in the tensor train format
- The density-matrix renormalization group in the age of matrix product states
- The geometry of algorithms using hierarchical tensors
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
- Tree-based tensor formats
- Well-posedness of convex maximization problems on Stiefel manifolds and orthogonal tensor product approximations
Cited in
(22)- Stable als approximation in the TT-format for rank-adaptive tensor completion
- Preconditioned low-rank Riemannian optimization for linear systems with tensor product structure
- Efficient low-rank regularization-based algorithms combining advanced techniques for solving tensor completion problems with application to color image recovering
- Riemannian optimization for high-dimensional tensor completion
- Covariate regularized community detection in sparse graphs
- Tensor theta norms and low rank recovery
- On identity testing of tensors, low-rank recovery and compressed sensing
- An optimal statistical and computational framework for generalized tensor estimation
- Optimization on the hierarchical Tucker manifold - applications to tensor completion
- Low-rank approximation and completion of positive tensors
- Minimum n-rank approximation via iterative hard thresholding
- Low-rank tensor train for tensor robust principal component analysis
- Variational Bayesian inference for CP tensor completion with subspace information
- Two algorithms for compressed sensing of sparse tensors
- Low rank tensor recovery via iterative hard thresholding
- Modified iterations for data-sparse solution of linear systems
- New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition
- Randomized Algorithms for Rounding in the Tensor-Train Format
- Tensor-based dynamic mode decomposition
- Block tensor train decomposition for missing data estimation
- N-Dimensional Tensor Completion for Nuclear Magnetic Resonance Relaxometry
- Low-rank tensor recovery using sequentially optimal modal projections in iterative hard thresholding (SeMPIHT)
This page was built for publication: Tensor completion in hierarchical tensor representations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460842)
