Analysis of accuracy and complexity of A* search for compressed sensing signal recovery

A* Orthogonal Matching Pursuit (A*OMP) utilizes best-first search for recovery of sparse signals from reduced dimensions. It applies A* search on a tree whose branches are extended similar to Orthogonal Matching Pursuit (OMP). A*OMP makes a tractable tree search possible via effective complexity-accuracy trade-off parameters. Here, we concentrate on the effects of these parameters on the recovery performance. Via empirical comparison of complexity and performance, we demonstrate the effects of the search parameters on search size and recovery. We also compare A*OMP with well-known compressed sensing (CS) recovery techniques to reveal the improvement in the reconstruction.