Here, we present a novel method for data protection to resolve the issue of mass-tampered regions of image watermarks. Our approach involves asymmetric cryptography and follows the nonspatial domain technique, where a codebook exists as a public key and a verification code exists as a private key. There are two major components to our study: self-recovery images and sparse approximation. Specifically, we generate self-recovery images on the basis of our previous research, and to generate verification codes, we mark data with the maximum coefficient resulting from the sparse approximation. The above approach processes 4 x 4 blocks of the given images. The results demonstrate that each block processed by the sparse approximation algorithm has its main texture feature associated with a codeword with a higher sparse coefficient value than the codebook. This provides a robust method to protect data via watermarking and to verify the copyright of the data. Our proposed method efficiently supports compression for transmission via popular communication applications. Using our method under common conditions, we confirmed an outstanding unit correction rate of approximately 90 %, especially for crop-attacked images.