Author:

Keywords:

tensor, sequentially truncated higher-order singular value decomposition, higher-order singular value decomposition, multilinear singular value decomposition, multilinear orthogonal projection, Science & Technology, Physical Sciences, Mathematics, Applied, Mathematics, PRODUCT APPROXIMATION, MULTIWAY ALGORITHMS, RANK APPROXIMATION, SVD, DIMENSIONALITY, DISCRIMINATION, TENSORS, SPEECH, 0102 Applied Mathematics, 0103 Numerical and Computational Mathematics, 0802 Computation Theory and Mathematics, Numerical & Computational Mathematics, 4901 Applied mathematics, 4903 Numerical and computational mathematics

Abstract:

We present an alternative strategy to truncate the higher-order singular value decomposition (T-HOSVD). An error expression for an approximate Tucker decomposition with orthogonal factor matrices is presented, leading us to propose a novel truncation strategy for the HOSVD, which we refer to as the sequentially truncated higher-order singular value decomposition (ST-HOSVD). This decomposition retains several favorable properties of the T-HOSVD, while reducing the number of operations to compute the decomposition and practically always improving the approximation error. Three applications are presented, demonstrating the effectiveness of ST-HOSVD. In the first application, ST-HOSVD, T-HOSVD and Higher-Order Orthogonal Iteration (HOOI) are employed to compress a database of images of faces. On average, the ST-HOSVD approximation was only 0.1% worse than the optimum computed by HOOI, while cutting the execution time by a factor 20. In the second application, classification of handwritten digits, ST-HOSVD achieved a speedup of 50 over T-HOSVD during the training phase, reduced the classification time and storage costs, while not significantly affecting the classification error. The third application demonstrates the effectiveness of ST-HOSVD in compressing results from a numerical simulation of a partial differential equation. In such problems, ST-HOSVD inevitably can greatly improve the running time. We present an example wherein the 2 hour 45 minute calculation of T-HOSVD was reduced to just over one minute by ST-HOSVD, representing a speedup of 133, while even improving the memory consumption.