Duke University; Syracuse University
Compressive sensing (CS) has achieved tremendous success in a wide range of applications such as medical imaging, radio detecting and ranging (radar), analog-to-information converters, spectrum sensing in cognitive radio networks, and data gathering for large wireless sensor networks. The theory of CS attempts to perform sampling and compression simultaneously, and under mild conditions, allows to recover a high dimensional sparse signal from low dimensional (noiseless or noisy) observations. When the measurements are noisy, signal recovery from imperfect measurements, also known as robust CS, becomes involved, and requires to solve a special instance of a second-order cone program (SOCP). This leads to a higher computational complexity of O(n3.5). Such high computational complexity significantly limits the applicability of robust compressed sensing for large-scale problems.
By taking advantage of novel hardware devices and computing paradigms, one can potentially accelerate robust CS solvers quite significantly, thus overcoming the fundamental challenges in speed and scalability. In particular, a crossbar array of the newly invented memristor devices (i.e., a memristor crossbar) exhibits a unique type of parallelism that can be utilized to perform matrix-vector multiplication and solve systems of linear equations in an astonishing O(1) time complexity. Furthermore, the memristor crossbar is compatible with CMOS technology, can achieve ultra-high layout density and can be reconfigured for different applications by changing the resistances of memristors. Hence, memristor crossbars can be potentially utilized for solving robust CS problems to achieve substantial acceleration in speed, enhancement in scalability, and reduction in computational complexity and power/energy consumption.
We will develop a memristor crossbar-based solution framework of robust CS problems, including (i) identifying proper algorithm, i.e., the alternating directions method of multipliers (ADMM), to extract subproblems of solving linear system of equations, which could be efficiently solved by memristor crossbar in O(1) complexity, from the solution path of robust CS, (ii) developing memristor crossbar-based solution framework of robust CS problems in the analog domain, and (iii) developing effective techniques to overcome inherent limitations of memristor crossbars, e.g., can only support non-negative coefficients and square matrices when solving a linear system.
Yanzhi Wang (EECS, SU) and Qinru Qiu (EECS, SU) will be responsible for the computing algorithm development and coordination with hardware development. Yiran Chen (ECE, Duke) and Hai Li (ECE, Duke) will be responsible for the device and hardware-level developments.
Experimental Plan and Industrial Relevance
(i) We will develop a memristor crossbar-based solution framework for robust CS problems. (ii) We will develop effective algorithm and hardware-level techniques to properly mitigate the effects of process variations and random noise, deal with important design challenges such as negative values, out-of-range values, and cases where no solution exists, and reduce hardware footprint, power consumption and improve performance. (iii) We will perform evaluations accounting for process variations and noises from algorithms, CMOS circuits, and memristor crossbars.
The proposed research will be of interests to multiple groups of industrial partners, including defense industry, mobile computing, signal processing, data mining, machine learning hardware accelerators.
The first-year deliverables include a memristor crossbar-based solution framework for robust CS problems and corresponding analysis results. The end-of-project deliverables include (i) various algorithm-level and hardware-level techniques to improve reliability, robustness, performance, and energy efficiency, and (ii) an effective evaluation framework.
Milestones and Time-to-Completion
The estimated duration of this project is 3 years. The milestones are listed in the following table.
Develop solution framework
Develop evaluation framework
Improve reliability and robustness
Improve performance and efficiency
Number of Graduate Students Supported
Total Cost to Completion