# Achievements

A list of project achievements obtained so far can be explored. The list is divided into areas corresponding to the project's workpackages and each area is further divided into activities, described with a short abstract and accompanied by a list of related papers. A short video presentation of each area's achievements is also provided right below.

*This page is updated to June, 13, 2014. For an up-to-date full list of project-related publications, refer to the Publications page.*

### Processing and analysis

Distributed Reconstruction

This activity focuses on the minimization of a nonlinear function which is a combination of local agent objective functions. Our main focus is on constrained problems where the unknown is sparse, i.e., only few degrees of freedom compared to their ambient dimension are significant. In-network optimization calls for more efficient algorithms, which are able to reduce the number of required communications, computations, and memory. To this end, we study distributed algorithms, that just require local, asynchronous communications. Based on consensus techniques and iterative hard thresholding methods, our algorithms attempt to minimize the given nonlinear function, promoting sparsity of the solution. We suggest and analyze different kind of sensor communication protocols, and we provide theoretical results about convergence and characterization of the fixed points. We also illustrate the use of the proposed technique

in different applications, and present several numerical results.

*Related papers:*

- Ravazzi, C., Fosson, S.M., Magli, E.,
**Energy-saving Gossip Algorithm for Compressed Sensing in Multi-agent Systems**,*39th International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, Firenze, Italy, May 4-9, 2014 - Fosson, S.M., Matamoros, J., Antón-Haro, C., Magli, E.,
**Distributed Support Detection of Jointly Sparse Signals**,*39th International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, Firenze, Italy, May 4-9, 2014 - Ravazzi, C. Fosson S.M., Magli, E.
**Distributed soft thresholding for sparse signal recovery**,*IEEE GLOBECOM 2013*December 9-13, Atlanta, Georgia, USA**,**

Joint Recovery Algorithms for Distributed Compressed Sensing

Distributed compressed sensing is concerned with representing an ensemble of jointly sparse signals using as few linear measurements as possible. Two novel joint reconstruction algorithms for distributed compressed sensing are developed in this work. These algorithms are based on the idea of using one of the signals as side information; this allows to exploit joint sparsity in a more effective way with respect to existing schemes. They provide gains in reconstruction quality, especially when the nodes acquire few measurements, so that the system is able to operate with fewer measurements than is required by other existing schemes. We show that the algorithms achieve better performance with respect to the state-of-the-art.

*Related papers:*

- Valsesia, D., Coluccia, G., Magli, E.
**Joint recovery algorithms using difference of innovations for distributed compressed sensing**,*Conference Record of the Forty Seventh Asilomar Conference on Signals, Systems and Computers (ASILOMAR)*, 2013

Parameter Estimation

The parameter estimation in the compressed domain represents an efficient way to extract data without the burden of the reconstruction. The research on this topic, at the first stage, focused on some simple maximum-likelihood estimators applied to compressed signals in order assess the performances of such parameter estimation. The results showed that the compressed measurements are indeed containing enough information that can be directly extracted by using ad-hoc estimators. Motivated by these results, the focus moved on the parametric autoregressive processes (AR). This work then leaded to the development of an estimator for AR processes in the compressed domain and a distributed algorithm able to estimate the covariance matrix of such a process corrupting compressed sensing data.

Compressive-domain signal processing with circulant matrices

Compressive sensing achieves effective dimensionality reduction of signals, under a sparsity constraint, by means of a small number of random measurements acquired through a sensing matrix. In a signal processing system, the problem arises of processing the random projections directly, without first reconstructing the signal. We show that circulant sensing matrices allow to perform a variety of classical signal processing tasks such as filtering, interpolation, registration, transforms, and so forth, directly in the compressed domain and in an exact fashion, i.e., without relying on estimators as proposed in the existing literature. The advantage of the techniques presented in this paper is to enable direct measurement-to-measurement transformations, without the need of costly recovery procedures.

*Related papers:*

- Valsesia, D., Magli, E.,
**Compressive Signal Processing with Circulant Sensing Matrices**,*39th International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, Firenze, Italy, May 4-9, 2014

### Communications

Rate-Distortion Analysis of Compressed Sensing

