The Starting Point

I figure that the best place to start this discussion is with the work that our group already done. One of the major problems with Compressed Sensing is the time required to reconstruct the final signal from its dimensionality reduced form. Let me pause here to say that for a more basic review what exactly Compressed Sensing is and what it is trying to accomplish, there are many researchers that have done an excellent job explaining the fundamentals. I suggest referring to the following resources:

• Tao's Explanation
• Carron's Big Picture
• Rice's Paper Compendium
• Candès and Wakin's Tutorial (pdf warning)

The reconstruction problem is formulated as either an equality or inequality constrained Linear Program, usually solved via a convex optimization process. The problem is this: to find the best value and arrangement of sparse basis coefficients so as to minimize the ell_1 magnitude of the sparse basis coefficients while maintaining an adequate 'closeness', in the case of inequality constrained optimizations, of the resulting image signal in the measurement basis. In other words, we want to find the sparsest signal that could have allowed for the observations we received from the encoder.

The difficulty with this decoding is that we are attempting to optimize an N-dimensional'vector', a time consuming, exponentially complex process that quickly becomes intractable for interestingly sized signals, say, images of size greater than 128x128. For one involved in the development of the theory behind Compressed Sensing, the pure and applied mathematicians, the proof that one can find a solution is enough to consider the solution found, but for engineers seeking to apply the theory to practical implementations, the computational barrier is one that destroys most of Compressed Sensing's potential usefulness.

As engineers, our group is interested in Compressed Sensing for its applications in Remote Sensing. It has already been shown that the theory can be physically implemented in such a way that a single sensor can capture an entire image of arbitrary resolution. This is excellent for applications, such as Remote Sensing within the lower frequency bands of the EM spectrum, where sensors are expensive to build and maintain, where high-resolution banks of them would be monetarily infeasible. However, applying current Compressed Sensing reconstruction techniques to modern Remote Sensing datacube sizes would be an exercise in futility, as the decoding procedure's time to run would be on the order of years.

In order to rein in time complexity of the decoding process, Dr. Fowler and Sungkwang, starting with Gan's work, have been progressing the area of Block Compressed Sensing. This method modifies the standard Compressed Sensing encoding process by enforcing a blocking rule, splitting the image domain into separate subproblems which can be stitched together at the decoder side. The blocking rule has two effects, firstly it restricts the size of the measurement matrix, therefore requiring less memory space on the encoder, and secondly, reducing the decoding time complexity by a few orders of magnitude. In physical implementation of the encoder, this would require a little bit more work, a rotating mirror and some additional lensing, but it would make Compressed Sensing viable for real data set sizes.

So far, we have recorded some significant results in this area and submitted a paper that we hope will soon be accepted and shared with you all. Suffice to say, we are seeing some very high quality reconstructions using this method, and all occurring at very high speed thanks to the low time complexity of the Projected Landweber and Thresholding algorithms.

Next time, I hope to update you all with some of the areas that I am specifically investigating and how it applies to the work we've already done.