Before revision:  In this work, we provide tight information-theoretic upper and lower bounds for the recovery problem , as well as the first non-trivial algorithmic bounds based on approximate message passing algorithms.
After revision:  In this work, we provide tight information-theoreticinformation-theoretic upper and lower bounds for the recovery problem , as well as the first non-trivial algorithmic bounds based on approximate message passing algorithms.