A Recovery Guarantee for Sparse Neural Networks
We prove the first guarantees of sparse recovery for ReLU neural networks, where the sparse network weights constitute the signal to be recovered. Specifically, we study structural properties of the sparse network weights for two-layer, scalar-output networks under which a simple iterative hard thresholding algorithm recovers these weights exactly, using memory that grows linearly in the number of nonzero weights. We validate this theoretical result with simple experiments on recovery of sparse planted MLPs, MNIST classification, and implicit neural representations. Experimentally, we find performance that is competitive with, and often exceeds, a high-performing but memory-inefficient baseline based on iterative magnitude pruning. Code is available at https://github.com/voilalab/MLP-IHT.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Analysis of Orthogonal Matching Pursuit for Compressed Sensing in Practical Settings
Orthogonal matching pursuit (OMP) is a widely used greedy algorithm for sparse signal recovery in compressed sensing (CS). Prior work on OMP, however, has only provided reconstruction guarantees under the assumption that…
compressed sensingA divide-and-conquer approach for sparse recovery of high dimensional signals
Compressed sensing (CS) techniques demand significant storage and computational resources, when recovering high-dimensional sparse signals. Block CS (BCS), a special class of CS, addresses both the storage and complexity…
compressed sensingSparse Representation of a Polytope and Recovery of Sparse Signals and Low-rank Matrices
This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis rel…
compressed sensingTwo step recovery of jointly sparse and low-rank matrices: theoretical guarantees
We introduce a two step algorithm with theoretical guarantees to recover a jointly sparse and low-rank matrix from undersampled measurements of its columns. The algorithm first estimates the row subspace of the matrix us…
Sparse recovery via Orthogonal Least-Squares under presence of Noise
We consider the Orthogonal Least-Squares (OLS) algorithm for the recovery of a $m$-dimensional $k$-sparse signal from a low number of noisy linear measurements. The Exact Recovery Condition (ERC) in bounded noisy scenari…