| Paper: | DISPS-L1.2 | ||
| Session: | Fast Algorithm Design and Synthesis | ||
| Time: | Wednesday, May 17, 16:50 - 17:10 | ||
| Presentation: | Lecture | ||
| Topic: | Design and Implementation of Signal Processing Systems: Fast Algorithms | ||
| Title: | Adaptive Multilinear SVD for Structured Tensors | ||
| Authors: | Rémy Boyer, LSS / CNRS / Supélec / Université Paris-Sud, XI, France; Roland Badeau, GET / Télécom Paris, France | ||
| Abstract: | The Higher-Order SVD (HOSVD) is a generalization of the SVD to higher-order tensors ({\em ie.} arrays with more than two indexes) and plays an important role in various domains. Unfortunately, the computational cost of this decomposition is very high since the basic HOSVD algorithm involves the computation of the SVD of three {\em highly redundant block-Hankel} matrices, called modes. In this paper, we present an ultra-fast way of computing the HOSVD of a third-order structured tensor. The key result of this work lies in the fact it is possible to reduce the basic HOSVD algorithm to the computation of the SVD of three {\em non-redundant Hankel} matrices whose columns are multiplied by a given weighting function. Next, we exploit an FFT-based implementation of the orthogonal iteration algorithm in an adaptive way. Even though for a square ($I \times I \times I$) tensor the complexity of the basic full-HOSVD is $O(I^4)$ and $O(rI^3)$ for its $r$-truncated version, our approach reaches a linear complexity of $O(rI \log_2(I))$. | ||
©2018 Conference Management Services, Inc. -||- email: webmaster@icassp2006.org -||- Last updated Friday, August 17, 2012