Over the past few years, quantization has shown great and consistent success in compressing high-dimensional data and over-parameterized models. This dissertation focuses on theoretical guarantees and applications of quantization algorithms for fast binary embeddings (FBEs), random Fourier features (RFFs), and neural networks (NNs). Chapter 1 presents an introduction to quantization and background information for topics covered by later chapters.

In Chapter 2, we introduce a novel fast binary embedding algorithm that transforms data points from high-dimensional space into low-dimensional binary sequences. We prove that the $\ell_2$ distances among original data points can be recovered by the $\ell_1$ norm on binary embeddings and its associated approximation error is comparable to that of a continuous valued Johnson-Lindenstrauss embedding plus a quantization error that admits a polynomial decay as the embedding dimension increases. So the length of the binary codes required to achieve a desired accuracy is quitesmall which is empirically verified by our experiments over natural images.

As a natural extension of Chapter 2, Chapter 3 proposes low-bit $\Sigma\Delta$ and distributed noise-shaping methods for quantizing RFFs associated with shift-invariant kernels. We show that the quantized RFFs achieve a high accuracy approximation of the underlying kernels with the approximation error decaying polynomially as the dimension of the RFFs increases, and decaying exponentially as a function of the bits used. Moreover, we test our method on multiple machine learning tasks that involve the kernel method.

In Chapter 4, we generalize a post-training neural-network quantization method, GPFQ, that is based on a greedy path-following mechanism. We expands the results of previous work on GPFQ to handle general quantization alphabets and a range of input distributions, showing that for quantizing a single-layer network, the relative square error essentially decays linearly in the number of weights – i.e., level of over-parametrization. Additionally, we propose modifications to promote sparsity of the weights, and rigorously analyze the associated error. Without fine-tuning, we can quantize several common architectures to $4$ bits, while attaining an accuracy loss less than $1\%$.

Since the theoretical results in Chapter 4 are limited to single-layer neural networks, in Chapter 5, we propose a new stochastic algorithm for quantizing pretrained neural networks. We establish, for the first time, rigorous full-network error bounds, under an infinite alphabet condition and minimal assumptions on the weights and input data. Moreover, we demonstrate that it is possible to achieve error bounds equivalent to those obtained in the infinite alphabet case, using a mere $\log_2\log N$ bits, where $N$ represents the maximum width across all layers.

This dissertation focuses on sparse representation and dictionary learning, with three relative topics. First, in chapter 1, we study the problem of low-rank matrix recovery in the presence of prior information. We first study the recovery of low-rank matrices with a necessary and sufficient condition, called the Null Space Property, for exact recovery from compressively sampled measurements using nuclear norm minimization. Here, we provide an alternative theoretical analysis of the bound on the number of random Gaussian measurements needed for the condition to be satisfied with high probability. We then study low-rank matrix recovery when prior information is available. We analyze an existing algorithm, provide the necessary and sufficient conditions for exact recovery and show that the existing algorithm is limited in certain cases. We provide an alternative recovery algorithm to deal with the drawback and provide sufficient recovery conditions based on that.

In chapter 2, we study the problem of learning a sparsifying dictionary of a set of data, focusing on learning dictionaries that admit fast transforms. Inspired by the Fast Fourier Transform, we propose a learning algorithm involving $O(N)$ unknown parameters for a $N\times N$ linear transformation matrix. Empirically, our algorithm can produce dictionaries that provide lower numerical sparsity for the sparse representation of images than the Discrete Fourier Transformation (DFT). Additionally, due to its structure, the learned dictionary can recover the original signal from the sparse representation in $O(N\log N)$ computations.

In chapter 3, we study the representation learning problem in a more complex setting. We use the concept of dictionary learning and apply it in a deep generative model. Motivated by an application in the computer gaming industry where designers needs to have an urban layout generation tool that allows fast generation and modification, we present a novel solution to synthesize high quality building placements using conditional generative latent optimization together with adversarial training. The capability of the proposed method is demonstrated in various examples. The inference is nearly in real time, thus it can assist designers to iterate their designs of virtual cities quickly.

