Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations.

Fast linear transforms are ubiquitous in machine learning, including the discrete Fourier transform, discrete cosine transform, and other structured transformations such as convolutions. All of these transforms can be represented by dense matrix-vector multiplication, yet each has a specialized and highly efficient (subquadratic) algorithm. We ask to what extent hand-crafting these algorithms and implementations is necessary, what structural priors they encode, and how much knowledge is required to automatically learn a fast algorithm for a provided structured transform. Motivated by a characterization of fast matrix-vector multiplication as products of sparse matrices, we introduce a parameterization of divide-and-conquer methods that is capable of representing a large class of transforms. This generic formulation can automatically learn an efficient algorithm for many important transforms; for example, it recovers the O(N log N) Cooley-Tukey FFT algorithm to machine precision, for dimensions N up to 1024. Furthermore, our method can be incorporated as a lightweight replacement of generic matrices in machine learning pipelines to learn efficient and compressible transformations. On a standard task of compressing a single hidden-layer network, our method exceeds the classification accuracy of unconstrained matrices on CIFAR-10 by 3.9 points-the first time a structured approach has done so-with 4× faster inference speed and 40× fewer parameters.

Learning Compressed Transforms with Low Displacement Rank.

The low displacement rank (LDR) framework for structured matrices represents a matrix through two displacement operators and a low-rank residual. Existing use of LDR matrices in deep learning has applied fixed displacement operators encoding forms of shift invariance akin to convolutions. We introduce a rich class of LDR matrices with more general displacement operators, and explicitly learn over both the operators and the low-rank component. This class generalizes several previous constructions while preserving compression and efficient computation. We prove bounds on the VC dimension of multi-layer neural networks with structured weight matrices and show empirically that our compact parameterization can reduce the sample complexity of learning. When replacing weight layers in fully-connected, convolutional, and recurrent neural networks for image classification and language modeling tasks, our new classes exceed the accuracy of existing compression approaches, and on some tasks even outperform general unstructured layers while using more than 20X fewer parameters.

A two-pronged progress in structured dense matrixvector multiplication.

Matrix-vector multiplication is one of the most fundamental computing primitives. Given a matrix A ∈ F N × N and a vector b ∈ F N , it is known that in the worst case Θ(N 2) operations over F are needed to compute Ab. Many types of structured matrices do admit faster multiplication. However, even given a matrix A that is known to have this property, it is hard in general to recover a representation of A exposing the actual fast multiplication algorithm. Additionally, it is not known in general whether the inverses of such structured matrices can be computed or multiplied quickly. A broad question is thus to identify classes of structured dense matrices that can be represented with O(N) parameters, and for which matrix-vector multiplication (and ideally other operations such as solvers) can be performed in a sub-quadratic number of operations. One such class of structured matrices that admit near-linear matrix-vector multiplication are the orthogonal polynomial transforms whose rows correspond to a family of orthogonal polynomials. Other well known classes include the Toeplitz, Hankel, Vandermonde, Cauchy matrices and their extensions (e.g. confluent Cauchy-like matrices) that are all special cases of a low displacementrank property. In this paper, we make progress on two fronts: Our work unifies, generalizes, and simplifies existing state-of-the-art results in structured matrix-vector multiplication. Finally, we show how applications in areas such as multipoint evaluations of multivariate polynomials can be reduced to problems involving low recurrence width matrices.

Using smartphones to collect time-activity data for long-term personal-level air pollution exposure assessment.

Because of the spatiotemporal variability of people and air pollutants within cities, it is important to account for a person's movements over time when estimating personal air pollution exposure. This study aimed to examine the feasibility of using smartphones to collect personal-level time-activity data. Using Skyhook Wireless's hybrid geolocation module, we developed "Apolux" (Air, Pollution, Exposure), an Android(TM) smartphone application designed to track participants' location in 5-min intervals for 3 months. From 42 participants, we compared Apolux data with contemporaneous data from two self-reported, 24-h time-activity diaries. About three-fourths of measurements were collected within 5 min of each other (mean=74.14%), and 79% of participants reporting constantly powered-on smartphones (n=38) had a daily average data collection frequency of <10 min. Apolux's degree of temporal resolution varied across manufacturers, mobile networks, and the time of day that data collection occurred. The discrepancy between diary points and corresponding Apolux data was 342.3 m (Euclidian distance) and varied across mobile networks. This study's high compliance and feasibility for data collection demonstrates the potential for integrating smartphone-based time-activity data into long-term and large-scale air pollution exposure studies.