M.Sc Thesis

M.Sc StudentGleichman Sivan
SubjectBlind Compressed Sensing
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROFESSOR EMERITUS David Malah


In many different application areas, such as imaging systems and data communication, we wish to reconstruct a discrete signal from a given set of linear measurements. A general signal can be uniquely determined by its measurements only if the number of measurements is not smaller then the ambient dimension. The use of prior knowledge can allow reduction in the number of measurements needed for perfect recovery. This is the concept behind the field of compressed sensing which has gained growing popularity in recent years. In compressed sensing the signal is assumed to be sparse. Roughly speaking, the information content of a sparse signal occupies only a small portion of its ambient dimension. For example, sparse vectors are those having only a small number of nonzero entries, or alternatively a vector is sparse under a basis if its representation under the basis transform is sparse. Compressed sensing exploits the sparsity of the signal and offers a linear measurement approach in which a high dimensional vector is represented by a small number of measurements. However, prior knowledge of the sparsity basis is essential for the recovery process. This work introduces the concept of blind compressed sensing, which avoids the need to know the sparsity basis in both the sampling and the recovery process. We suggest three possible constraints on the sparsity basis that can be added to the problem in order to make its solution unique. For each constraint we prove conditions for uniqueness, and suggest a simple method to retrieve the solution. Under the uniqueness conditions, and as long as the signals are sparse enough, we demonstrate through simulations that without knowing the sparsity basis our methods can achieve results similar to those of standard compressed sensing, which rely on prior knowledge of the sparsity basis. This offers a general sampling and reconstruction system that fits all sparse signals, regardless of the sparsity basis, under the conditions and constraints presented in this work.