| October 12, 11:00

Low-rank tensor recovery via Iterative Hard Thresholding algorithm

Zeljka Stojanac

Low-rank tensor recovery is an interesting subject from both theoretical and application point of view. On one side, it is a natural extension of the sparse vector and low-rank matrix recovery problem. On the other side, estimating a low-rank tensor has applications in many different areas such as machine learning, video compression, and seismic data interpolation. In this talk, an iterative approach to low rank tensor recovery is introduced. This approach is a generalization of the iterative hard thresholding algorithm for sparse vector and low-rank matrix recovery to tensor scenario (tensor IHT or TIHT algorithm). Here, we consider the tensor train decomposition (or TT-decomposition), also called the matrix product states (or MPS). The a! nalysis of the algorithm is based on a version of the restricted isometry property (tensor RIP or TRIP). We show that subgaussian measurement ensembles satisfy TRIP with high probability under an almost optimal condition on the number of measurements. Additionally, we show that partial Fourier maps combined with random sign flips of the tensor entries satisfy TRIP with high probability. Under the assumption that the linear operator satisfies TRIP and under an additional assumption on the thresholding operator, we provide a linear convergence result for the TIHT algorithm. Similar results also hold for HOSVD (Tucker) and Hierarchical Tucker decomposition (HT-decomposition). Finally, we illustrate the performance of iterative hard thresholding algorithm for tensor recovery via numerical experiments where we consider recovery from Gaussian measurement ensembles and Fourier measurements for third order tensors.


Universität Bonn
Seminarroom 0.02, ETP
Contact: not specified