Spectral embedding based on the Singular Value Decomposition (SVD) is a
widely used "preprocessing" step in many learning tasks, typically leading to
dimensionality reduction by projecting onto a number of dominant singular
vectors and rescaling the coordinate axes (by a predefined function of the
singular value). However, the number of such vectors required to capture
problem structure grows with problem size, and even partial SVD computation
becomes a bottleneck. In this paper, we propose a low-complexity it compressive
spectral embedding algorithm, which employs random projections and finite order
polynomial expansions to compute approximations to SVD-based embedding. For an
m times n matrix with T non-zeros, its time complexity is O((T+m+n)log(m+n)),
and the embedding dimension is O(log(m+n)), both of which are independent of
the number of singular vectors whose effect we wish to capture. To the best of
our knowledge, this is the first work to circumvent this dependence on the
number of singular vectors for general SVD-based embeddings. The key to
sidestepping the SVD is the observation that, for downstream inference tasks
such as clustering and classification, we are only interested in using the
resulting embedding to evaluate pairwise similarity metrics derived from the
euclidean norm, rather than capturing the effect of the underlying matrix on
arbitrary vectors as a partial SVD tries to do. Our numerical results on
network datasets demonstrate the efficacy of the proposed method, and motivate
further exploration of its application to large-scale inference tasks.

本文提出一种基于随机投影与有限阶多项式拓展计算奇异值分解嵌入的压缩光谱嵌入算法，其降维效果与计算复杂度不受特征向量数量影响。此算法对聚类和分类等下游推断任务的对比相似度度量具有较好效果。