The ubiquity of high-dimensional data often poses a significant challenge for many science and engineering problems − both in theory and practice. Fortunately, in most situations the data exhibits certain low-dimensional property such as sparsity or being contained in a smooth manifold despite it being expressed in a high-dimensional ambient space. This fact later became exploitable thanks to a breakthrough in compressed sensing, that is, certain random matrices can efficiently embed such structured data into a low-dimensional space whilst almost preserving the pairwise distance between data points − an attribute known as the Restricted Isometry Property (RIP). This enables applications to circumvent the high dimensionality of the ambient space and instead work with the embedded low-...[ Read more ]

The ubiquity of high-dimensional data often poses a significant challenge for many science and engineering problems − both in theory and practice. Fortunately, in most situations the data exhibits certain low-dimensional property such as sparsity or being contained in a smooth manifold despite it being expressed in a high-dimensional ambient space. This fact later became exploitable thanks to a breakthrough in compressed sensing, that is, certain random matrices can efficiently embed such structured data into a low-dimensional space whilst almost preserving the pairwise distance between data points − an attribute known as the Restricted Isometry Property (RIP). This enables applications to circumvent the high dimensionality of the ambient space and instead work with the embedded low-dimensional space − a much cheaper alternative.

This thesis explores two applications of random projections in the context of deep learning. The first application is on the approximation power of feedforward neural networks for data with a low-dimensional structure, namely sparsity or smooth manifold. Using the fact that Gaussian random projections satisfy RIP with high probability, this thesis will prove that the minimum number of neurons required to achieve a prescribed accuracy when approximating a Lipschitz continuous function depends mainly on the low-dimensional structure and only weakly on the ambient space. The second application is on improving the practical efficiency of neural networks. Experiments demonstrate that by carefully incorporating random projections into fully-connected and convolutional neural networks, the number of parameters and computational complexity can be drastically reduced without causing any significant loss of prediction accuracy in classification tasks.