In this paper, we use a set-theoretic approach to provide an efficient and deterministic iterative solution for the compensated signature embedding (CSE) scheme introduced in an earlier work.4 In CSE, a fragile signature is derived and embedded into the media using a robust watermarking technique. Since the embedding process leads to altering the media, the media samples are iteratively adjusted to compensate for the embedding distortion. Projections Onto Convex Sets (POCS) is an iterative set-theoretic approach known to be deterministic, effective and has been used in many image processing applications. We propose to use POCS for providing a compensation mechanism to address the CSE problem. We identify two convex constraint sets defined according to image fidelity and signature-generation criteria, and use them in a POCS-based CSE image authentication system. The system utilizes the wavelet transform domain for embedding and compensation. Simulation results are presented to show that the proposed scheme is efficient and accurate in terms of both achieving high convergence speed and maintaining image fidelity.