This research activity focuses on the reconstruction performances of CS algorithms. We first analyze the baseline oracle receiver, knowing perfectly the sparsity pattern of the signal, and derive the closed-form expression of the mean square error performance for this kind of receivers. With respect to existing bounds, our result is exact and does not depend on a particular realization of the sensing matrix. Moreover, our result holds irrespective of whether the noise affecting the measurements is white or correlated. Ongoing activity focuses then on the performance of this kind of receivers, but with a mismatch between the estimated and true sparsity supports.

Moving to a distributed scenario, we consider correlated and distributed sources without cooperation at the encoder. For these sources, we derive the best achievable performance in the rate-distortion sense of any distributed compressed sensing scheme, under the constraint of high-rate quantization. Moreover, under this model we derive a closed-form expression of the rate gain achieved by taking into account the correlation of the sources at the receiver and a closed-form expression of the average performance of the oracle receiver for joint reconstruction. Even if the derivation is performed in the large system regime, where signal and system parameters tend to infinity, numerical results show that the equations match simulations for parameter values of practical interest.

*Related papers:*

- Coluccia, G., Roumy, A., Magli, E.,
**Operational Rate-Distortion Performance of Single-source and Distributed Compressed Sensing**,*to appear in IEEE Transactions on Communications*, 2014 - Coluccia, G., Roumy, A., Magli, E.,
**Exact Performance Analysis of the Oracle Receiver for Compressed Sensing Reconstruction**,*39th International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, Firenze, Italy, May 4-9, 2014

Multiple Description Coding using Compressed Sensing

The low complexity of compressed sensing (CS) is appealing for resource-constrained scenarios like sensor networks. However, such scenarios are often coupled with unreliable communication channels and providing robust transmission of the acquired data to a receiver is an issue. Multiple description coding (MDC) effectively combats channel losses for systems without feedback, thus raising the interest in developing MDC methods explicitly designed for the CS framework, and exploiting its properties. We propose a method called Graded Quantization (CS-GQ) that leverages the democratic property of compressive measurements to effectively implement MDC, and we provide methods to optimize its performance. A novel decoding algorithm based on the alternating directions method of multipliers is derived to reconstruct signals from a limited number of received descriptions. Simulations are performed to assess the performance of CS-GQ against other methods in presence of packet losses. The proposed method is successful at providing robust coding of CS measurements and outperforms other schemes for the considered test metrics.

*Related papers:*

- Valsesia, D, Coluccia, G., Magli, E.
**Graded Quantization: Democracy for Multiple Descriptions in Compressed Sensing**,*38th International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, Vancouver, Canada, May 26 - 31, 2013, pp. 5825-5829

Spatially Scalable Compressed Image Sensing

Compressive imaging is an emerging application of compressed sensing, devoted to acquisition, encoding and reconstruction of images using random projections as measurements.

In this work we propose a novel method to provide a scalable encoding of an image acquired by means of compressed sensing techniques. Two bit-streams are generated to provide two distinct quality levels: a low-resolution base layer and full-resolution enhancement layer. In the proposed method we exploit a fast preview of the image at the encoder in order to perform inter-layer prediction and encode the prediction residuals only. The proposed method successfully provides resolution and quality scalability with modest complexity and it provides gains in the quality of the reconstructed images with respect to separate encoding of the quality layers. Remarkably, we also show that the scheme can also provide significant gains with respect to a direct, non-scalable system, thus accomplishing two features at once: scalability and improved reconstruction performance.

*Related papers:*

- Valsesia, D., Magli, E.
**Spatially Scalable Compressed Image Sensing with Hybrid Transform and Inter-layer Prediction Model**,*15th International Workshop on Multimedia Signal Processing*, September 30-October 3, 2013, Pula, Italy, pp. 373-378

### Security

CS cryptosystems

