Module subspace_embedding 

Subspace embedding methods for dimensionality-reduced optimization.

Uses random projections (Johnson-Lindenstrauss lemma) to reduce the dimension of large optimization problems. Three projection families are supported:

• Gaussian random projection (i.i.d. N(0, 1/k) entries).
• Sparse random projection (Achlioptas 2003: entries ±√(3/k) with probability 1/6 each, 0 with probability 2/3).
• Fast JL (placeholder backed by the Gaussian construction; a full SRHT implementation can be substituted without changing the public API).

The module also exposes sketched_least_squares, a one-shot sketching solver for overdetermined systems min ||Ax - b||².

References

• Johnson, W.B. & Lindenstrauss, J. (1984). Extensions of Lipschitz mappings.
• Achlioptas, D. (2003). Database-friendly random projections. JCSS 66(4).
• Mahoney, M.W. (2011). Randomized algorithms for matrices and data. Found. Trends.

Structs

SubspaceEmbedding

A random subspace embedding S: R^n → R^k (k × n projection matrix).

SubspaceEmbeddingConfig

Configuration for a subspace embedding.

Enums

EmbeddingType

Random projection embedding methods.

Functions

sketched_least_squares

Sketched least-squares solver for overdetermined systems min ||Ax − b||².