When Compressive Sensing Meets Data Hiding

We present a novel framework of performing multimedia data hiding using an over-complete dictionary, which brings compressive sensing to the application of data hiding. Unlike the conventional orthonormal full-space dictionary, the over-complete dictionary produces an underdetermined system with infinite transform results. We first discuss the minimum norm formulation (l(2)-norm) which yields a closed-form solution and the concept of watermark projection, so that higher embedding capacity and an additional privacy preserving feature can be obtained. Furthermore, we study the sparse formulation (l(0)-norm) and illustrate that as long as the l(0)-norm of the sparse representation of the host signal is less than the signal's dimension in the original domain, an informed sparse domain data hiding system can be established by modifying the coefficients of the atoms that have not participated in representing the host signal. A single support modification-based data hiding system is then proposed and analyzed as an example. Several potential research directions are discussed for further studies. More generally, apart from the l(2)- and l(0)-norm constraints, other conditions for reliable detection performance are worth of future investigation.