This research activity has regarded the analysis of the security of the compressed sensing (CS) framework as a form of data confidentiality. Two important properties of random linear measurements were outlined: i) measurements acquired using a Gaussian i.i.d. matrix reveal only the energy of the sensed signal; ii) only the energy of the measurements leaks information about the energy of the signal. An important consequence of the above facts is that CS may provide information theoretic secrecy in particular scenarios. Namely, a simple strategy based on the normalization of Gaussian measurements achieves, at least in theory, perfect secrecy, enabling the use of CS as an additional security layer in practical cryptosystems. In the generic scenario in which CS does not provide information theoretic secrecy, we introduced an alternative security notion linked to the difficulty of estimating the energy of the signal. Useful bounds on the mean square error of any possible estimator were provided and compared to simulations. The results indicated that CS is in general not secure according to cryptographic standards, but may provide a data obfuscation layer similar to that of perceptual encryption.

*Related papers:*

- Bianchi, T., Bioglio, V., Magli, E.,
**On the Security of Random Linear Measurements**,*39th International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, Firenze, Italy, May 4-9, 2014

### Optimal reconstruction of rich media

Compressed sensing and reconstruction for Multidimensional Signals

Compressed Sensing can be thought of as a natural candidate for acquisition of multidimensional signals, as the amount of data acquired and processed by conventional sensors could create problems in terms of computational complexity. In this research activity, we propose a framework for the acquisition and reconstruction of multidimensional correlated signals. The approach is general and can be applied to D dimensional signals, even if the algorithms we propose to practically implement such architectures apply to 2D and 3D signals, images and hyperspectral images, respectively. The proposed architectures employ iterative local signal reconstruction based on a hybrid transform/prediction correlation model, coupled with a proper initialization strategy. For what concerns hyperspectral images, the proposed technique is specifically tailored to onboard acquisition devices, with the final purpose to design and build a compressive hyperspectral sensor, where random projections are directly acquired by the hardware.

*Related papers:*

- Kamdem Kuiteing, S., Coluccia, G., Barducci, A., Barni, M., Magli, E.,
**Compressive Hyperspectral Imaging Using Progressive Total Variation**,*39th International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, Firenze, Italy, May 4-9, 2014 - Coluccia, G., Kuiteing, S. K., Abrardo, A., Barni, M., Magli, E.
**Progressive compressed sensing and reconstruction of multidimensional signals using hybrid transform/prediction sparsity model**.*IEEE Journal on emerging and Selected Topics in Circuits and Systems*, 2(3), 340-352. - Coluccia, G., Magli, E.
**A Novel Progressive Image Scanning and Reconstruction Scheme Based on Compressed Sensing and Linear Prediction**.*In 2012 IEEE International Conference on Multimedia and Expo (ICME)*, (pp. 866-871). IEEE.

Block-Based image reconstruction from random projections

This research activity addresses the problem of visual quality of images reconstructed from block-wise random projections. Independent reconstruction of the blocks can severely affect visual quality, by displaying artifacts along block borders. We propose a method to enforce smoothness across block borders by modifying the sensing and reconstruction process so as to employ partially overlapping blocks. The proposed algorithm accomplishes this by computing a fast preview from the blocks, whose purpose is twofold. On one hand, it allows to enforce a

set of constraints to drive the reconstruction algorithm towards a smooth solution, imposing the similarity of block borders. On the other hand, the preview is used as a predictor of the entire block, allowing to recover the prediction error, only. The quality improvement over the result of independent reconstruction can be easily assessed both visually and in terms of PSNR and SSIM index.

*Related papers:*

- Coluccia, G., Valsesia, D., Magli, E.
**Smoothness-Constrained Image Recovery from Block-Based Random Projections**,*15th International Workshop on Multimedia Signal Processing*, September 30-October 3, 2013, Pula, Italy, pp. 129-134

Gaussian Mixtures

In this activity we design a new class of iterative re-weighted least squares (IRLS) algorithms for sparse recovery problems. The proposed methods are inspired by constrained maximum likelihood estimation under a Gaussian scale mixture (GSM) distribution assumption. We provide sufficient conditions ensuring the convergence of the sequences generated by these algorithms to the fixed points of the maps that rule their dynamics. We further prove the quadratic convergence of these algorithms in a neighborhood of the solution and show through numerical experiments that the proposed methods outperform classical IRLS for ℓ_𝜏-minimization with 𝜏∈(0,1] in terms of speed and of sparsity-undersampling tradeoff.

Compressed Sensing over Finite Fields

