random-projection-complexity-dense
IN premise — summaries/2026/08/24/wiki-Random_projection.md
Created 2026-08-25T02:58:51+00:00
Computing a random projection of dense data has complexity O(d·k·N), and for sparse data with c nonzeros per column it reduces to O(c·k·N).
Summary
When you shrink a large dataset using a random projection, the work scales with the number of features you have, how much you're shrinking to, and how many samples you're processing. The key takeaway is that if the data is sparse (mostly zeros), you only pay for the non-zero entries, so the computation cost drops proportionally — meaning systems working with sparse representations get a real speed advantage over dense ones.