# Compressed Sensing

Singular Value Thresholding Algorithm
We introduced a method to recover a large low rank matrix from a small subset of its entries by developing a simple first-order and easy-to-implement algorithm that is extremely efficient. The algorithm is iterative, produces a sequence of matrice, and at each step performs a thresholding operation on the singular values of the matrix. This led to the iterative singular value thresholding (SVT) algorithm of .  We also provided a convergence analysis showing that the sequence of iterates converges in .  The SVT algorithm is to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints which may be understood as the convex relaxation of a rank minimization problem. It may also be understood as applying the three steps of iterative thresholding algorithms for image restorations. The first step is to find an approximate solution from the given observed data; then perform a thresholding operation in a  domain where the approximate solution has a  sparse representation; and, finally, iterate until convergence. In fact, the low rank matrix completion problem can be viewed as an image inpainting problem. The only difference is the sparsifying transformation used for the matrix completion problem is the singular value decomposition and the thresholding operation is performed on the singular values of the matrix.

1. Jainfeng Cai, Emmanuel. J. Candes, Zuowei Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20 (4) (2010), 1956-1982. SVT.pdf

CT reconstruction
Respiration-correlated cone-beam computed tomography (CBCT), commonly called 4DCBCT, provides respiratory phase-resolved CBCT images. A typical 4DCBCT consists of a small number (usually 10 or less) of CBCT images, each corresponding to a particular breathing phase and reconstructed using all projections falling in that phase bin over the 4DCBCT scan. Therefore, 4DCBCT represents averaged patient images over one breathing cycle and the 4th dimension is actually the breathing phase instead of time. In many clinical applications, it is desirable to obtain true 4DCBCT with the 4th dimension being time, i.e., each constituent CBCT image corresponds to an instantaneous projection. Theoretically, it is impossible to reconstruct a CBCT image from a single projection. However, if all the constituent CBCT images of a 4DCBCT scan share a lot of redundant information and can be represented with or approximated by linear combinations of a small number of basis images, it might be possible to make a good reconstruction of these images by exploring sparsity and coherence/redundancy of these CBCT images. These CBCT images are not completely time resolved since they are represented by a small number of basis images, but they can exploit both local and global temporal coherence of the patient anatomy automatically and contain much more temporal variation information of the patient geometry than the conventional 4DCBCT. We proposed in this work a computational model and algorithms for the reconstruction of this type of semi-time-resolved CBCT, called cine-CBCT, based on low rank approximation that can utilize the underlying temporal coherence both locally and globally, such as slow variation, periodicity, or repetition, in those cine-CBCT images.

1. Jianfeng Cai, Xun Jia, Hao Gao, Steve B. Jiang, Zuowei Shen, Hongkai Zhao, Cine cone beam CT reconstruction using low-rank matrix factorization: algorithm and a proof-of-principle study, IEEE Transactions on Medical Imaging 33 (8) (2014), 1581-1591. PDF
2. Hao Gao, Jianfeng Cai, Zuowei Shen, Hongkai Zhao, Robust principle component analysis based four-dimensional computed tomography, Physics in Medicine and Biology, 56(11) (2011), 3181-3198. PDF

Video Processing
Most existing video denoising algorithms assume a single statistical model of image noise, e.g. additive Gaussian white noise, which often is violated in practice. In this project, we presented a new patch-based video denoising algorithm capable of removing serious mixed noise from video data. We formulated the problem of removing mixed noise as a low-rank matrix completion problem by grouping similar patches in both spatial and temporal domains. This led to a denoising scheme without strong assumptions on the statistical properties of the noise.

1. Hui Ji, Sibin Huang, Zuowei Shen, Yuhong Xu, Robust video restoration by joint sparse and low rank matrix approximation, SIAM Journal on Imaging Sciences, 4 (4) (2011), 1122-1142 PDF
2. Hui Ji, Chaoqiang Liu, Zuowei Shen, Yuhong Xu, Robust video denoising using low rank matrix completion, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), San Francisco, 2010. PDF

Video Analysis
In computer vision, inferring scene geometry and camera motion from a sequence of images is a well-studied problem known as the structure-from-motion problem. This is an ill-conditioned problem for objects that may be distant with respect to their size, or especially for “missing data” that occur because of occlusion or tracking failures. However, when properly stacked and indexed, these images form a matrix that has a very low rank. We addressed the problem of reconstructing and analyzing surveillance videos by decomposing this matrix to a sum of a low rank matrix and a sparse matrix.

1. Hong Jiang, Songqing Zhao, Zuowei Shen, Wei Deng, Paul Wilford, Raziel, Haimi-Cohen, Surveillance video analysis using compressive sensing with low latency, Bell Labs Technical Journal, 18(4), (2014), 63-74. PDF
2. Fei Yang, Hong Jiang, Zuowei Shen, Wei Deng, Dimitris Metaxas, Adaptive low rank and sparse decomposition of video using compressive sensing, IEEE International Conference on Image Processing (ICIP) Melbourne, Australia, 2013. PDF
3. Hong Jiang, Wei Deng, Zuowei Shen, Surveillance video processing using compressive sensing, Inverse Problem and Imaging, 6 (2), (2012), 201-214. PDF