The use in CS of techniques derived from linear codes is emerging as promising since it can provide some advantages over the classical CS. However, the works present in literature exploit real field measurements, while the study of CS over finite fields has been left aside. Namely, while sensing and measurement quantization of a real signals may cause loss of accuracy, performing operations over finite fields avoids this issue, and linear codes techniques can be exploited for efficient signal recovery. Moreover, recent papers hint that the knowledge that a signal belongs to a finite alphabet should be exploited in the reconstruction process. While it seems obvious that such knowledge should be useful, the actual CS reconstruction algorithms are unable to exploit this information. We propose an algorithm for signals defined over finite fields able to exploit the finite nature of the alphabet to improve the recovery performance.

*Related papers:*

- Bioglio, V., Coluccia, G., Magli, E.,
**Sparse Image Recovery Using Compressed Sensing Over Finite Alphabets**, IEEE International Conference on Image Processing (ICIP) 2014, Paris, France, October 27-30, 2014

### Testbed

Compressive Camera

In this activity the single pixel camera has been reproduced based on a liquid crystal spatial light modulator for the sensing pattern. A parallel compressive imaging architecture has also been designed, which avoids the sequential sensing process of the single pixel camera, which causes long acquisition times. This novel architecture uses fewer detectors than the number of reconstructed pixels and is able to acquire the image in a single acquisition. This paves the way for the development of video architectures that acquire several frames per second. Specifically the diffraction problem is addressed, showing that deconvolution normally used to recover diffraction blur can be replaced by convolution of the sensing matrix, and how measurements of a 0/1 physical sensing matrix can be converted to -1/1 compressive sensing matrix without any extra acquisitions. Simulations of the architecture show that the image quality is comparable to that of a classic Compressive Imaging camera, whereas the proposed architecture avoids long acquisition times due to sequential sensing. This one-shot procedure also allows to employ a fixed sensing matrix instead of a complex device such as a Digital Micro Mirror array or Spatial Light Modulator. It also enables imaging at bandwidths where these are not efficient. A low resolution version of the parallel architecture has also successfully been built on the optics test bed.

*Related papers:*

- Björklund, T., Magli, E. A
**Parallel Compressive Imaging Architecture for One-Shot Acquisition**,*30th Picture Coding Symposium*, December 8-11, San Jose, California, USA

Localization

This research activity focuses on the localization problem in an indoor environment using wireless sensors networks. We propose an accurate RSS-based indoor positioning system using the theory of sparse representations, which is a method to recover sparse signals from a small number of noisy measurements. In particular, we design efficient algorithms based on fingerprinting methods and exploiting the block-coherence measure of the signature map. The proposed algorithms are practical and experimental evaluation with real data shows that they outperform traditional fingerprinting methods in terms of the achieved positioning accuracy.

*Related papers:*

- Bay, A., Fragneto,P., Grella, M., Fosson, S.M., Ravazzi, C., Magli, E.
**Sparsity-based Indoor Localization in Wireless Sensor Networks**, Demo Session at*15th International Workshop on Multimedia Signal Processing*, September 30-October 3, 2013, Pula, Italy

CS implementation on GPUs

Compressive sensing enables lightweight acquisition of sparse signals by lifting the computational complexity at the receiver, which is left with the burden of recovering the signal.

The time required to recover the signal increases with the number of signal samples, hence it is of pivotal importance to reduce the time required to recover the signal when the number of samples in the signal is particularly large, as for images. We exploit the computational capabilities of modern Graphical Processing Units (GPUs) by designing a parallel Iterative Soft Threshold-based algorithm, which is by nature inherently parallelizable and hence suitable for GPU-based implementations. Experimental evidence shows that our algorithm slashes the signal recovery time with respect to a serial implementation, plus it suggest that further gains can be achieved if the algorithm is redesigned accounting for the hardware characteristics of GPUs.

*Related papers:*

- Fiandrotti, A, Fosson S.M., Ravazzi C., Magli E.
**PISTA: Parallel Iterative Soft Thresholding Algorithm for Sparse Image Recovery**,*30th Picture Coding Symposium*, December 8-11, San Jose, California, USA