This thesis explores the topic of quantization in the context of data science and digital signal processing. It is already well-known that quantization plays a critical role in signal processing given the ubiquity of digital devices. Applications of quantization to data science have only recently started emerging. Perhaps the most important application is that of quantizing neural networks. Below, we consider quantization in three particular contexts. The first chapter considers the problem of quantizing a pre-trained neural network with a data-driven approach. I propose a novel algorithm for quantizing the weights of a hidden unit in a given layer using a greedy path following algorithm which is equivalent to running a dynamical system. I prove that this dynamical system is stable when quantizing a single layer neural network, or equivalently the first layer of a multi-layer network, when the training data are Gaussian. I then give bounds on the generalization error of the learned quantization and describe how these bounds may be tightened when the feature data lay in a low-dimensional subspace. In the second chapter, I generalize a 2016 result proven by Saab, Wang, and Yilmaz for recovering sparse vectors to the setting of low-rank matrices. Specifically, I show that low-rank matrices may be robustly recovered from \(\Sigma\Delta\) quantized subgaussian linear measurements. Using these techniques I show that the reconstruction error associated with our methods decays polynomially with the oversampling factor, and that one can leverage this result to obtain root-exponential accuracy by optimizing over the choice of quantization scheme. Additionally, if a random encoding of the quantized measurements is used then the reconstruction bound exhibits a near-optimal exponential rate-distortion trade-off. In the third chapter, I generalize work done by Iwen, Krahmer, Krause-Solberg, and Maly in 2018 to prove that signal recovery is possible when given \(\Sigma\Delta\) quantized linear measurements of signals from a manifold where the manifold is only approximately known through a Geometric Multi-Resolution Analysis. In addition to proving error bounds that outperform those in the Memoryless Scalar Quantization approach taken in the aforementioned work, we also extend the ensemble of linear measurements beyond the Gaussian case.

In this dissertation, we study a new approach to the problem of phase retrieval, which is the task of reconstructing a complex-valued signal from magnitude-only measurements. This problem occurs naturally in several specialized imaging applications such as electron microscopy and X-ray crystallography. Although solutions were first proposed for this problem as early as the 1970s, these algorithms have lacked theoretical guarantees of success, and phase retrieval has suffered from a considerable gap between practice and theory for almost the entire history of its study.

A common technique in fields that use phase retrieval is that of ptychography, where measurements are collected by only illuminating small sections of the sample at any time. We refer to measurements designed in this way as local measurements, and in this dissertation, we develop and expand the theory for solving phase retrieval in measurement regimes of this kind. Our first contribution is a basic model for this setup in the case of a one-dimensional signal, along with an algorithm that robustly solves phase retrieval under this model. This work is unique in many ways that represent substantial improvements over previously existing solutions: perhaps most significantly, many of the recovery guarantees in recent work rely on the measurements being generated by a random process, while we devise a class of measurements for which the conditioning of the system is known and quickly checkable. These advantages constitute major progress towards producing theoretical results for phase retrieval that are directly usable in laboratory settings. Chapter 1 conducts a survey of the history of phase retrieval and its applications, as well as the recent literature on the subject. Chapter 2 presents co-authored results defining and establishing the setting and solution of the base model explored in this dissertation. Chapter 3 expands the theory on what measurement schemes are admissible in our model, including an analysis of conditioning and runtime. Chapter 4 introduces an alternate solution for angular synchronization that yields helpful theoretical results. Chapter 5 brings our model nearer to the actual practice of ptychography. Chapter 6 extends the base model to two dimensions.

We study two problems from mathematical signal processing. First, we consider problem of approximately recovering signals on a smooth, compact manifold from one-bit linear measurements drawn from either a Gaussian ensemble, partial circulant ensemble, or bounded orthonormal ensemble and quantized using \(\Sigma\Delta\) or distributed noise-shaping schemes. We construct a convex optimization algorithm for signal recovery that, given a Geometric Multi-Resolution Analysis approximation of the manifold, guarantees signal recovery with high probability. We prove an upper bound on the recovery error which outperforms prior works that use memoryless scalar quantization, requires a simpler analysis, and extends the class of measurements beyond Gaussians.

Second, we consider the problem of approximation continuous functions on compact domains using neural networks. The learning speed of feed-forward neural networks is notoriously slow and has presented a bottleneck in deep learning applications for several decades. For instance, gradient-based learning algorithms, which are used extensively to train neural networks, tend to work slowly when all of the network parameters must be iteratively tuned. To counter this, both researchers and practitioners have tried introducing randomness to reduce the learning requirement. Based on the original construction of B.~Igelnik and Y.H.~Pao, single layer neural-networks with random input-to-hidden layer weights and biases have seen success in practice, but the necessary theoretical justification is lacking. We begin to fill this theoretical gap by providing a (corrected) rigorous proof that the Igelnik and Pao construction is a universal approximator for continuous functions on compact domains, with \(\varepsilon\)-error convergence rate inversely proportional to the number of network nodes; we then extend this result to the non-asymptotic setting using a concentration inequality for Monte-Carlo integral approximations. We further adapt this randomized neural network architecture to approximate functions on smooth, compact submanifolds of Euclidean space, providing theoretical guarantees in both the asymptotic and non-asymptotic cases.