We consider the task of feature selection for reconstruction which consists\nin choosing a small subset of features from which whole data instances can be\nreconstructed. This is of particular importance in several contexts involving\nfor example costly physical measurements, sensor placement or information\ncompression. To break the intrinsic combinatorial nature of this problem, we\nformulate the task as optimizing a binary mask distribution enabling an\naccurate reconstruction. We then face two main challenges. One concerns\ndifferentiability issues due to the binary distribution. The second one\ncorresponds to the elimination of redundant information by selecting variables\nin a correlated fashion which requires modeling the covariance of the binary\ndistribution. We address both issues by introducing a relaxation of the problem\nvia a novel reparameterization of the logitNormal distribution. We demonstrate\nthat the proposed method provides an effective exploration scheme and leads to\nefficient feature selection for reconstruction through evaluation on several\nhigh dimensional image benchmarks. We show that the method leverages the\nintrinsic geometry of the data, facilitating reconstruction.\n