A Spin Glass Model for Reconstructing Nonlinearly Encrypted Signals Corrupted by Noise
Yan V. Fyodorov · Journal of Statistical Physics · 2019
We define a (symmetric key) encryption of a signal $$\mathbf{s}\in {\mathbb {R^N}}$$ as a random mapping $$\mathbf{s}\mapsto \mathbf y =(y_1,\ldots ,y_M)^T\in \mathbb {R}^M$$ known both to the sender and a recipient. In general the recipients may have access only to images $$\mathbf{y}$$ corrupted by an additive noise of unknown strength. Given the encryption redundancy parameter (ERP) $$\mu =M/N\ge 1$$ and the signal strength parameter $$R=\sqrt{\sum _i {s_i^2/N}}$$ , we consider the problem of reconstructing $$\mathbf{s}$$ from its corrupted image by a Least Square Scheme for a certain class of random Gaussian mappings. The problem is equivalent to finding the configuration of minimal energy in a certain version of spherical spin glass model, with squared Gaussian random interaction potential. We use the Parisi replica symmetry breaking scheme to evaluate the mean overlap $$p_{\infty }\in [0,1]$$ between the original signal and its recovered image (known as ’estimate’) as $$N\rightarrow \infty $$ , for a given (’bare’) noise-to-signal ratio (NSR) $$\gamma \ge 0$$ . Such an overlap is a measure of the quality of the signal reconstruction. We explicitly analyze the general case of linear-quadratic family of random mappings and discuss the full $$p_{\infty } (\gamma )$$ curve. When nonlinearity exceeds a certain threshold but redundancy is not yet too big, the replica symmetric solution is necessarily broken in some interval of NSR. We show that encryptions with a nonvanishing linear component permit reconstructions with $$p_{\infty }>0$$ for any $$\mu >1$$ and any $$\gamma 1$$ there exists a threshold NSR value $$\gamma _c(\mu )$$ such that $$p_{\infty }=0$$ for $$\gamma >\gamma _c(\mu )$$ making the reconstruction impossible. The behaviour close to the threshold is given by $$p_{\infty }\sim (\gamma _c-\gamma )^{3/4}$$ and is controlled by the replica symmetry breaking mechanism.