A spin glass model for reconstructing nonlinearly encrypted signals corrupted by noise

Abstract

An encryption of a signal $\mathbf{s}\in {\mathbb{R}}^{\mathbb{N}}$ is a random mapping $\mathbf{s}\mapsto \text{y}=(y_1,\dots ,y_M{)}^T\in {\mathbb{R}}^M$ which can be corrupted by an additive noise. Given the Encryption Redundancy Parameter (ERP) $\mu =M/N\ge 1$, the signal strength parameter $R=\sqrt{{\sum }_i{s}_i^2/N}$, and the ('bare') noise-to-signal ratio (NSR) $\gamma \ge 0$, 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-distributed random 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 'estimator') as $N\to \infty$, 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_{\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 <\infty$, with $p_{\infty }\sim {\gamma }^{-1/2}$ as $\gamma \to \infty$. In contrast, for the case of purely quadratic nonlinearity, for any ERP $\mu >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.

33 pages, 5 figures

References in corpus (6)

• Classical Particle in a Box with Random Potential: exploiting rotational symmetry of replicated Hamiltonian
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model
• Statistical mechanics of a single particle in a multiscale random potential: Parisi landscapes in finite dimensional Euclidean spaces
• Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed p-spin models
• Statics and dynamics of infinite-dimensional liquids and glasses: a parallel, compact derivation
• Phase diagram of matrix compressed sensing

Cited by in corpus (9)

• Nonlinearity-generated Resilience in Large Complex Systems
• Distribution of rare saddles in the $p$-spin energy landscape
• A continuous constraint satisfaction problem for the rigidity transition in confluent tissues
• Analysis of overfitting in the regularized Cox model
• Finite size effects and loss of self-averageness in the relaxational dynamics of the spherical Sherrington-Kirkpatrick model
• Dynamical mean field theory for models of confluent tissues and beyond
• On the topology of solutions to random continuous constraint satisfaction problems
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Optimization landscape in the simplest constrained random least-square problem