Source author record

Matan Gavish

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.ST Statistics Theory Information Theory Machine Learning math.IT math.OC Methodology

Catalog footprint

Research overview

7works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

LOCA: LOcal Conformal Autoencoder for standardized data coordinates

We propose a deep-learning based method for obtaining standardized data coordinates from scientific measurements.Data observations are modeled as samples from an unknown, non-linear deformation of an underlying Riemannian manifold, which is parametrized by a few normalized latent variables. By leveraging a repeated measurement sampling strategy, we present a method for learning an embedding in $\mathbb{R}^d$ that is isometric to the latent variables of the manifold. These data coordinates, being invariant under smooth changes of variables, enable matching between different instrumental observations of the same phenomenon. Our embedding is obtained using a LOcal Conformal Autoencoder (LOCA), an algorithm that constructs an embedding to rectify deformations by using a local z-scoring procedure while preserving relevant geometric information. We demonstrate the isometric embedding properties of LOCA on various model settings and observe that it exhibits promising interpolation and extrapolation capabilities. Finally, we apply LOCA to single-site Wi-Fi localization data, and to $3$ -dimensional curved surface estimation based on a $2$ -dimensional projection.

preprint2017arXiv

Random Subsets of Structured Deterministic Frames have MANOVA Spectra

We draw a random subset of $k$ rows from a frame with $n$ rows (vectors) and $m$ columns (dimensions), where $k$ and $m$ are proportional to $n$ . For a variety of important deterministic equiangular tight frames (ETFs) and tight non-ETF frames, we consider the distribution of singular values of the $k$ -subset matrix. We observe that for large $n$ they can be precisely described by a known probability distribution -- Wachter's MANOVA spectral distribution, a phenomenon that was previously known only for two types of random frames. In terms of convergence to this limit, the $k$ -subset matrix from all 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 $k$ -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 $k$ frame vectors out of $n$ possible vectors, and has a variety of implications for erasure coding, compressed sensing, and sparse recovery. When the aspect ratio $m/n$ is small, the MANOVA spectrum tends to the well known Marcenko-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.

preprint2016arXiv

Optimal Shrinkage of Singular Values

We consider 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 $\sqrt{y^2-4nσ^2 }$ (or to 0 if $y<2\sqrt{n}σ$ ). This optimal 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.

preprint2014arXiv

Minimax risk of matrix denoising by singular value thresholding

An unknown $m$ by $n$ matrix $X_0$ is to be estimated from noisy measurements $Y=X_0+Z$ , where the noise matrix $Z$ has i.i.d. Gaussian entries. A popular matrix denoising scheme solves the nuclear norm penalization problem $\operatorname {min}_X\|Y-X\|_F^2/2+λ\|X\|_*$ , where $\|X\|_*$ denotes the nuclear norm (sum of singular values). This is the analog, for matrices, of $\ell_1$ penalization in the vector case. It has been empirically observed that if $X_0$ has low rank, it may be recovered quite accurately from the noisy measurement $Y$ . In a proportional growth framework where the rank $r_n$ , number of rows $m_n$ and number of columns $n$ all tend to $\infty$ proportionally to each other ( $r_n/m_n\rightarrow ρ$ , $m_n/n\rightarrow β$ ), we evaluate the asymptotic minimax MSE $\mathcal {M}(ρ,β)=\lim_{m_n,n\rightarrow \infty}\inf_λ\sup_{\operatorname {rank}(X)\leq r_n}\operatorname {MSE}(X_0,\hat{X}_λ)$ . Our formulas involve incomplete moments of the quarter- and semi-circle laws ( $β=1$ , square case) and the Marčenko-Pastur law ( $β<1$ , nonsquare case). For finite $m$ and $n$ , we show that MSE increases as the nonzero singular values of $X_0$ grow larger. As a result, the finite- $n$ worst-case MSE, a quantity which can be evaluated numerically, is achieved when the signal $X_0$ is "infinitely strong." The nuclear norm penalization problem is solved by applying soft thresholding to the singular values of $Y$ . We also derive the minimax threshold, namely the value $λ^*(ρ)$ , which is the optimal place to threshold the singular values. All these results are obtained for general (nonsquare, nonsymmetric) real matrices. Comparable results are obtained for square symmetric nonnegative-definite matrices.

preprint2014arXiv

The Optimal Hard Threshold for Singular Values is 4/sqrt(3)

