Luis Rademacher

NeurIPS Conference 2024 Conference Paper

Euclidean distance compression via deep random features

• Brett Leroux
• Luis Rademacher

Motivated by the problem of compressing point sets into as few bits as possible while maintaining information about approximate distances between points, we construct random nonlinear maps $\varphi_\ell$ that compress point sets in the following way. For a point set $S$, the map $\varphi_\ell: \mathbb{R}^d \to N^{-1/2}\{-1, 1\}^N$ has the property that storing $\varphi_\ell(S)$ (a sketch of $S$) allows one to report squared distances between points up to some multiplicative $(1\pm \epsilon)$ error with high probability. The maps $\varphi_\ell$ are the $\ell$-fold composition of a certain type of random feature mapping. Compared to existing techniques, our maps offer several advantages. The standard method for compressing point sets by random mappings relies on the Johnson-Lindenstrauss lemma and involves compressing point sets with a random linear map. The main advantage of our maps $\varphi_\ell$ over random linear maps is that ours map point sets directly into the discrete cube $N^{-1/2}\{-1, 1\}^N$ and so there is no additional step needed to convert the sketch to bits. For some range of parameters, our maps $\varphi_\ell$ produce sketches using fewer bits of storage space. We validate the method with experiments, including an application to nearest neighbor search.

SODA Conference 2020 Conference Paper

Efficiency of the floating body as a robust measure of dispersion

• Joseph Anderson
• Luis Rademacher

STOC Conference 2018 Conference Paper

The minimum euclidean-norm point in a convex polytope: Wolfe's combinatorial algorithm is exponential

• Jesús A. De Loera
• Jamie Haddock
• Luis Rademacher

The complexity of Philip Wolfe’s method for the minimum Euclidean-norm point problem over a convex polytope has remained unknown since he proposed the method in 1974. We present the first example that Wolfe’s method takes exponential time. Additionally, we improve previous results to show that linear programming reduces in strongly-polynomial time to the minimum norm point problem over a simplex

AAAI Conference 2017 Conference Paper

Heavy-Tailed Analogues of the Covariance Matrix for ICA

• Joseph Anderson
• Navin Goyal
• Anupama Nandi
• Luis Rademacher

Independent Component Analysis (ICA) is the problem of learning a square matrix A, given samples of X = AS, where S is a random vector with independent coordinates. Most existing algorithms are provably efficient only when each Si has finite and moderately valued fourth moment. However, there are practical applications where this assumption need not be true, such as speech and finance. Algorithms have been proposed for heavy-tailed ICA, but they are not practical, using random walks and the full power of the ellipsoid algorithm multiple times. The main contributions of this paper are: (1) A practical algorithm for heavy-tailed ICA that we call HTICA. We provide theoretical guarantees and show that it outperforms other algorithms in some heavy-tailed regimes, both on real and synthetic data. Like the current state-of-theart, the new algorithm is based on the centroid body (a first moment analogue of the covariance matrix). Unlike the stateof-the-art, our algorithm is practically efficient. To achieve this, we use explicit analytic representations of the centroid body, which bypasses the use of the ellipsoid method and random walks. (2) We study how heavy tails affect different ICA algorithms, including HTICA. Somewhat surprisingly, we show that some algorithms that use the covariance matrix or higher moments can successfully solve a range of ICA instances with infinite second moment. We study this theoretically and experimentally, with both synthetic and real-world heavy-tailed data.

AAAI Conference 2016 Conference Paper

The Hidden Convexity of Spectral Clustering

• James Voss
• Mikhail Belkin
• Luis Rademacher

In recent years, spectral clustering has become a standard method for data analysis used in a broad range of applications. In this paper we propose a new class of algorithms for multiway spectral clustering based on optimization of a certain “contrast function” over the unit sphere. These algorithms, partly inspired by certain Indepenent Component Analysis techniques, are simple, easy to implement and efficient. Geometrically, the proposed algorithms can be interpreted as hidden basis recovery by means of function optimization. We give a complete characterization of the contrast functions admissible for provable basis recovery. We show how these conditions can be interpreted as a “hidden convexity” of our optimization problem on the sphere; interestingly, we use ef- ficient convex maximization rather than the more common convex minimization. We also show encouraging experimental results on real and simulated data.

NeurIPS Conference 2015 Conference Paper

A Pseudo-Euclidean Iteration for Optimal Recovery in Noisy ICA

• James Voss
• Mikhail Belkin
• Luis Rademacher

Independent Component Analysis (ICA) is a popular model for blind signal separation. The ICA model assumes that a number of independent source signals are linearly mixed to form the observed signals. We propose a new algorithm, PEGI (for pseudo-Euclidean Gradient Iteration), for provable model recovery for ICA with Gaussian noise. The main technical innovation of the algorithm is to use a fixed point iteration in a pseudo-Euclidean (indefinite “inner product”) space. The use of this indefinite “inner product” resolves technical issues common to several existing algorithms for noisy ICA. This leads to an algorithm which is conceptually simple, efficient and accurate in testing. Our second contribution is combining PEGI with the analysis of objectives for optimal recovery in the noisy ICA model. It has been observed that the direct approach of demixing with the inverse of the mixing matrix is suboptimal for signal recovery in terms of the natural Signal to Interference plus Noise Ratio (SINR) criterion. There have been several partial solutions proposed in the ICA literature. It turns out that any solution to the mixing matrix reconstruction problem can be used to construct an SINR-optimal ICA demixing, despite the fact that SINR itself cannot be computed from data. That allows us to obtain a practical and provably SINR-optimal recovery method for ICA with arbitrary Gaussian noise.

