Optimal Exponent of the Single-Error Correction Threshold with Fixed Redundancy for Analog Error-Correcting Codes

Abstract

Analog error-correcting codes (Analog ECCs), introduced by Roth [1], address errors in vector-matrix multiplication arising from analog noise and sparse outliers in in-memory computing. A fundamental open problem concerns the lower bound on the single-error correction threshold ${\Gamma }_2(\mathcal{C})$ for real $[n,k]$ linear codes with fixed redundancy $r=n-k\ge 2$. Li et al. [2] recently established that for redundancy $r=2$, every real $[n,n-2]$ linear code $\mathcal{C}$ satisfies ${\Gamma }_2(\mathcal{C})\ge {\csc }^2(\frac{\pi }{2n})$, resolving an open problem in [1], and showed that, for every fixed $r\ge 2$, there exists a class of $[n,k]$ linear code $\mathcal{C}$ over $\mathbb{R}$ such that ${\Gamma }_2(\mathcal{C})\le O(n^{1+\frac{1}{r-1}})$. This paper proves the matching converse in [2]. For every $[n,k]$ linear code $\mathcal{C}\subseteq {\mathbb{R}}^n$ with fixed redundancy $2\le r<n$, we show that \[ Γ_2(\mathcal C)\ge \frac{a_r}{\sqrt{r}\,β_{r-1}\,2^{\frac{1}{r-1}}}\cdot n^{1+\frac{1}{r-1}}, \] where $a_r=\frac{\Gamma (\frac{r}{2})}{\sqrt{\pi }\Gamma (\frac{r+1}{2})}$ and ${\beta }_d={\left(\frac{d{\pi }^{d-1}|{\mathbb{S}}^d|}{|{\mathbb{S}}^{d-1}|}\right)}^{\frac{1}{d}}$ for positive integer $d$. Here ${\mathbb{S}}^d$ denotes the unit sphere in ${\mathbb{R}}^{d+1}$, $|{\mathbb{S}}^d|$ its surface area, and $\Gamma (\cdot )$ the Gamma function. In particular, we further show that ${\Gamma }_2(\mathcal{C})\ge \frac{1}{4\pi \sqrt{3}r}\cdot n^{1+\frac{1}{r-1}}$. Together with the upper bound in [2], this confirms that the exponent $n^{1+\frac{1}{r-1}}$ is optimal, completing the asymptotic characterization of the single-error correction threshold for Analog ECCs.