We consider recovery of low-rank matrices from noisy data by hard thresholding of singular values, where singular values below a prescribed threshold $λ$ are set to 0. We study the asymptotic MSE in a framework where the matrix size is large compared to the rank of the matrix to be recovered, and the signal-to-noise ratio of the low-rank piece stays constant. The AMSE-optimal choice of hard threshold, in the case of n-by-n matrix in noise level σ, is simply $(4/\sqrt{3}) \sqrt{n}σ\approx 2.309 \sqrt{n}σ$ when $σ$ is known, or simply $2.858\cdot y_{med}$ when $σ$ is unknown, where $y_{med}$ is the median empirical singular value. For nonsquare $m$ by $n$ matrices with $m \neq n$ , these thresholding coefficients are replaced with different provided constants. In our asymptotic framework, this thresholding rule adapts to unknown rank and to unknown noise level in an optimal manner: it is always better than hard thresholding at any other value, no matter what the matrix is that we are trying to recover, and is always better than ideal Truncated SVD (TSVD), which truncates at the true rank of the low-rank matrix we are trying to recover. Hard thresholding at the recommended value to recover an n-by-n matrix of rank r guarantees an AMSE at most $3nrσ^2$ . In comparison, the guarantee provided by TSVD is $5nrσ^2$ , the guarantee provided by optimally tuned singular value soft thresholding is $6nrσ^2$ , and the best guarantee achievable by any shrinkage of the data singular values is $2nrσ^2$ . Empirical evidence shows that these AMSE properties of the $4/\sqrt{3}$ thresholding rule remain valid even for relatively small n, and that performance improvement over TSVD and other shrinkage rules is substantial, turning it into the practical hard threshold of choice.

preprint2013arXiv

The Maximum Entropy Relaxation Path

The relaxed maximum entropy problem is concerned with finding a probability distribution on a finite set that minimizes the relative entropy to a given prior distribution, while satisfying relaxed max-norm constraints with respect to a third observed multinomial distribution. We study the entire relaxation path for this problem in detail. We show existence and a geometric description of the relaxation path. Specifically, we show that the maximum entropy relaxation path admits a planar geometric description as an increasing, piecewise linear function in the inverse relaxation parameter. We derive fast algorithms for tracking the path. In various realistic settings, our algorithms require $O(n\log(n))$ operations for probability distributions on $n$ points, making it possible to handle large problems. Once the path has been recovered, we show that given a validation set, the family of admissible models is reduced from an infinite family to a small, discrete set. We demonstrate the merits of our approach in experiments with synthetic data and discuss its potential for the estimation of compact n-gram language models.

preprint2013arXiv

The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising

Let $X_0$ be an unknown $M$ by $N$ matrix. In matrix recovery, one takes $n < MN$ linear measurements $y_1,..., y_n$ of $X_0$ , where $y_i = \Tr(a_i^T X_0)$ and each $a_i$ is a $M$ by $N$ matrix. For measurement matrices with Gaussian i.i.d entries, it known that if $X_0$ is of low rank, it is recoverable from just a few measurements. A popular approach for matrix recovery is Nuclear Norm Minimization (NNM). Empirical work reveals a \emph{phase transition} curve, stated in terms of the undersampling fraction $δ(n,M,N) = n/(MN)$ , rank fraction $ρ=r/N$ and aspect ratio $β=M/N$ . Specifically, a curve $δ^* = δ^*(ρ;β)$ exists such that, if $δ> δ^*(ρ;β)$ , NNM typically succeeds, while if $δ< δ^*(ρ;β)$ , it typically fails. An apparently quite different problem is matrix denoising in Gaussian noise, where an unknown $M$ by $N$ matrix $X_0$ is to be estimated based on direct noisy measurements $Y = X_0 + Z$ , where the matrix $Z$ has iid Gaussian entries. It has been empirically observed that, if $X_0$ has low rank, it may be recovered quite accurately from the noisy measurement $Y$ . A popular matrix denoising scheme solves the unconstrained optimization problem $\text{min} \| Y - X \|_F^2/2 + λ\|X\|_*$ . When optimally tuned, this scheme achieves the asymptotic minimax MSE $\cM(ρ) = \lim_{N \goto \infty} \inf_λ\sup_{\rank(X) \leq ρ\cdot N} MSE(X,\hat{X}_λ)$. We report extensive experiments showing that the phase transition $δ^*(ρ)$ in the first problem coincides with the minimax risk curve $\cM(ρ)$ in the second problem, for {\em any} rank fraction $0 < ρ< 1$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.