Reconstruction Algorithms For Compressive Sensing And Their Applications To Digital Watermarking

Compressive sensing is a novel signal sampling theory under the condition that the signal is sparse or compressible. In this case, the signal can be reconstructed accurately from a small amount of sampled values if the signal is sparse or compressible. The theory has successfully overcome the difficulties such as redundancy of sampling and waste of physical resources. The reconstruction algorithm is a very important part for compressive sensing. In this paper, we mainly discussed the properties of the reconstruction algorithms available. Based on the analysis of the existing reconstruction algorithms, we made some great improvements. The main contributions of this paper are summarized as follows.Improvement on subspace pursuit (SP) algorithm for better signal reconstruction. In this paper, we reviewed the existing reconstruction algorithms such as OMP, ROMP and SP and analyzed the atoms renewal process in those algorithms. We mainly focused on the recalling process in SP, in which some atoms may be removed from the atom set even if they were probably selected in the last iteration. So the problem is that whether the accuracy of the algorithm can be improved when those atoms are renewed. In this paper, we proposed a new atom renewal method, which can successfully solve the problem. The experimental results show that the new algorithm is superior to the SP algorithm.Improvement on SLO algorithm for better signal reconstruction. The key point of smoothed l0 norm algorithm is using smooth function to approximate l0 norm. With the introduction of convex programming, including the steepest descent method and gradient projection, the algorithm can obtain the final solution by solving an optimization problem. Based on thorough study of SLO algorithm, we chose the hyperbolic tangent function to approximate l0 norm. Finally we proposed a new reconstruction algorithm based on smoothed l0 norm and revised Newton method (NSLO algorithm).The application of the CS theory to digital watermarking. The digital watermarking theory is a technology to confirm the ownership of data by embedding secret information (watermark) in original data. In this paper, by making full use of the characteristics of CS, we complemented digital watermarking process in CS domain. The measurement matrix for CS acts as the key for extraction of watermark. Since there are a lot of methods for constructing a measurement matrix and the size of matrix is various, it is difficult to extract the watermark from the given image without the key. Simulation results show that the proposed method is robust to most of attacks..