Signal processing

Sparse recovery

We developed two new heuristics (called LiMapS and $k$-LiMapS respectively) for the classical sparse recovery problem \[ \min_{\alpha} || \alpha ||_{0} \quad \mbox{such that}\quad s=\Phi\alpha.\] They rely on a parametric class $\left\{G_\lambda : \lambda \geq 0 \right\}$ of nonlinear mappings which turn to be useful to solve the sparsity minimization of the above problem by the Picard iterative scheme: \begin{equation} \alpha_{t+1} = G_{\lambda_t}(\alpha_{t}) \end{equation} We show that for a given sequence $\{\lambda_t\}_{t\geq 0}$, the iterative scheme converges when $\sum_{t} \frac{1}{\lambda_t}<+\infty$. To study such a minimization problem, it is first relaxed to a smooth version corresponding to the original as $\lambda\to+\infty$: \begin{equation} \min_{\alpha} || \alpha ||_{\langle \lambda \rangle} \quad \mbox{such that}\quad s=\Phi\alpha \end{equation} where the family $\{ || \cdot ||_{\langle\lambda \rangle}:\lambda >0\}$ is a collection of suitable quasi-norms. We find that, under reasonable assumptions, the local minima of the relaxed problem are asymptotically stable fixed points of $G_\lambda$. It is also proved that, for sufficiently large $\lambda$, the sparsest solution is ''very close'' to a fixed point of $G_\lambda$.

Real-time ICA

We explore information redundancy of linearly mixed sources in order to accomplish the demixing task (BSS) by ICA techniques in real-time. Assuming piecewise stationarity of the sources, the idea is to prune uniformly and independently most of sample data while preserving the ability of Kurtosis-based algorithms to reconstruct the original sources using pruned mixtures instead of original ones. The mainstay of this method is to control the sub-mixtures size so that the Kurtosis is sharply concentrated about that of the entire mixtures with exponentially small error probabilities. Referring to the FastICA algorithm, it is shown that the dimensionality reduction proposed while assuring high quality of the source estimate yields to a significant reduction of the demixing time. In particular, it is experimentally shown that, in case of online applications, the pruning of blockwise stationary data is not only essential for guarantying the time-constraints keeping, but it is also effective.

The following Figures report (in log-scale) the average performance index and computation times over 100 executions of FastICA and P-FastICA algorithms. The pruning parameters vary in the range [0.05,0.1] for ε and [0.1,0.2] for δ.

Performances Times

Next two Figures show the average performance index and the computation times over 100 executions of FastICA and P-FastICA algorithms. The pruning parameters used here also vary in the range [0.05,0.1] for ε and [0.1,0.2] for δ. Observe that, even if our hw/sw architecture is not a real-time oriented apparatus, the performance index of the two algorithms are comparable while the computation time of the more pruned mixtures are under the unitary computation time.

Performances Times

Architecture Design

Neural Hw

Under this topic we propose FPGA implementations of novel neural stochastic models for solving constrained NP-hard problems. The models exploits pseudo-Boolean functions both to express the constraints and to define the cost function, interpreted as energy of a neural network. A wide variety of NP-hard problems fall in the class of problems that can be solved by this models, particularly those having a quadratic pseudo-Boolean penalty function. The hardware implementation allows to obtain high computation speed by exploiting parallelism, as the neuron update and the constraint violation check can be performed in parallel over the whole network. The neural system has been tested on random and benchmark graphs, showing good performance, with respect to the same heuristic for the same problems. Furthermore, the computational speed of the FPGA implementation has been measured and compared to software implementation. The developed architecture featured dramatically faster computation, with respect to the software implementation, even adopting a low-cost FPGA chip.


In figure the block diagram of the proposed architecture. The Adjacency Matrix A and the threshold α are provided as input, prior to algorithm execution.

Sensor Networks

Sensori wireless della Moteiv Corporation (Tmote SKY)

Tmote sky is the latest wireless sensor module from Moteiv Corporation. Based on the Telos Revision B design, Tmote sky enables extremely low power, high data-rate, sensor network applications designed with the dual goal of fault tolerance and development ease. Featuring hardware write protection, the industry's lowest power consumption, integrated antenna, and 10kB of RAM for data processing, Tmote sky is a robust, powerful module that meets the needs of long-lived applications.