A compressed sensing (CS) recognition algorithm for sonar image based on non-negative matrix factorization and adjacency spectra (A-NMF) feature extraction is proposed in this paper. The feature vector of the tradition CS recognition algorithm is random Gaussian matrix, which causes the identification rate unstable. The stable feature vector which is extracted by the A-NMF feature extraction is used in this algorithm. The feature and structure of the original data can be expressed more accurately by this feature vector. Then the sonar images are classified under the compressed sensing framework. Experimental results show that the sonar image recognition is high, efficient and stable.