cicyt UNIZAR
Full-text links:

Download:

Current browse context:

cs.DS

Change to browse by:

References & Citations

DBLP - CS Bibliography

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo ScienceWISE logo

Computer Science > Data Structures and Algorithms

Title: Leveraging Sparsity to Speed Up Polynomial Feature Expansions of CSR Matrices Using $K$-Simplex Numbers

Abstract: We provide an algorithm that speeds up polynomial and interaction feature expansion on sparse matrices. The algorithm operates on and produces a compressed sparse row matrix with no densification. It works by defining a bijective function involving simplex numbers of column indices in the original matrix to column indices in the expanded matrix. This function allows for only the nonzero elements to be iterated over and multiplied together, greatly improving the expansion of sparse matrices in compressed sparse row format. For a vector of dimension $D$ and density $0 \le d \le 1$, the algorithm has time complexity $\Theta(d^KD^K)$ where $K$ is the polynomial-feature order; this is an improvement by a factor $d^K$ over the standard method.
Comments: 7 pages, 2 figures
Subjects: Data Structures and Algorithms (cs.DS); Numerical Analysis (cs.NA)
Cite as: arXiv:1803.06418 [cs.DS]
  (or arXiv:1803.06418v1 [cs.DS] for this version)

Submission history

From: Andrew Nystrom [view email]
[v1] Fri, 16 Mar 2018 22:24:32 GMT (220kb,D)