The fundamental principle underlying compressed sensing is that a signal, which is sparse under some basis representation, can be recovered from a small number of linear measurements. However, prior knowledge of the sparsity basis is essential for the recovery process. Blind compressed sensing (BCS) avoids the need to know the sparsity basis in both the sampling and the recovery process. That is, BCS aims at recovering an ensemble of vectors, all sparse under the same unknown basis, given small number of linear measurements of these vectors.

If the columns of the m x N matrix X are the desired vectors, then the measurements are the columns of B=AX, where A is a known n x m measurement matrix. That is, the BCS problem can be formulated as follows:

Given the measurements B and the measurement matrix A find the signal matrix X such that B = AX where X = PS for some basis P and a k-sparse matrix S.

In order to achieve uniqueness of the solution to this BCS problem a constraint on the sparsity basis P is required. Several such constraints are possible. In the reference below we explore 3 options:
1) P is one of a finite and known set of bases.

2) P is sparse under some known dictionary.

3) P is orthogonal and has a block diagonal structure.

We now focus on the third constraint, in which P is orthogonal and block diagonal. The orthogonal block diagonal BCS (OBD-BCS) algorithm solves the BCS problem under this constraint, and under the assumption that the measurement matrix is a union of L orthogonal bases, so that

Where M>1 is an integer, and A₁,…,A_L and P¹,…,P^ML are all orthogonal.

The OBD-BCS algorithm finds X = PS by computing a basis P and a sparse matrix S using two alternating steps. The first step is sparse coding, in which P is fixed and S is updated using a standard CS algorithm. In the second step S is fixed and P is updated using several singular value decompositions (SVD).

Conditions for the uniqueness of this constrained problem and for the convergence of this algorithm are discussed in the reference below.

Illustration of the matrices structure for M=2 and L=2.

There are two versions of the OBD-BCS algorithm. The first version assumes that the maximal number of nonzero elements in the columns of S is known, and that these elements can be anywhere along the columns of S. The second version divides S into sub-matrices corresponding to the blocks of P, and assumes the maximal number of nonzero elements in each sub-matrix is known.

• S. Gleichman and Y. C. Eldar, "Blind Compressed Sensing", IEEE Trans. on Information Theory, vol. 57, issue 10, pp. 6958-6975, Oct. 2011.

• The OBD-BCS implementation uses the OMP package, implemented by Ron Rubinstein (computer science department Technion), which can be downloaded from here.
• Download OBD-BCS Matlab implementation. Version 1.1 February, 2010.

Software & Hardware:   SoftwareHardwareDemo movies