FOCS Conference 2015 Conference Paper

Heavy-Tailed Independent Component Analysis

• Joseph Anderson
• Navin Goyal
• Anupama Nandi
• Luis Rademacher

Independent component analysis (ICA) is the problem of efficiently recovering a matrix A ∈ ℝ n×n from i. i. d. Observations of X=AS where S ∈ ℝ n is a random vector with mutually independent coordinates. This problem has been intensively studied, but all existing efficient algorithms with provable guarantees require that the coordinates Si have finite fourth moments. We consider the heavy-tailed ICA problem where we do not make this assumption, about the second moment. This problem also has received considerable attention in the applied literature. In the present work, we first give a provably efficient algorithm that works under the assumption that for constant γ > 0, each S i has finite (1+γ)-moment, thus substantially weakening the moment requirement condition for the ICA problem to be solvable. We then give an algorithm that works under the assumption that matrix A has orthogonal columns but requires no moment assumptions. Our techniques draw ideas from convex geometry and exploit standard properties of the multivariate spherical Gaussian distribution in a novel way.

NeurIPS Conference 2013 Conference Paper

Fast Algorithms for Gaussian Noise Invariant Independent Component Analysis

• James Voss
• Luis Rademacher
• Mikhail Belkin

The performance of standard algorithms for Independent Component Analysis quickly deteriorates under the addition of Gaussian noise. This is partially due to a common first step that typically consists of whitening, i. e. , applying Principal Component Analysis (PCA) and rescaling the components to have identity covariance, which is not invariant under Gaussian noise. In our paper we develop the first practical algorithm for Independent Component Analysis that is provably invariant under Gaussian noise. The two main contributions of this work are as follows: 1. We develop and implement a more efficient version of a Gaussian noise invariant decorrelation (quasi-orthogonalization) algorithm using Hessians of the cumulant functions. 2. We propose a very simple and efficient fixed-point GI-ICA (Gradient Iteration ICA) algorithm, which is compatible with quasi-orthogonalization, as well as with the usual PCA-based whitening in the noiseless case. The algorithm is based on a special form of gradient iteration (different from gradient descent). We provide an analysis of our algorithm demonstrating fast convergence following from the basic properties of cumulants. We also present a number of experimental comparisons with the existing methods, showing superior results on noisy data and very competitive performance in the noiseless case.

FOCS Conference 2010 Conference Paper

Efficient Volume Sampling for Row/Column Subset Selection

• Amit Deshpande 0001
• Luis Rademacher

We give efficient algorithms for volume sampling, i. e. , for picking k-subsets of the rows of any given matrix with probabilities proportional to the squared volumes of the simplices defined by them and the origin (or the squared volumes of the parallelepipeds defined by these subsets of rows). This solves an open problem from the monograph on spectral algorithms by Kannan and Vempala (see Section 7. 4 of [15], also implicit in [1], [5]). Our first algorithm for volume sampling k-subsets of rows from an m-by-n matrix runs in O(kmn ω log n) arithmetic operations (where ω is the exponent of matrix multiplication) and a second variant of it for (1 + ϵ)-approximate volume sampling runs in O(mn log m · k 2 /ϵ 2 +m log ω m · k 2ω+1 /ϵ 2ω · log(kϵ -1 log m)) arithmetic operations, which is almost linear in the size of the input (i. e. , the number of entries) for small k. Our efficient volume sampling algorithms imply the following results for low-rank matrix approximation: 1) Given A ∈ R m×n, in O(kmn ω log n) arithmetic operations we can find k of its rows such that projecting onto their span gives a √k + 1-approximation to the matrix of rank fc closest to A under the Frobenius norm. This improves the O(k√log k)-approximation of Boutsidis, Drineas and Mahoney [1] and matches the lower bound shown in [5]. The method of conditional expectations gives a deterministic algorithm with the same complexity. The running time can be improved to O(mn log m · k 2 /e 2 + m log ω m·k 2ω+1 ϵ 2ω -log(kϵ -1 log m)) at the cost of losing an extra (1 + ϵ) in the approximation factor. 2) The same rows and projection as in the previous point give a √(k + 1)(n -k)-approximation to the matrix of rank k closest to A under the spectral norm. In this paper, we show an almost matching lower bound of √n, even for k = 1.

SODA Conference 2009 Conference Paper

Expanders via random spanning trees

• Navin Goyal
• Luis Rademacher
• Santosh S. Vempala

FOCS Conference 2006 Conference Paper

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

• Luis Rademacher
• Santosh S. Vempala

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume algorithms for convex bodies in Ropf n (the current best algorithm has complexity roughly n 4, conjectured to be n 3 ). Our main tools, dispersion of random determinants and dispersion of the length of a random point from a convex body, are of independent interest and applicable more generally; in particular, the latter is closely related to the variance hypothesis from convex geometry. This geometric dispersion also leads to lower bounds for matrix problems and property testing

SODA Conference 2006 Conference Paper

Matrix approximation and projective clustering via volume sampling

• Amit Deshpande 0001
• Luis Rademacher
• Santosh S. Vempala
• Grant Wang