A New Truncation Strategy for the Higher-Order Singular Value Decomposition

Abstract

We present an alternative strategy for truncating 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 required 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 of $20$. In the second application, classification of handwritten digits, ST-HOSVD achieved a speedup factor of $50$ over T-HOSVD during the training phase, and 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 factor of $133$, while even improving the memory consumption.