Comparative Analysis of Sparse Signal Reconstruction Algorithms for Compressed Sensing

Published in: Innovation in Engineering, Technology and Education for Competitiveness and Prosperity: Proceedings of the 12th Latin American and Caribbean Conference for Engineering and Technology
Date of Conference: July 21-24,2014
Location of Conference: Guayaquil,Ecuador
Authors: Maytee Zambrano
Fernando Arias
Carlos Medina
Refereed Paper: #134

Abstract:

Compressed sensing (CS) is a rapidly growing field, attracting considerable attention in many areas from imaging to communication and control systems. This signal processing framework is based on the reconstruction of signals, which are sparse in some domain, from a very small data collection of linear projections of the signal. The solution to the underdetermined linear system, resulting from these data, allows us to estimate the original signal. Finding the solution is an optimization problem which is mainly based on the minimization of the l1-norm. For this purpose, fast algorithms have been developed, and the aim of this paper is to make a comparative analysis of some of these algorithms. Specifically, we study the performance of sparse reconstructions with five commonly used algorithms implemented in Matlab (CVX, L1magic, SPGL1, UnlocBoX and YALL1) in order to determine the viability of implementation of a large number of applications proposed in the last years using CS. The objective is to offer a reference analysis for algorithm selection in CS applications and also provide a methodology for algorithm analysis in sparse reconstruction. Consequently, in order to determine each algorithm’s effectiveness and being able to compare them in a standardized manner, three indicators are considered: execution time, percent error and CPU usage, being the first two indicators crucial to any application involving compressed sensing. In addition some general basic concepts on compressed sensing are included.

Resumen:

La detección con datos dispersos (CS - compressed sensing) es un campo de rápido crecimiento, que atrae considerable atención en muchas áreas, desde la producción de imágenes hasta sistemas de comunicación y control. Esta técnica de procesamiento de señales está basada en la reconstrucción de señales, que tienen una representación dispersa en algún dominio, a partir de una cantidad muy pequeña de datos correspondientes a proyecciones lineales de la señal. La solución al sistema lineal subdeterminado, resultante de los datos, permite estimar la señal original. Encontrar la solución es un problema de optimización basado principalmente en la minimización de la norma l1. Para este propósito, se han desarrollado algoritmos rápidos, y el propósito de este trabajo es realizar un análisis comparativo de algunos de estos algoritmos. Específicamente, se estudia el desempeño de reconstrucciones con datos dispersos con cinco algoritmos comúnmente utilizados implementados en Matlab (CVX, L1magic, SPGL1, UnlocBoX y YALL1), con el fin de determinar la viabilidad de la implementación de una gran cantidad de aplicaciones propuestas en los últimos años usando CS. El objetivo es ofrecer un análisis de referencia para la selección de algoritmos en aplicaciones de CS y también proveer una metodología para el análisis de algoritmos para reconstrucciones con datos dispersos. Por consiguiente, para determinar la eficacia de cada algoritmo y poder compararlos de manera estandarizada, se consideran tres indicadores: tiempo de ejecución, porcentaje de error y uso del CPU, siendo los dos primeros indicadores cruciales para cualquier aplicación de detección con datos dispersos. Además, se han incluido algunos conceptos básicos generales sobre detección con datos dispersos.