Tree search network for sparse estimation

Abstract

We consider the classical sparse estimation problem of recovering a synthetic sparse signal x(0) given measurement vector y = Phi x(0) + w. We propose a tree search algorithm, TSN, driven by a deep neural network for sparse estimation. TSN improves the signal reconstruction performance of the deep neural network designed for sparse estimation by performing a tree search with pruning. In both noiseless and noisy cases, the proposed TSN recovers all synthetic signals at lower complexity than conventional tree search and outperforms existing algorithms by a large margin regarding several variations of sensing matrix Phi, which is widely used in sparse estimation. We also demonstrate the superiority of TSN for two typical applications of sparse estimation.