  The Johnson--Lindenstrauss (JL) lemma is a powerful tool for dimensionality
reduction in modern algorithm design. The lemma states that any set of
high-dimensional points in a Euclidean space can be flattened to lower
dimensions while approximately preserving pairwise Euclidean distances. Random
matrices satisfying this lemma are called JL transforms (JLTs). Inspired by
existing $s$-hashing JLTs with exactly $s$ nonzero elements on each column, the
present work introduces an ensemble of sparse matrices encompassing so-called
$s$-hashing-like matrices whose expected number of nonzero elements on each
column is~$s$. The independence of the sub-Gaussian entries of these matrices
and the knowledge of their exact distribution play an important role in their
analyses. Using properties of independent sub-Gaussian random variables, these
matrices are demonstrated to be JLTs, and their smallest and largest singular
values are estimated non-asymptotically using a technique from geometric
functional analysis. As the dimensions of the matrix grow to infinity, these
singular values are proved to converge almost surely to fixed quantities (by
using the universal Bai--Yin law), and in distribution to the Gaussian
orthogonal ensemble (GOE) Tracy--Widom law after proper rescalings.
Understanding the behaviors of extreme singular values is important in general
because they are often used to define a measure of stability of matrix
algorithms. For example, JLTs were recently used in derivative-free
optimization algorithmic frameworks to select random subspaces in which are
constructed random models or poll directions to achieve scalability, whence
estimating their smallest singular value in particular helps determine the
dimension of these subspaces.
