In this work, we formally prove that, under certain conditions, if a neural network is invariant to a finite group then its weights recover the Fourier transform on that group. This provides a mathematical explanation for the emergence of Fourier features – a ubiquitous phenomenon in both biological and artificial learning systems. The results hold even for non-commutative groups, in which case the Fourier transform encodes all the irreducible unitary group representations. Our findings have consequences for the problem of symmetry discovery. Specifically, we demonstrate that the algebraic structure of an unknown group can be recovered from the weights of a network that is at least approximately invariant within certain bounds. Overall, this work contributes to a foundation for an algebraic learning theory of invariant neural network representations.

An important problem in signal processing and deep learning is to achieve *invariance* to nuisance factors not relevant for the task. Since many of these factors are describable as the action of a group $G$ (e.g. rotations, translations, scalings), we want methods to be $G$-invariant. The $G$-Bispectrum extracts every characteristic of a given signal up to group action: for example, the shape of an object in an image, but not its orientation. Consequently, the $G$-Bispectrum has been incorporated into deep neural network architectures as a computational primitive for $G$-invariance\textemdash akin to a pooling mechanism, but with greater selectivity and robustness. However, the computational cost of the $G$-Bispectrum ($\mathcal{O}(|G|^2)$, with $|G|$ the size of the group) has limited its widespread adoption. Here, we show that the $G$-Bispectrum computation contains redundancies that can be reduced into a *selective $G$-Bispectrum* with $\mathcal{O}(|G|)$ complexity. We prove desirable mathematical properties of the selective $G$-Bispectrum and demonstrate how its integration in neural networks enhances accuracy and robustness compared to traditional approaches, while enjoying considerable speeds-up compared to the full $G$-Bispectrum.

A challenge in image processing is quantifying the perceptual quality of distorted images. Solutions to this problem allow lossy compression algorithms to be more easily and accurately evaluated. Motivated by failings of mean-squared error (MSE/PSNR), Wang, Bovik, and others proposed a perceptual image measure called mean structural similarity (MSSIM), which decomposes the distortion of image patches into three components: a difference in mean luminance, a difference in luminance variance, and a difference in structure. We present a new measure, mean discrete structural similarity (MDSSIM), that replaces the structural comparison of MSSIM with the Hamming distance between suitably discretized original and distorted image patches. To assess its performance, we apply this new image measure to a standard human psychophysics dataset, the LIVE Image Quality Assessment Database (Release 2). The high correlation of MDSSIM with human scores suggests, consistent with experiment and well-known results about lossy compression, that the human visual system may be fundamentally concerned with discrete structure in natural images.

Sparse coding or sparse dictionary learning has been widely used to recover underlying structure in many kinds of natural data. Here, we provide conditions guaranteeing when this recovery is universal; that is, when sparse codes and dictionaries are unique (up to natural symmetries). Our main tool is a useful lemma in combinatorial matrix theory that allows us to derive bounds on the sample sizes guaranteeing such uniqueness under various assumptions for how training data are generated. Whenever the conditions to one of our theorems are met, any sparsity-constrained learning algorithm that succeeds in reconstructing the data recovers the original sparse codes and dictionary. We also discuss potential applications to neuroscience and data analysis.

The Hopfield network is a well-known model of memory and collective processing in networks of abstract neurons, but it has been dismissed for use in signal processing because of its small pattern capacity, difficulty to train, and lack of practical applications. In the last few years, however, it has been demonstrated that exponential storage is possible for special classes of patterns and network connectivity structures. Over the same time period, advances in training large-scale networks have also appeared. Here, we train Hopfield networks on discretizations of grayscale digital photographs using a learning technique called minimum probability flow (MPF). After training, we demonstrate that these networks have exponential memory capacity, allowing them to perform state-of-the-art image compression in the high quality regime. Our findings suggest that the local structure of images is remarkably well-modeled by a binary recurrent neural network.

We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list includes: determining the feasibility of a system of bilinear equations, deciding whether a 3-tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or the spectral norm; and determining the rank or best rank-1 approximation of a 3-tensor. Furthermore, we show that restricting these problems to symmetric tensors does not alleviate their NP-hardness. We also explain how deciding nonnegative definiteness of a symmetric 4-tensor is NP-hard and how computing the combinatorial hyperdeterminant is NP-, #P-, and VNP-hard.

Sparse coding networks, which utilize unsupervised learning to maximize coding efficiency, have successfully reproduced response properties found in primary visual cortex [1]. However, conventional sparse coding models require that the coding circuit can fully sample the sensory data in a one-to-one fashion, a requirement not supported by experimental data from the thalamo-cortical projection. To relieve these strict wiring requirements, we propose a sparse coding network constructed by introducing synaptic learning in the framework of compressed sensing. We demonstrate a new model that evolves biologically realistic, spatially smooth receptive fields despite the fact that the feedforward connectivity subsamples the input and thus the learning must rely on an impoverished and distorted account of the original visual data. Further, we demonstrate that the model could form a general scheme of cortical communication: it can form meaningful representations in a secondary sensory area, which receives input from the primary sensory area through a “compressing” cortico-cortical projection. Finally, we prove that our model belongs to a new class of sparse coding algorithms in which recurrent connections are essential in forming the spatial receptive fields.

A new algorithm is proposed for a) unsupervised learning of sparse representations from subsampled measurements and b) estimating the parameters required for linearly reconstructing signals from the sparse codes. We verify that the new algorithm performs efficient data compression on par with the recent method of compressive sampling. Further, we demonstrate that the algorithm performs robustly when stacked in several stages or when applied in undercomplete or overcomplete situations. The new algorithm can explain how neural populations in the brain that receive subsampled input through fiber bottlenecks are able to form coherent response properties.

A symmetric ideal I ⊂ R = K[x1,x2,...] is an ideal that is invariant under the natural action of the infinite symmetric group. We give an explicit algorithm to find Grobner bases for symmetric ideals in the infinite dimensional polynomial ring R. This allows for symbolic computation in a new class of rings. In particular, we solve the ideal membership problem for symmetric ideals of R.