Estimation of sparse distributions

A vector is called sparse when most of its components are zero. Many natural signals admit sparse representations with respect to some bases. This dissertation deals with the problem of recovering a sparse signal from a small number of measurements formed by computing the inner product of the signal with the rows of a measurement matrix. The task of recovering a sparse signal from its small number of measurements is a problem of finding the sparsest solution of a underdetermined system of linear equations. The problem can be solved by using a l0 norm based optimization problem which is NP-hard in general. Some recent researches have demonstrated that the NP-hard problem can be solved tractably by using linear programming approach under some reasonable conditions. However, real-world applications often demand more efficient algorithms which are robust to measurement noise. To this aim, an efficient sparse signal recovery algorithm is developed in the first part of the thesis. The proposed algorithm uses a convex-concave procedure to optimize its cost function. A range of theoretical results are presented. The theoretical analysis of the algorithm gives a bound on the run-time estimation error. In many real world problems the resulting sparse signals exhibit additional structures. The proposed algorithm is then extended to exploit the structures of sparse signal. Experimental results demonstrated that in most settings the extended algorithm outperforms other conventional algorithms with a large margin. Finally an interesting sparse signal recovery approach is considered when a part of the support of the sparse signal is known in advance. A maximum a posteriori (MAP) estimation framework is considered to deal with the issue. Second part of the thesis explores the applicability of the proposed algorithms for solving some practical problems. In some cases, the proposed algorithm exhibits additional advantages. For example, in the broadband direction of arrival (DOA) estimation problem, the proposed algorithm allows relaxing the half-wavelength sensor spacing restriction, which leads to a significant performance improvement. In some applications, the proposed algorithm can exploit underlying structure of the linear system. For example, in frequency estimation problem, it is possible to exploit the structure of the Fourier basis to achieve a significant reduction of the computational complexity.