arXiv research

Let $Φ\in\mathbb{R}^{m\times n}$ be a sparse Johnson-Lindenstrauss transform [KN14] with $s$ non-zeroes per column. For a subset $T$ of the unit sphere, $\varepsilon\in(0,1/2)$ given, we study settings for $m,s$ required to ensure $\mathop{\mathbb{E}}_Φ\sup_{x\in T} \left|\|Φx\|_2^2 - 1 \right| < \varepsilon ,$ i.e…

A new method for private query release using Johnson-Lindenstrauss projection.

Novel privatization framework for high-dimensional variable selection with differential privacy.

Tensorized Rademacher projections outperform Gaussian projections in reducing tensor dimensions.

Principal Components Regression (PCR) is a traditional tool for dimension reduction in linear regression that has been both criticized and defended. One concern about PCR is that obtaining the leading principal components tends to be computationally demanding for large data sets. While random projections do not possess…

The paper studies how norms of random vectors are preserved by random projections.

Unified analysis simplifies Johnson-Lindenstrauss lemma for data reduction.

In this paper, we study a fast approximation method for {\it large-scale high-dimensional} sparse least-squares regression problem by exploiting the Johnson-Lindenstrauss (JL) transforms, which embed a set of high-dimensional vectors into a low-dimensional space. In particular, we propose to apply the JL transforms to …

We present a theory for Euclidean dimensionality reduction with subgaussian matrices which unifies several restricted isometry property and Johnson-Lindenstrauss type results obtained earlier for specific data sets. In particular, we recover and, in several cases, improve results for sets of sparse and structured spars…

A fast binary embedding method preserves Euclidean distances in high-dimensional data.

This paper surveys various methods for dimensionality reduction and nearest neighbor search.

Optimization can learn Johnson-Lindenstrauss embeddings without randomization.

We examine a class of embeddings based on structured random matrices with orthogonal rows which can be applied in many machine learning applications including dimensionality reduction and kernel approximation. For both the Johnson-Lindenstrauss transform and the angular kernel, we show that we can select matrices yield…

This paper deals with two related problems, namely distance-preserving binary embeddings and quantization for compressed sensing . First, we propose fast methods to replace points from a subset $\mathcal{X} \subset \mathbb{R}^n$, associated with the Euclidean metric, with points in the cube $\{\pm 1\}^m$ and we associa…

Randomized matrix compression techniques, such as the Johnson-Lindenstrauss transform, have emerged as an effective and practical way for solving large-scale problems efficiently. With a focus on computational efficiency, however, forsaking solutions quality and accuracy becomes the trade-off. In this paper, we investi…

We develop a probabilistic framework for sequential random projection.

We present a new paradigm for speeding up randomized computations of several frequently used functions in machine learning. In particular, our paradigm can be applied for improving computations of kernels based on random embeddings. Above that, the presented framework covers multivariate randomized functions. As a bypr…

Random projections help in representing sparse graphs efficiently.

New algorithm speeds up regression tasks for large datasets.

The Johnson-Lindenstrauss Lemma allows for the projection of $n$ points in $p-$dimensional Euclidean space onto a $k-$dimensional Euclidean space, with $k \ge \frac{24\ln \emph{n}}{3ε^2-2ε^3}$, so that the pairwise distances are preserved within a factor of $1\pmε$. Here, working directly with the distributions of the …

HD-BWDM improves clustering validation in high-dimensional data.

We consider the problem of efficient randomized dimensionality reduction with norm-preservation guarantees. Specifically we prove data-dependent Johnson-Lindenstrauss-type geometry preservation guarantees for Ho's random subspace method: When data satisfy a mild regularity condition -- the extent of which can be estima…

The paper examines how well node similarities are preserved by random projections in graph embeddings.

Tensorized random projections reduce high-dimensional tensor size efficiently.

Aggregates predictions from multiple regression models using random projections and kernel methods.

