Let $\Phi\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}}_\Phi \sup_{x\in T} \left|\|\Phi x\|_2^2 - 1
\right| < \varepsilon , $$ i.e. so that $\Phi$ preserves the norm of every
$x\in T$ simultaneously and multiplicatively up to $1+\varepsilon$. We
introduce a new complexity parameter, which depends on the geometry of $T$, and
show that it suffices to choose $s$ and $m$ such that this parameter is small.
Our result is a sparse analog of Gordon's theorem, which was concerned with a
dense $\Phi$ having i.i.d. Gaussian entries. We qualitatively unify several
results related to the Johnson-Lindenstrauss lemma, subspace embeddings, and
Fourier-based restricted isometries. Our work also implies new results in using
the sparse Johnson-Lindenstrauss transform in numerical linear algebra,
classical and model-based compressed sensing, manifold learning, and
constrained least squares problems such as the Lasso.

研究了一个基于稀疏 Johnson-Lindenstrauss 变换的几何设置，它在 T 上保存每个 x 的范数，从而推导出一种关于几何复杂度的新参数，并且该参数可以帮助限制需要 M、S 的大小。这一结果是 Gordon 定理的稀疏模拟，并且该方法可应用于经典和基于模型的压缩感知、流形学习和约束最小二乘问题等领域。

欧几里德空间稀疏降维统一理论探索

Toward a unified theory of sparse dimensionality reduction in Euclidean  space

Suppose that party A collects private information about its users, where each
user's data is represented as a bit vector. Suppose that party B has a
proprietary data mining algorithm that requires estimating the distance between
users, such as clustering or nearest neighbors. We ask if it is possible for
party A to publish some information about each user so that B can estimate the
distance between users without being able to infer any private bit of a user.
Our method involves projecting each user's representation into a random,
lower-dimensional space via a sparse Johnson-Lindenstrauss transform and then
adding Gaussian noise to each entry of the lower-dimensional representation. We
show that the method preserves differential privacy---where the more privacy is
desired, the larger the variance of the Gaussian noise. Further, we show how to
approximate the true distances between users via only the lower-dimensional,
perturbed data. Finally, we consider other perturbation methods such as
randomized response and draw comparisons to sketch-based methods. While the
goal of releasing user-specific data to third parties is more broad than
preserving distances, this work shows that distance computations with privacy
is an achievable goal.

通过使用稀疏约翰逊 - 林登斯特劳斯变换和高斯噪声对低维用户表示进行发布，以实现差分隐私，并利用这些数据来计算用户之间的距离。

通过约翰逊 - 林登斯特劳斯变换实现隐私保护

Privacy via the Johnson-Lindenstrauss Transform

Recent work of [Dasgupta-Kumar-Sarlos, STOC 2010] gave a sparse
Johnson-Lindenstrauss transform and left as a main open question whether their
construction could be efficiently derandomized. We answer their question
affirmatively by giving an alternative proof of their result requiring only
bounded independence hash functions. Furthermore, the sparsity bound obtained
in our proof is improved. The main ingredient in our proof is a spectral moment
bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson,
FOCS 2010].

本文提出一种替代方法，利用有界独立哈希函数和谱矩估计性质，对 Dasgupta-Kumar-Sarlos (STOC 2010) 提出的基于稀疏 Johnson-Lindenstrauss 变换的深入研究，并得到了更好的稀疏限制。