Sparse signal recovery with additional l2 null space constraint
Nicolae Cleju
International Symposium on Signals, Circuits & Systems - ISSCS 2015
Download
Abstract
This paper studies a relaxed version of the analysis sparsity model, in which the signal produces an output vector that is not rigorously sparse itself, instead it is within a $\ell_2$ distance from a sparse vector. Conversely, this can also be viewed as a synthesis model with the additional requirement that the sparse decomposition has only a limited component in the dictionary's null space. We show that if this $\ell_2$ constraint is sufficiently tight, a sparse signal can be recovered via $\ell_0$ minimization if the Restricted Isometry constant of the system matrix satisfies $\delta_{2k-1} < 1$, which is an improvement over the $\delta_{2k} < 1$ condition used in the usual synthesis sparse model. In practical simulations, the mixture of sparsity and $\ell_2$ constraints leads to reduced recovery errors when sparsity alone is not enough.
Optimized projections for compressed sensing via rank-constrained nearest correlation matrix
Nicolae Cleju, Applied and Computational Harmonic Analysis, vol. 36, no. 3, pp. 495-507, 2014
Abstract
Optimizing the acquisition matrix is useful for compressed sensing of signals that are sparse in overcomplete dictionaries, because the acquisition matrix can be adapted to the particular correlations of the dictionary atoms. In this paper a novel formulation of the optimization problem is proposed, in the form of a rank-constrained nearest correlation matrix problem. Furthermore, improvements for three existing optimization algorithms are introduced, which are shown to be particular instances of the proposed formulation. Simulation results show notable improvements and superior robustness in sparse signal recovery.
Download
Code (Matlab):
- The code without dependencies. Dependencies (not full packages, only the files actually used). Beware, it takes days to run completely!
- Download the dictionary of image patches dictionary already trained with K-SVD for test1. This saves about 1 day of running K-SVD. Save in the "data" folder. Disable the call to create_dict_patches() on line 9 of test1_learneddict.m since we already have it.
A generalization of analysis and synthesis sparsity
Nicolae Cleju, International Symposium on Signals, Circuits & Systems - ISSCS2013
Download
[Paper (.pdf)] [Code(Python)] [Presentation (.pdf)]
Abstract
This paper introduces a generalized sparsity model that extends synthesis and analysis sparsity.
The generalized model asserts that a signal has a sparse representation in a dictionary, which is at the same time orthogonal to a part of the dictionary's null space. Alternatively, analyzing the signal with an analysis operator yields an output vector that can be represented as the sum between a sparse vector and a vector from a low-dimensional subspace. We show that the proposed model allows recovery of sparse signals from few incoherent measurements, with algorithms that are similar to the familiar algorithms of the synthesis and analysis sparsity models.
Contributions to signal analysis and processing using compressed sensing techniques
PhD Thesis, Tech. Univ. Iasi, 2012
Download
[Thesis (.pdf)] [Resume (.pdf)] [Rezumat scurt (.pdf), rom.] [Presentation (.pdf)]
Selection of Network Coding Nodes for Minimal Playback Delay in Streaming Overlays
N. Cleju, N. Thomos and P. Frossard, IEEE Transactions on Multimedia, vol. 13, no. 5, p. 1103-1115, 2011
Download
Code:
-
Algorithms:
- Matlab code (original used for paper)
- Python code on GitHub (later translation to Python, bugfixed, maybe not as fully tested)
- Validation:
- Explanatory help file
Abstract
Network coding permits to deploy distributed packet delivery algorithms that locally adapt to the network availability in media streaming applications. However, it may also increase delay and computational complexity if it is not implemented efficiently. We address here the effective placement of a limited number of nodes that implement randomized network coding in overlay networks, so that the goodput is kept high while the delay for decoding stays small in streaming applications. We first estimate the decoding delay at each client, which depends on the innovative rate in the network. This estimation permits to identify the nodes that have to perform coding in order to reduce the decoding delay. We then propose two iterative algorithms for selecting the nodes that should perform network coding. The first algorithm relies on the knowledge of the full network statistics. The second algorithm uses only local network statistics at each node. Simulation results show that large performance gains can be achieved with the selection of only a few network coding nodes. Moreover, the second algorithm performs very closely to the central estimation strategy, which demonstrates that the network coding nodes can be selected efficiently with help of a distributed innovative flow rate estimation solution. Our solution provides large gains in terms of throughput, delay, and video quality in realistic overlay networks when compared to methods that employ traditional streaming strategies as well as random network coding nodes selection algorithms.