In this paper we show that the computational complexity of the Iterative Thresholding and K-residual-Means (ITKrM) algorithm for dictionary learning can be significantly reduced by using dimensionality-reduction techniques based on the Johnson-Lindenstrauss lemma. The dimensionality reduction is efficiently carried out…

This work improves tensor decomposition methods, especially for large datasets.

Optimizes embedding accuracy for data variance and error.

A new method uses matrix sketches for efficient graph clustering in dynamic environments.

We provide fast algorithms for overconstrained $\ell_p$ regression and related problems: for an $n\times d$ input matrix $A$ and vector $b\in\mathbb{R}^n$, in $O(nd\log n)$ time we reduce the problem $\min_{x\in\mathbb{R}^d} \|Ax-b\|_p$ to the same problem with input matrix $\tilde A$ of dimension $s \times d$ and corr…

Unified bounds for sketched bilinear forms in machine learning and statistics.

Corrects bias in random sampling matrices for improved ML methods.

Feature hashing and other random projection schemes are commonly used to reduce the dimensionality of feature vectors. The goal is to efficiently project a high-dimensional feature vector living in $\mathbb{R}^n$ into a much lower-dimensional space $\mathbb{R}^m$, while approximately preserving Euclidean norm. These sc…

Derandomization reveals structure in neural networks, reducing sample complexity.

New faster, space-saving methods for subspace embeddings in tensors.

Sparse butterfly network replaces dense layers in neural networks, improving expressibility and performance.

We introduce sparse random projection, an important dimension-reduction tool from machine learning, for the estimation of discrete-choice models with high-dimensional choice sets. Initially, high-dimensional data are compressed into a lower-dimensional Euclidean space using random projections. Subsequently, estimation …

Union of Subspaces (UoS) is a popular model to describe the underlying low-dimensional structure of data. The fine details of UoS structure can be described in terms of canonical angles (also known as principal angles) between subspaces, which is a well-known characterization for relative subspace positions. In this pa…

We study the $k$-median clustering problem for high-dimensional polygonal curves with finite but unbounded number of vertices. We tackle the computational issue that arises from the high number of dimensions by defining a Johnson-Lindenstrauss projection for polygonal curves. We analyze the resulting error in terms of …

Neural networks approximate high-dimensional functions better than theory predicts.

For various applications, the relations between the dependent and independent variables are highly nonlinear. Consequently, for large scale complex problems, neural networks and regression trees are commonly preferred over linear models such as Lasso. This work proposes learning the feature nonlinearities by binning fe…

Let $\varepsilon\in(0,1)$ and $X\subset\mathbb R^d$ be arbitrary with $|X|$ having size $n>1$. The Johnson-Lindenstrauss lemma states there exists $f:X\rightarrow\mathbb R^m$ with $m = O(\varepsilon^{-2}\log n)$ such that $\forall x\in X\ \forall y\in X, \|x-y\|_2 \le \|f(x)-f(y)\|_2 \le (1+\varepsilon)\|x-y\|_2 .$…

We develop a novel methodology based on the marriage between the Bhattacharyya distance, a measure of similarity across distributions of random variables, and the Johnson-Lindenstrauss Lemma, a technique for dimension reduction. The resulting technique is a simple yet powerful tool that allows comparisons between data-…

New bounds on random quadratic forms hold under dependence, useful for adaptive modeling.

From a fresh data science perspective, this thesis discusses the prediction of coronary artery disease based on genetic variations at the DNA base pair level, called Single-Nucleotide Polymorphisms (SNPs), collected from the Ontario Heart Genomics Study (OHGS). First, the thesis explains two commonly used supervised le…

The main contribution of the paper is to show that Gaussian sketching of a kernel-Gram matrix $\boldsymbol K$ yields an operator whose counterpart in an RKHS $\mathcal H$, is a \emph{random projection} operator---in the spirit of Johnson-Lindenstrauss (J-L) lemma. To be precise, given a random matrix $Z$ with i.i.d. Ga…

New method preserves distances in time series data.

New method for computing terminal embeddings in sublinear time.