Fast algorithms for higher-order singular value decomposition from incomplete data

DOI10.4208/JCM.1608-M2016-0641MaRDI QIDQ4688138zbMATH OpenOpenAlexFDO

Authors Yangyang Xu

Publication date 22 October 2018

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

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

zbMATH Keywords

global convergencehigher-order orthogonality iterationhigher-order singular value decompositionlow-rank tensor completionmultilinear data analysisnon-convex optimization

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Matrix completion problems (15A83)

Abstract: Higher-order singular value decomposition (HOSVD) is an efficient way for data reduction and also eliciting intrinsic structure of multi-dimensional array data. It has been used in many applications, and some of them involve incomplete data. To obtain HOSVD of the data with missing values, one can first impute the missing entries through a certain tensor completion method and then perform HOSVD to the reconstructed data. However, the two-step procedure can be inefficient and does not make reliable decomposition. In this paper, we formulate an incomplete HOSVD problem and combine the two steps into solving a single optimization problem, which simultaneously achieves imputation of missing values and also tensor decomposition. We also present two algorithms for solving the problem based on block coordinate update. Global convergence of both algorithms is shown under mild assumptions. The convergence of the second algorithm implies that of the popular higher-order orthogonality iteration (HOOI) method, and thus we, for the first time, give global convergence of HOOI. In addition, we compare the proposed methods to state-of-the-art ones for solving incomplete HOSVD and also low-rank tensor completion problems and demonstrate the superior performance of our methods over other compared ones. Furthermore, we apply them to face recognition and MRI image reconstruction to show their practical performance.

Recommendations

• Fast Multilinear Singular Value Decomposition for Structured Tensors
• An iterative method for tensor inpainting based on higher-order singular value decomposition
• A new truncation strategy for the higher-order singular value decomposition
• A low-rank tensor-based algorithm for face recognition
• A Multilinear Singular Value Decomposition

Cited in

(7)

• A new truncation strategy for the higher-order singular value decomposition
• scientific article; zbMATH DE number 2045498 (Why is no real title available?)
• Fast Multilinear Singular Value Decomposition for Structured Tensors
• Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition
• Incremental algorithms for truncated higher-order singular value decompositions
• A multiscale reduced-order-model strategy for transient thermoelasticity with variable microstructure
• Cyclical inverse interpolation: an approach for the inverse interpolation of black-box models using tensor product representations

This page was built for publication: Fast algorithms for higher-order singular value decomposition from incomplete data

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