Warm-start Algorithm and Versatile Platform Design for Sparse Reconstruction Applications
Date Issued
2012
Date
2012
Author(s)
Yang, Tien-Ju
Abstract
Sparsity is a property of the natural world. For decades, the sparsity of natural signals has played an important role in various fields such as data compression. The powerfulness of sparsity is also demonstrated in the human brains. In recent years, compressed sensing and sparse representation have attracted substantial attention in the signal processing and computer vision communities. Compressed sensing demonstrates that a sparse signal can be recovered precisely using a sampling rate lower than that proposed in Nyquist-Shannon theory; additionally, the compression is conducted as the signal is sensed. Sparse representation models a signal as a sparse linear combination of atoms from a dictionary, achieving state-of-the-art performance for several computer vision routines. These two techniques are built on sparse reconstruction algorithms. Sparse reconstruction algorithms solve an underdetermined system of linear equations based on the assumption that the answer or the target signal is sparse. The main challenge of sparse reconstruction is the high computational complexity, which hinders its integration into applications that require real-time processing or that have stringent power constraints.
In this thesis, to address the issues mentioned previously, we propose a warm-start homotopy-based algorithm (WarmL1) and a corresponding platform for sparse signal reconstruction. WarmL1 provides a general method for rapidly reconstructing a sparse signal under several dynamic system modifications. Although the system is altered slightly, resolving the new problem from a base level requires significant computational resources. WarmL1 solves the new problem by adopting the previous result as the starting point rather than recalculating a new solution from the base level. According to the experimental results, the non-warm-start homotopy-based algorithm provides the most balanced performance regarding the need for measurements, speed, and reconstruction accuracy with noiseless and noisy measurements among existent non-warm-start algorithms. In this study, we also included several algorithm optimization methods for practical implementation. Extensive numerical experiments and applications were performed and proposed. The results show that WarmL1 can achieve 3.2x to 37.5x acceleration or up to 1/5100 l2-error at the same computational costs compared to that achieved in related works.
The platform with the Application-Specific Integrated Circuit (ASIC) implementation enables real-time and low-power sparse reconstruction applications to be realized. Considering the versatility, the platform supports both compressed sensing and sparse representation applications, and both non-warm-start and warm-start reconstructions. The primary challenges are the high bandwidth demands, storage requirements, and computational complexity. To address the bandwidth and storage requirements, we proposed an online matrix generation scheme with fast state-skipping technique. In this scheme, only the seeds are stored, and the entries in the sensing matrix are randomly generated using the seeds and given state transitions. Thus, the storage requirements are reduced from 1 Gb to 10 Kb. Moreover, the fast state-skipping technique enables rapid random access to the sensing matrix. To address the high computational complexity, we proposed a multi-core design with 19 cores to provide a parallelism of up to 256. Additionally, each core can be disabled to reduce the power further. We also proposed a specifically designed randomly positioned stripe-based matrix to boost the speed further. Subsequently, we developed an efficient Cholesky-factorization-based linear algebra engine. A carefully designed data flow, efficient buffering mechanism, and in-place matrix updating technique were proposed.
The proposed sparse reconstruction platform achieved 128.7 fps for the vehicle tracking application and 28.1 fps for the surveillance video reconstruction task, with a power of 242.4 mW. Thus, the real-time, low-power, and versatility requirements were satisfied.
Subjects
Sparse reconstruction
Warm start
Compressed sensing
Sparse representation
Multi-core design
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-101-R99943034-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):844c35ba2c2c1185aa8354123b91ddeb