# American Institute of Mathematical Sciences

April  2020, 14(2): 267-290. doi: 10.3934/ipi.2020012

## Enhanced image approximation using shifted rank-1 reconstruction

 Harbin Institute of Technology, Department of Mathematics, 150001 Harbin, China

Received  February 2019 Revised  December 2019 Published  February 2020

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 $\mathit{\boldsymbol{{A}}}\in \mathbb{C}^{M\times N}$. These matrices are of the form $S_{\mathit{\boldsymbol{{\lambda}}}}(\mathit{\boldsymbol{{u}}}\mathit{\boldsymbol{{v}}}^*)$ where $\mathit{\boldsymbol{{u}}}\in \mathbb{C}^M$, $\mathit{\boldsymbol{{v}}}\in \mathbb{C}^N$ and $\mathit{\boldsymbol{{\lambda}}}\in \mathbb{Z}^N$. The operator $S_{\mathit{\boldsymbol{{\lambda}}}}$ circularly shifts the $k$-th column of $\mathit{\boldsymbol{{u}}}\mathit{\boldsymbol{{v}}}^*$ by $\lambda_k$.

These kind of shifts naturally appear in applications, where an object $\mathit{\boldsymbol{{u}}}$ is observed in $N$ measurements at different positions indicated by the shift $\mathit{\boldsymbol{{\lambda}}}$. The vector $\mathit{\boldsymbol{{v}}}$ gives the observation intensity. This model holds for seismic waves that are recorded at $N$ sensors at different times $\mathit{\boldsymbol{{\lambda}}}$. Other examples are a car that moves through a video changing its position $\mathit{\boldsymbol{{\lambda}}}$ in each of the $N$ frames, or non-destructive testing based on ultrasonic waves that are reflected by defects inside the material.

The main difficulty of the above stated problem lies in finding a suitable shift vector $\mathit{\boldsymbol{{\lambda}}}$. Once the shift is known, a simple singular value decomposition can be applied to reconstruct $\mathit{\boldsymbol{{u}}}$ and $\mathit{\boldsymbol{{v}}}$. We propose a greedy method to reconstruct $\mathit{\boldsymbol{{\lambda}}}$. By using the formulation of the problem in Fourier domain, a shifted rank-$1$ approximation can be calculated in $O(NM\log M)$. Convergence to a locally optimal solution is guaranteed. Furthermore, we give a heuristic initial guess strategy that shows good results in the numerical experiments.

We validate our approach in several numerical experiments on different kinds of data. We compare the technique to shift-invariant dictionary learning algorithms. Furthermore, we provide examples from application including object segmentation in non-destructive testing and seismic exploration as well as object tracking in video processing.

Citation: Florian Bossmann, Jianwei Ma. Enhanced image approximation using shifted rank-1 reconstruction. Inverse Problems & Imaging, 2020, 14 (2) : 267-290. doi: 10.3934/ipi.2020012
##### References:

show all references

