We consider the hashing mechanism for constructing binary embeddings, that
involves pseudo-random projections followed by nonlinear (sign function)
mappings. The pseudo-random projection is described by a matrix, where not all
entries are independent random variables but instead a fixed "budget of
randomness" is distributed across the matrix. Such matrices can be efficiently
stored in sub-quadratic or even linear space, provide reduction in randomness
usage (i.e. number of required random values), and very often lead to
computational speed ups. We prove several theoretical results showing that
projections via various structured matrices followed by nonlinear mappings
accurately preserve the angular distance between input high-dimensional
vectors. To the best of our knowledge, these results are the first that give
theoretical ground for the use of general structured matrices in the nonlinear
setting. In particular, they generalize previous extensions of the
Johnson-Lindenstrauss lemma and prove the plausibility of the approach that was
so far only heuristically confirmed for some special structured matrices.
Consequently, we show that many structured matrices can be used as an efficient
information compression mechanism. Our findings build a better understanding of
certain deep architectures, which contain randomly weighted and untrained
layers, and yet achieve high performance on different learning tasks. We
empirically verify our theoretical findings and show the dependence of learning
via structured hashed projections on the performance of neural network as well
as nearest neighbor classifier.

此论文研究了利用哈希机制来构建二进制嵌入的方法，该方法包括伪随机投影和非线性映射，使用结构化矩阵可以有效地压缩信息并降低随机性使用，实验证明了其对神经网络学习性能和最近邻分类器性能的依赖关系。

结构化散列投影的二进制嵌入

Binary embeddings with structured hashed projections

We consider a class of nonlinear mappings $\mathsf{F}_{A,N}$ in
$\mathbb{R}^N$ indexed by symmetric random matrices $A\in\mathbb{R}^{N\times
N}$ with independent entries. Within spin glass theory, special cases of these
mappings correspond to iterating the TAP equations and were studied by
Bolthausen [Comm. Math. Phys. 325 (2014) 333-366]. Within information theory,
they are known as "approximate message passing" algorithms. We study the
high-dimensional (large $N$) behavior of the iterates of $\mathsf{F}$ for
polynomial functions $\mathsf{F}$, and prove that it is universal; that is, it
depends only on the first two moments of the entries of $A$, under a
sub-Gaussian tail condition. As an application, we prove the universality of a
certain phase transition arising in polytope geometry and compressed sensing.
This solves, for a broad class of random projections, a conjecture by David
Donoho and Jared Tanner.

研究了一类非线性映射在高维情况下的特性及其在多面体几何和压缩感知方面的应用。