SpaRCS

Introduction

SpaRCS is a greedy, iterative algorithm that solves the decomposition problem, when we have a compressively sampled video volume, instead of the full video volume. For compression we randomly drop pixels in the video. Here is the optimization formulation for SpaRCS

The operator A randomly drops pixels from the video volume to give us the observation y. The optimization tries to reduce the L2 norm of the error which is y-A(L+S). Since we have observations only at certain points, which are given by the operator A, we try to reduce the total error on those points only. Also notice the constraints. L is subjected to be low rank (ideally rank 1) and S has a sparsity level of atmost K.

Algorithm

Here is the algorithm for SpaRCS:

SpaRCS iteratively estimates L and S given obervations y, a rank estimate r and sparsity estimate K. At each iteration it computes a signal proxy and then proceeds through a 4 step update of its estimates of L and S. Finally the residue is updated. Here are details of the steps

• Signal Proxy computation: The residue w is taken and operator A is applied to it to find P = A(w_k-1). Since we do not know the value of the pixels at the dropped locations, we only look at the residue at those points that the operator A does not drop.
• Support Identification and Merger: We find a candidate support set of both L and S components. Since L is low rank, we perform SVD and add the largest 2r elements to possible support set. Similarly for S which is sparse we add the largest 2K non zero elements to the possible support of S.
• Least Squares Estimation: With the new estimated support we find least squares fits for both L and S
• Support Pruning: Finally to keep the support of L within the rank estimate r, we perform SVD again, and keep only the largest r elements. Similar we constraint the support of S by choosing the largest K elements only, thus keeping its sparsity atmost K.
• Residue Update: Lastly the residue is updated w_k-1 = y=A(L_k+S_k), where L_k and S_k are the estimates for L and S at that iteration.

Results

Here is a screenshot of the video, compressed video and separation results:

Here is a video showing the input video and the compressed video, and also the separation result.