##### References:
Input data: Cartoon-like, natural, ultrasonic and seismic images
(a) Singular value ratio to $\||\hat{\bm{{A}}}|\|_2$ after the individual steps of Algorithm 3. (b) Average approximation error over all kinds of input data
Reconstruction of Lena image using 1, 5 and 10 shifted rank-$1$ matrices
Approximation error of all algorithms for different kinds of input data plotted against the storage costs
Sparse approximation of image "phantom" using Wavelets (left), SR1 (middle) and UC-DLA (right)
(a) Average runtime of data approximation against the number of rows. (b) Average runtime of matrix vector multiplication using different number of shifted rank-$1$ matrices
Separation of an ultrasonic image in two signals (top and bottom) using SR1 (left), MoTIF (middle) and UC-DLA (right)
Identified earth layer reflection in noisy seismic image
Tracked route in original video (top) and reconstructed singular vectors $\mathit{\boldsymbol{{u}}}^1$, $\mathit{\boldsymbol{{u}}}^2$ (middle); as comparison the reconstructed background and person using MAMR is shown (bottom)
First and last frame of the soccer video clip
Tracked objects in soccer clip (top): advertising banners, referee and time stamp. As comparison the reconstructed background and foreground using MAMR is shown (bottom)
Mean number of iterations for different kinds of input data
 data global local total orthogonal 139 21 160 natural 137 24 161 cartoon 91 15 106 seismic 95 16 111 ultrasound 95 18 113
 data global local total orthogonal 139 21 160 natural 137 24 161 cartoon 91 15 106 seismic 95 16 111 ultrasound 95 18 113
 [1] Vasso Anagnostopoulou. Stochastic dominance for shift-invariant measures. Discrete & Continuous Dynamical Systems, 2019, 39 (2) : 667-682. doi: 10.3934/dcds.2019027 [2] R. Yamapi, R.S. MacKay. Stability of synchronization in a shift-invariant ring of mutually coupled oscillators. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 973-996. doi: 10.3934/dcdsb.2008.10.973 [3] Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006 [4] Simon Arridge, Pascal Fernsel, Andreas Hauptmann. Joint reconstruction and low-rank decomposition for dynamic inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021059 [5] Rua Murray. Approximation error for invariant density calculations. Discrete & Continuous Dynamical Systems, 1998, 4 (3) : 535-557. doi: 10.3934/dcds.1998.4.535 [6] Antonio G. García. Sampling in $\Lambda$-shift-invariant subspaces of Hilbert-Schmidt operators on $L^2(\mathbb{R}^d)$. Mathematical Foundations of Computing, 2021, 4 (4) : 281-297. doi: 10.3934/mfc.2021019 [7] Henk Broer, Aaron Hagen, Gert Vegter. Numerical approximation of normally hyperbolic invariant manifolds. Conference Publications, 2003, 2003 (Special) : 133-140. doi: 10.3934/proc.2003.2003.133 [8] Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076 [9] Changming Song, Yun Wang. Nonlocal latent low rank sparse representation for single image super resolution via self-similarity learning. Inverse Problems & Imaging, 2021, 15 (6) : 1347-1362. doi: 10.3934/ipi.2021017 [10] Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321 [11] Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83 [12] Yanfeng Guo, Jinqiao Duan, Donglong Li. Approximation of random invariant manifolds for a stochastic Swift-Hohenberg equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (6) : 1701-1715. doi: 10.3934/dcdss.2016071 [13] Gilles Carbou, Bernard Hanouzet. Relaxation approximation of the Kerr model for the impedance initial-boundary value problem. Conference Publications, 2007, 2007 (Special) : 212-220. doi: 10.3934/proc.2007.2007.212 [14] Richard Archibald, Hoang Tran. A dictionary learning algorithm for compression and reconstruction of streaming data in preset order. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021102 [15] Chris Guiver. The generalised singular perturbation approximation for bounded real and positive real control systems. Mathematical Control & Related Fields, 2019, 9 (2) : 313-350. doi: 10.3934/mcrf.2019016 [16] Lucian Coroianu, Danilo Costarelli, Sorin G. Gal, Gianluca Vinti. Approximation by multivariate max-product Kantorovich-type operators and learning rates of least-squares regularized regression. Communications on Pure & Applied Analysis, 2020, 19 (8) : 4213-4225. doi: 10.3934/cpaa.2020189 [17] Peng Jiang. Unique global solution of an initial-boundary value problem to a diffusion approximation model in radiation hydrodynamics. Discrete & Continuous Dynamical Systems, 2015, 35 (7) : 3015-3037. doi: 10.3934/dcds.2015.35.3015 [18] Zhouchen Lin. A review on low-rank models in data analysis. Big Data & Information Analytics, 2016, 1 (2&3) : 139-161. doi: 10.3934/bdia.2016001 [19] Mingchao Zhao, You-Wei Wen, Michael Ng, Hongwei Li. A nonlocal low rank model for poisson noise removal. Inverse Problems & Imaging, 2021, 15 (3) : 519-537. doi: 10.3934/ipi.2021003 [20] Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems & Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011

2020 Impact Factor: 1.639

## Tools

Article outline

Figures and Tables