We consider the recovery of low-rank matrices from noisy data by shrinkage of singular values, in which a single, univariate nonlinearity is applied to each of the empirical singular values. We adopt an asymptotic framework, in which the matrix size is much larger than the rank of the signal matrix to be recovered, and the signal-to-noise ratio of the low-rank piece stays constant. For a variety of loss functions, including Mean Square Error (MSE) - (square Frobenius norm), the nuclear norm loss and the operator norm loss, we show that in this framework there is a well-defined asymptotic loss that we evaluate precisely in each case. In fact, each of the loss functions we study admits a unique admissible shrinkage nonlinearity dominating all other nonlinearities. We provide a general method for evaluating these optimal nonlinearities, and demonstrate our framework by working out simple, explicit formulas for the optimal nonlinearities in the Frobenius, nuclear and operator norm cases. For example, for a square low-rank n-by-n matrix observed in white noise with level σ, the optimal nonlinearity for MSE loss simply shrinks each data singular value y to √(y 2 -4nσ 2 ) (or to 0 if y <; 2√nσ). This optimal value y to nonlinearity guarantees an asymptotic MSE of 2nrσ 2 , which compares favorably with optimally tuned hard thresholding and optimally tuned soft thresholding, providing guarantees of 3nrσ 2 and 6nrσ 2 , respectively. Our general method also allows one to evaluate optimal shrinkers numerically to arbitrary precision. As an example, we compute optimal shrinkers for the Schatten-p norm loss, for any p > 0.
23 November 2020 in Proceedings of the National Academy of Sciences
We propose a local conformal autoencoder (LOCA) for standardized data coordinates. LOCA is a deep learning-based method for obtaining standardized data coordinates from scientific measurements. Data observations are modeled as samples from an unknown, nonlinear deformation of an underlying Riemannian manifold, which is parametrized by a few normalized, latent variables. We assume a repeated measurement sampling strategy, common in scientific measurements, and present a method for learning an embedding in that is isometric to the latent variables of the manifold. The coordinates recovered by our method are invariant to diffeomorphisms of the manifold, making it possible to match between different instrumental observations of the same phenomenon. Our embedding is obtained using LOCA, which is an algorithm that learns to rectify deformations by using a local z-scoring procedure, while preserving relevant geometric information. We demonstrate the isometric embedding properties of LOCA in various model settings and observe that it exhibits promising interpolation and extrapolation capabilities, superior to the current state of the art. Finally, we demonstrate LOCA’s efficacy in single-site Wi-Fi localization data and for the reconstruction of three-dimensional curved surfaces from two-dimensional projections. Significance A fundamental issue in empirical science is the ability to calibrate between different types of measurements/observations of the same phenomenon. This naturally suggests the selection of canonical variables, in the spirit of principal components, to enable matching/calibration among different observation modalities/instruments. We develop a method for extracting standardized, nonlinear, intrinsic coordinates from measured data, leading to a generalized isometric embedding of the observations. This is achieved through a local burst data acquisition strategy that allows us to capture the local z-scored structure. We implement this method using a local conformal autoencoder architecture and illustrate it computationally. The proposed embedding is fast, parallelizable, easy to implement using existing open-source neural network implementations and exhibits surprising interpolation and extrapolation capabilities.
18 January 2010 in Ergodic Theory and Dynamical Systems
We introduce a property of measures on Euclidean space, termed ‘uniform scaling scenery’. For these measures, the empirical distribution of the measure-valued time series, obtained by rescaling around a point, is (almost everywhere) independent of the point. This property is related to existing notions of self-similarity: it is satisfied by the occupation measure of a typical Brownian motion (which is ‘statistically’ self-similar), as well as by the measures associated to attractors of affine iterated function systems (which are ‘exactly’ self-similar). It is possible that different notions of self-similarity are unified under this property. The proofs trace a connection between uniform scaling scenery and Furstenberg’s ‘CP processes’, a class of natural, discrete-time, measure-valued Markov processes, useful in fractal geometry.
13 June 2017 in Proceedings of the National Academy of Sciences
We draw a random subset of rows from a frame with rows (vectors) and columns (dimensions), where and are proportional to . For a variety of important deterministic equiangular tight frames (ETFs) and tight non-ETFs, we consider the distribution of singular values of the -subset matrix. We observe that, for large , they can be precisely described by a known probability distribution—Wachter’s MANOVA (multivariate ANOVA) spectral distribution, a phenomenon that was previously known only for two types of random frames. In terms of convergence to this limit, the -subset matrix from all of these frames is shown to be empirically indistinguishable from the classical MANOVA (Jacobi) random matrix ensemble. Thus, empirically, the MANOVA ensemble offers a universal description of the spectra of randomly selected subframes, even those taken from deterministic frames. The same universality phenomena is shown to hold for notable random frames as well. This description enables exact calculations of properties of solutions for systems of linear equations based on a random choice of frame vectors of possible vectors and has a variety of implications for erasure coding, compressed sensing, and sparse recovery. When the aspect ratio is small, the MANOVA spectrum tends to the well-known Marčenko–Pastur distribution of the singular values of a Gaussian matrix, in agreement with previous work on highly redundant frames. Our results are empirical, but they are exhaustive, precise, and fully reproducible. Significance A frame (overcomplete set of vectors) represents an analog coding scheme. Deterministic frame constructions offer useful codes for communication and signal processing tasks. When the coded signal only uses a random subset of the frame vectors (for example, in compressed sensing), the coding quality is determined by the typical covariances within subsets of frame vectors. We provide a method to calculate functions of these typical covariances, which predict specific performance measures of the corresponding coding scheme. Our method uses a universality property: for many well-known deterministic and random frames, typical covariances within subsets of frame vectors do not depend on the frame and are described by the MANOVA (multivariate ANOVA) ensemble, a classical object in statistics and random matrix theory.
25 June 2018 in Proceedings of the National Academy of Sciences
In matrix recovery from random linear measurements, one is interested in recovering an unknown M-by-N matrix from measurements , where each is an M-by-N measurement matrix with i.i.d. random entries, . We present a matrix recovery algorithm, based on approximate message passing, which iteratively applies an optimal singular-value shrinker—a nonconvex nonlinearity tailored specifically for matrix estimation. Our algorithm typically converges exponentially fast, offering a significant speedup over previously suggested matrix recovery algorithms, such as iterative solvers for nuclear norm minimization (NNM). It is well known that there is a recovery tradeoff between the information content of the object to be recovered (specifically, its matrix rank r) and the number of linear measurements n from which recovery is to be attempted. The precise tradeoff between r and n, beyond which recovery by a given algorithm becomes possible, traces the so-called phase transition curve of that algorithm in the plane. The phase transition curve of our algorithm is noticeably better than that of NNM. Interestingly, it is close to the information-theoretic lower bound for the minimal number of measurements needed for matrix recovery, making it not only state of the art in terms of convergence rate, but also near optimal in terms of the matrices it successfully recovers. Significance Various problems of science and engineering can be reduced to recovery of an unknown matrix from a small number of random linear measurements. We present two matrix recovery algorithms based on approximate message passing, a framework originally developed for sparse vector recovery problems. Our algorithms typically converge exponentially fast. Matrix recovery algorithms can be compared in terms of the number of measurements required for successful recovery. One of our algorithms requires the same number of measurements as the popular (but much slower) nuclear norm minimization algorithm, while the other, based on optimal singular-value shrinkage, requires a number of measurements close to the information-theoretic lower bound, making it near optimal.