A spin glass model for reconstructing nonlinearly encrypted signals corrupted by noise
An encryption of a signal s∈R^N is a random mapping sy=(y_1,...,y_M)^T∈R^M which can be corrupted by an additive noise. Given the Encryption Redundancy Parameter (ERP) μ=M/N> 1, the signal strength parameter R=√(∑_i s_i^2/N), and the ('bare') noise-to-signal ratio (NSR) γ> 0, we consider the problem of reconstructing 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-distributed random potential. We use the Parisi replica symmetry breaking scheme to evaluate the mean overlap p_∞∈ [0,1] between the original signal and its recovered image (known as 'estimator') as N→∞, which 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_∞ (γ) 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_∞>0 for any μ>1 and any γ<∞, with p_∞∼γ^-1/2 as γ→∞. In contrast, for the case of purely quadratic nonlinearity, for any ERP μ>1 there exists a threshold NSR value γ_c(μ) such that p_∞=0 for γ>γ_c(μ) making the reconstruction impossible. The behaviour close to the threshold is given by p_∞∼ (γ_c-γ)^3/4 and is controlled by the replica symmetry breaking mechanism.
READ FULL TEXT