TY - GEN
T1 - Kernel reconstruction
T2 - 2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
AU - Bayar, Beihassen
AU - Bouaynaya, Nidhal
AU - Shterenberg, Roman
PY - 2014/2/5
Y1 - 2014/2/5
N2 - Compressive sensing is the theory of sparse signal recovery from undersampled measurements or observations. Exact signal reconstruction is an NP hard problem. A convex approximation using the l1-norm has received a great deal of theoretical attention. Exact recovery using the l1 approximation is only possible under strict conditions on the measurement matrix, which are difficult to check. Many greedy algorithms have thus been proposed. However, none of them is guaranteed to lead to the optimal (sparsest) solution. In this paper, we present a new greedy algorithm that provides an exact sparse solution of the problem. Unlike other greedy approaches, which are only approximations of the exact sparse solution, the proposed greedy approach, called Kernel Reconstruction, leads to the exact optimal solution in less operations than the original combinatorial problem. An application to the recovery of sparse gene regulatory networks is presented.
AB - Compressive sensing is the theory of sparse signal recovery from undersampled measurements or observations. Exact signal reconstruction is an NP hard problem. A convex approximation using the l1-norm has received a great deal of theoretical attention. Exact recovery using the l1 approximation is only possible under strict conditions on the measurement matrix, which are difficult to check. Many greedy algorithms have thus been proposed. However, none of them is guaranteed to lead to the optimal (sparsest) solution. In this paper, we present a new greedy algorithm that provides an exact sparse solution of the problem. Unlike other greedy approaches, which are only approximations of the exact sparse solution, the proposed greedy approach, called Kernel Reconstruction, leads to the exact optimal solution in less operations than the original combinatorial problem. An application to the recovery of sparse gene regulatory networks is presented.
UR - http://www.scopus.com/inward/record.url?scp=84983205991&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84983205991&partnerID=8YFLogxK
U2 - 10.1109/GlobalSIP.2014.7032355
DO - 10.1109/GlobalSIP.2014.7032355
M3 - Conference contribution
AN - SCOPUS:84983205991
T3 - 2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
SP - 1390
EP - 1393
BT - 2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 3 December 2014 through 5 December 2014
ER -