Atom-Refined Multiway Greedy Algorithm for Tensor-Based Compressive Sensing

In this paper, we develop a novel multiway greedy algorithm, named atom-refined multiway orthogonal matching pursuit, for tensor-based compressive sensing (TCS) reconstruction. The alternative supports of each dimension are selected using the respective inner product tensors and refined via a global least square coefficients tensor. For each inner product tensor, the Frobenius-norm (F-norm) of the tensor bands, instead of the largest magnitude entry, is employed to measure the correlation between the atoms and the residual. Theoretical analysis shows that the proposed algorithm could guarantee to exactly reconstruct an arbitrary multi-dimensional block-sparse signal in the absence of noise, provided that the sensing matrices for each dimension satisfy restricted isometry properties with constant parameters. The maximum required number of iterations for exact reconstruction shows an approximate logarithmic growth as the signal size increases. Furthermore, under the noise condition, it is presented that the F-norm of the reconstruction error can be upper-bounded by using the F-norm of noise and the restricted isometry constants of sensing matrices for each dimension. The simulation results demonstrate that the proposed algorithm exhibits obvious advantages as regards both reconstruction accuracy and speed compared with the existing multiway greedy algorithms. Besides TCS, the proposed algorithm also has the potential to be applied in diverse fields, such as hyperspectral image processing and tensor-based dictionary learning.