Three important properties of a classification machinery are: (i) the system
preserves the core information of the input data; (ii) the training examples
convey information about unseen data; and (iii) the system is able to treat
differently points from different classes. In this work we show that these
fundamental properties are satisfied by the architecture of deep neural
networks. We formally prove that these networks with random Gaussian weights
perform a distance-preserving embedding of the data, with a special treatment
for in-class and out-of-class data. Similar points at the input of the network
are likely to have a similar output. The theoretical analysis of deep networks
here presented exploits tools used in the compressed sensing and dictionary
learning literature, thereby making a formal connection between these important
topics. The derived results allow drawing conclusions on the metric learning
properties of the network and their relation to its structure, as well as
providing bounds on the required size of the training set such that the
training examples would represent faithfully the unseen data. The results are
validated with state-of-the-art trained networks.

本研究证明深度神经网络具有保留核心信息、能准确处理不同类别数据和传递关于未见数据的信息等重要属性，同时实现距离保持嵌入，并验证此结果适用于现有各类深度神经网络。

带有随机高斯权重的深度神经网络：一种通用的分类策略？

Deep Neural Networks with Random Gaussian Weights: A Universal  Classification Strategy?

We show how to test whether a graph with n vertices and m edges is a partial
cube, and if so how to find a distance-preserving embedding of the graph into a
hypercube, in the near-optimal time bound O(n^2), improving previous O(nm)-time
solutions.

本研究介绍了如何在 O (n^2) 的时间复杂度内测试一个由 n 个顶点和 m 条边组成的图是否为 partial cube，并在此基础上找到一个将该图转化为 distance-preserving embedding 进而嵌入到 hypercube 中的方法，从而实现优化。