SIAM Journal on Scientific Computing vol:34 issue:2 pages:A1027-A1052
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 ﬁrst 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 signiﬁcantly 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.