Sharp Reconstruction Bounds for Autoencoders Using the Same Forward Map

Autoencoders typically meet tight latent-memory budgets by making each latent representation smaller, sacrificing representational capacity. We ask a different question: can multiple wider latents be stored together instead? We introduce the Superposed Latent Autoencoder (SLAE), which preserves high-capacity latent representations while sharing storage through learned superposition. SLAE transforms latents into storage-friendly codes, binds them with randomized keys, superposes multiple codes into a single memory tensor, and learns to recover each latent before decoding. Under the same storage budget, SLAE replaces irreversible dimensional bottlenecks with structured interference that can be suppressed. Across CIFAR-10/100, SVHN, STL-10, Tiny ImageNet, and a wide range of memory budgets, SLAE substantially improves the reconstruction--memory tradeoff, reducing reconstruction error by up to 56% over conventional autoencoders at matched storage. Further analysis shows that SLAE's advantage comes from making wider representations usable under the same storage budget. These gains also extend beyond reconstruction: the information preserved by SLAE improves downstream classification by up to 16.79 percentage points under the same memory budget. Our results suggest a new principle for representation compression: instead of making every latent smaller, keep representations wide and let them share memory.

Autoencoders are widely used for nonlinear dimensionality reduction and manifold learning. While most common implementations rely on both nonlinear encoders and decoders, we investigate the specific role of the encoder and the extent to which it can be constrained to be linear without reducing accuracy. We conduct a comparative study on four autoencoder architectures: standard fully nonlinear autoencoders (AE), linear-encoder autoencoders (Lenc-AE), linear-decoder autoencoders (Ldec-AE), and fully linear autoencoders (LAE), evaluated on synthetic manifolds, computational mechanics data sets, and real-world image data sets including MNIST. We demonstrate that imposing a linear encoder preserves most of the representational capacity of the autoencoder, provided the decoder remains nonlinear. In particular, Lenc-AE consistently outperforms both Ldec-AE and LAE, and achieves reconstruction quality comparable to fully nonlinear AE, while offering advantages in terms of parsimony and interpretability of the latent representation. These results suggest that the nonlinear decoder is the critical component for manifold learning, rather than the encoder. A geometric interpretation of this finding is developed, which identifies the precise conditions under which a linear encoder is sufficient, and the specific manifold configurations that expose its limitations.

We study the problem of reconstructing an unknown point in $\mathbb{R}^d$ from approximate linear queries. This setting arises naturally in applications ranging from low-dimensional remote sensing and signal recovery to high-dimensional data analysis and privacy-sensitive inference. Our main goal is to characterize the optimal reconstruction error as a function of the number of queries $T$, the ambient dimension $d$, and the noise parameter $δ$. We first analyze the limit $T \to \infty$ and show that the optimal reconstruction error converges to the explicit value $\sqrt{2d/(d+1)} δ$, which plays a role analogous to the Bayes optimal error in supervised learning. When the dimension is fixed, we show that the excess error above this limit decays doubly exponentially fast as $T \to \infty$, a rate that is significantly faster than those typically encountered in learning curves. When the dimension grows, we show that a number of queries on the order of $\exp(d)$ is necessary and sufficient to achieve vanishing excess error. Finally, we introduce and analyze an improper variant of the reconstruction problem. From a technical perspective, our main contribution is a generalization of Jung's theorem (1901). The classical theorem bounds the maximum possible radius of a set of diameter 1 and characterizes extremal bodies. Our generalization provides a robust variant that characterizes near-extremal bodies and is proved via geometric and dynamical arguments exploiting symmetry and Lie group actions.