Enhanced image approximation using shifted rank-1 reconstruction

Abstract

Low rank approximation has been extensively studied in the past. It is most suitable to reproduce rectangular like structures in the data. In this work we introduce a generalization using shifted rank-1 matrices to approximate $A\in {\mathbb{C}}^{M\times N}$. These matrices are of the form $S_{\lambda }(u{v}^{\ast })$ where $u\in {\mathbb{C}}^M$, $v\in {\mathbb{C}}^N$ and $\lambda \in {\mathbb{Z}}^N$.The operator $S_{\lambda }$ circularly shifts the k-th column of $u{v}^{\ast }$ by ${\lambda }_k$. These kind of shifts naturally appear in applications, where an object $u$ is observed in $N$ measurements at different positions indicated by the shift $\lambda$. The vector $v$ gives the observation intensity. Exemplary, a seismic wave can be recorded at $N$ sensors with different time of arrival $\lambda$; Or a car moves through a video changing its position in every frame. We present theoretical results as well as an efficient algorithm to calculate a shifted rank-1 approximation in $O(NM\log M)$. The benefit of the proposed method is demonstrated in numerical experiments. A comparison to other sparse approximation methods is given. Finally, we illustrate the utility of the extracted parameters for direct information extraction in several applications including video processing or non-destructive testing.