Iterative Hard Thresholding

                      

•    Algorithm

 

Instead of needing to solve a least square problem like OMP, iterative hard thresholding (IHT) employs a thresholding approach where only the k largest elements of the approximation are maintained and all of the other elements are set to zero. This small change allows for a compact representation of the core algorithm as 

 

 

 

 

 

 

 

 

 

Where B is composed by the product between the sensing matrix and the basis where the signal is sparse, a is the approximation and y is the measurement vector. The operator Hk is the one responsible for the thresholding. 

 

While this algorithm may take more iterations to recover the signal, and the sensing matrix must have a norm lower than 1 to ensure convergence, it was shown that IHT can recover approximately sparse vectors with near optimal accuracy.

 

•    Architecture

 

To implement the algorithm in hardware, the flow must be broken down into steps that will then be mapped into separate blocks.

 

In the development of the architecture, some considerations were taken:

• Since the target signal will be images, the chosen sparsity basis was the 2D-DCT;

• To prevent the normalization of the sensing matrix two times per-iteration, it will be done after the multiplication by the transposed B matrix using the squared normalization coefficient.  

 

As a result, the block architecture of one IHT processor is presented in the next diagram. Of note is the fact that two different matrix-vector approches will be taken: one for the data from the 2D-DCT operation and another before the 2D-IDCT.