undefined | Better HN

0 pointsfc417fc8021mo ago0 comments

It looks nice! Fair enough about QJL - it seems to be nothing more than an unbiasing measure anyway.

I'm not sure if it's my own misunderstanding or if the paper [0] has something of an error. Section 3.1 starts out to the effect "let x be on the unit hypersphere" (but I'm fairly certain it's actually not). Neither algorithm 1 nor algorithm 2 show a normalization step prior to rotating x. Algorithm 2 line 8 shows that the scalar returned is actually the magnitude of the residual without accounting for QJL.

Anyway I'm pretty sure the authors inadvertently omitted that detail which really had me confused for a while there.

[0] https://arxiv.org/abs/2504.19874

0 comments

mesuvash1mo ago

IIUC, The paper's notation S^(d-1) means the unit sphere in R^d (e.g., the familiar unit circle is S^1 living in R^2). So, i think, x in the algorithm is already a unit vector.

Reference: Section 2:Preliminaries ... We use the notation S^d−1 to denote the hypersphere in R^d of radius 1.

Section 3.1 Let x ∈ S^d−1 be a (worst-case) vector on the unit sphere in dimension d.

fc417fc802OP1mo ago

Right but in reality IIUC w ∈ R^d and it's x = w / ||w|| ∈ S^(d-1) and then given r = x - Qmse^-1( Qmse( x ) ) the scalar you use is derived as ||r|| (I'm missing a couple subscript twos there I think).

I was primarily aiming to confirm my understanding given the author's omission but also the scalar is subtly different than in your linked explanation (although conceptually equivalent).

j / k navigate · click thread line to collapse