REVIEW 3 major objections 4 minor 4 references
A Kaczmarz-Inspired Method for Orthogonalization
T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read A randomized pairwise projection procedure orthogonalizes any independent unit vectors almost surely, with O(n² log(1/(det(|A|)ε))) iterations to reach volume 1-ε.
desk verdict A clean potential-function analysis of a simple orthogonalization rule, but the printed Corollary 2.8 'In particular' misapplies the tail bound and controls the wrong event; the advertised rate is not proved as written, though the fix looks easy. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the potential $\Phi(A)=-\log\det(|A|)$, where $|A|=(A^*A)^{1/2}$; $\Phi=0$ exactly when the columns are orthonormal. One update multiplies $\det(|A|)$ by $\sqrt{1-|\langle a_i,a_j\rangle|^2}$, so $\Phi$ changes by $\tfrac12\log(1-|\langle a_i,a_j\rangle|^2)$. The proof combines this identity with an optimization lemma showing that the average squared overlap between distinct columns is at least $(1-\det(|A|)^2)/(n-1)^2$, giving the one-step drift bound $\mathbb{E}\Phi(A')\le f(\Phi(A))$ with $f(x)=x-(1-e^{-2x})/(2(n-1)^2)$. Monotonicity of $\Phi$ under every update, together with this drift, makes $\Phi(A_t)$ a supermartingale; hitting-time tail bounds convert the expected drift into the $O(n^2)$ iteration count.
What would settle it
Take $n=3$ and any invertible $3\times 3$ Gram matrix with unit diagonal; compute $P=\det(|A|)^2$ and compare the average of $|\langle a_i,a_j\rangle|^2$ over the six ordered pairs with $(1-P)/(n-1)^2=(1-P)/4$. If any configuration gives an average below that threshold, Lemma 2.2—and therefore the one-step drift bound—is false; this can be checked by random search over $3\times3$ correlation matrices.
Extended reading notes
Core claim
The paper's central claim is that the stochastic process $A_{t+1}=\mathrm{orth}(A_t,i_t,j_t)$, with $(i_t,j_t)$ sampled uniformly from ordered pairs of distinct indices, drives $\Phi(A_t)=-\log\det(|A_t|)$ to $0$ almost surely for every starting matrix with unit-length linearly independent columns. The quantitative form is a tail bound on $\Phi(A_t)$: the probability that it stays above a level $\beta$ decays exponentially in $t/((n-1)^2(\Phi(A)+e\lceil\log(1/\beta)\rceil))$, so after $\Theta(n^2\log(1/(\det(|A|)\varepsilon)))$ iterations $\det(|A_t|)\ge 1-\varepsilon$ with constant probability. Consequently the nonzero singular values of $A_t$ concentrate near $1$, and $A_t$ is within Frobenius distance $O(\sqrt{\varepsilon})$ of an orthonormal basis for its column space.
Load-bearing premise
The proof of the one-step drift relies on Lemma B.1, a claim justified only by a Lagrange-multiplier sketch: among $n$ nonnegative numbers with fixed sum and fixed product, the sum of squares $\sum x_i^2$ is minimized when $n-1$ of the numbers are equal and the remaining one is no larger; if that lemma fails, the expected-progress estimate and every iteration bound built on it fail.
Editorial extensions
If this is right
- Any starting configuration of $n$ linearly independent unit vectors converges almost surely to an orthonormal basis of its span, so the span is preserved exactly without a sequential orthogonalization pass.
- After $t=\Theta(n^2\log(1/(\det(|A|)\varepsilon)))$ iterations, $\det(|A_t|)\ge 1-\varepsilon$ with constant probability; by Facts 2.9–2.10 the nonzero singular values of $A_t$ lie in $[1-O(\sqrt{\varepsilon}),1+O(\sqrt{\varepsilon})]$ and $A_t$ is within Frobenius distance $O(\sqrt{\varepsilon})$ of an orthonormal basis for its column space.
- The potential $\Phi(A_t)$ decreases monotonically even when the pair is chosen adversarially, so every run improves the conditioning of the columns and the process can be stopped early as a preconditioner.
- The batched updates described in the appendix allow up to $O(n)$ pairwise orthogonalizations per round while preserving the same drift estimate, so the iteration bound carries over to parallel implementations.
Reading between the lines
- Because each update costs $O(d)$ and the number of updates depends on $\det(|A|)$, the practical crossover against the classical QR-based orthogonalization depends on how ill-conditioned the starting set is; the paper does not report wall-clock benchmarks, so that comparison is an open empirical question.
- The drift $f(x)$ is multiplicative for small $x$ and additive for large $x$, which suggests that a selection rule biased toward pairs with currently large overlap could accelerate the early phase; proving such an acceleration would require a different argument from the uniform-pair analysis.
- Lemma 2.1 holds for any pair of columns, so the monotonicity is robust to asynchronous or distributed update orders; the parallel-forest construction is one concrete way to exploit this, but other scheduling rules are not analyzed.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a randomized iterative procedure for orthogonalizing n linearly independent unit vectors in C^d while preserving their span: at each step, two distinct columns are chosen uniformly at random and one is replaced by its component perpendicular to the other, renormalized to unit length. The main quantity is Phi(A) = -log det(|A|), where |A|=(A*A)^{1/2}; the paper proves that Phi is pointwise nonincreasing under every step (Lemma 2.1), gives a one-step expected drift bound (Lemma 2.3), derives expectation and tail bounds for Phi(A_t) (Proposition 2.4, Corollary 2.8), and concludes that the determinant of |A_t| approaches 1. The abstract advertises that O(n^2 log(1/(det(|A|) epsilon))) iterations suffice to bring det(|A_t|) above 1-epsilon with constant probability. The individual lemmas are internally consistent and checkable, but the paper's stated derivation of the advertised iteration bound contains a genuine error in the 'In particular' paragraph of Corollary 2.8, which applies the beta<1 tail bound with beta=1+epsilon and controls the wrong event. The intended rate is recoverable by applying the tail bound with beta=-log(1-epsilon).
Significance. The algorithm itself is attractive: it is simple, parameter-free, span-preserving, and its analysis is based on an external geometric potential rather than fitted constants. Lemma 2.1 gives an exact identity for the determinant change, and the drift function f(x) is derived rather than chosen. The expected hitting-time argument in Lemmas 2.5-2.7 is a clean and reusable mechanism, and the paper correctly identifies the relationship between Phi and other orthogonality measures in Facts 2.9 and 2.10. If the tail-bound application is corrected, the paper would establish a quantitative convergence rate matching the abstract's claim. However, as printed the central rate claim is not supported by the proved statements, because the specific substitution in Corollary 2.8 violates the corollary's hypothesis and the event controlled is not the complement of the determinant target. The gap is localized and repairable, so the contribution is promising but requires a substantive revision.
major comments (3)
- [Corollary 2.8, final paragraph] The advertised iteration bound does not follow from the proved results. The corollary's hypothesis requires beta<1, but the 'In particular' paragraph applies the bound with beta=1+epsilon>1. Moreover, the event controlled, Phi(A_t) >= 1+epsilon, is not the complement of the abstract's target det(|A_t|)>1-epsilon. To bound the failure event det(|A_t|) <= 1-epsilon one must control Phi(A_t) >= -log(1-epsilon), i.e. beta=-log(1-epsilon). With this substitution the proof does yield t = O(n^2 (log(1/det(|A|)) + log(1/epsilon)) log(1/delta)) iterations for Pr(Phi(A_t) >= -log(1-epsilon)) <= delta, which matches the abstract's rate; but as printed the central claim is unsupported. The error is not a harmless typo, since the tail bound becomes harder as beta decreases and beta=1+epsilon is in the opposite regime.
- [Appendix B, Lemma B.1] Lemma B.1 underpins Lemma 2.2's lower bound on the expected progress, and hence all subsequent iteration bounds, but its proof is only a sketch. The sentence 'Using Lagrange multipliers, one can see' does not by itself establish that the critical point with two distinct values is the global minimizer, and the final step 'In particular, we must have b=y1<=y2=...=yn=a' requires ruling out boundary cases and configurations in which more than one coordinate is small. The claim is standard and likely correct, but since it is load-bearing, the proof should be completed or replaced with a reference.
- [Abstract and Section 2.2] The abstract and introduction assert almost-sure convergence to an orthonormal basis of the span, but the body does not state or prove this as a named theorem. The claim does follow from Lemma 2.6, because for every beta>0 the expected hitting time of {Phi < beta} is finite and hence the hitting time is almost surely finite, giving Phi(A_t) -> 0 almost surely by monotonicity. Please make this derivation explicit so that the abstract's main qualitative claim is formally supported.
minor comments (4)
- [Corollary 2.8, final paragraph] After correcting the beta substitution, please re-derive the displayed threshold for t and the constant involving 2 log(4/epsilon); the current display appears tied to the incorrect event Phi >= 1+epsilon.
- [Appendix A, Eq. (25)] The sentence 'Replacing the result of Lemma 2.3 with (25) allows the subsequent proofs to go through' should be expanded, because the later bounds in Lemma 2.7 use the specific form of f from Lemma 2.3, and the batched drift function f_t has different constants.
- [Section 2.3, Fact 2.10] The reduction to upper triangular form should explicitly note that left multiplication by a unitary matrix does not change the singular values of A, hence does not change Phi(A).
- [Throughout] The phrase 'constant probability' in the abstract should be clarified: the body provides a bound with an explicit delta and a factor log(1/delta), so the statement should specify that delta is held fixed.
Circularity Check
No significant circularity: the drift and tail bounds are derived from the determinant potential, with no fitted parameters and no load-bearing self-citation.
full rationale
The paper's derivation chain is self-contained and non-circular. The potential Phi(A) = -log det(|A|) is an external geometric measure of orthogonality, and the one-step drift f(x) = x - (1 - exp(-2x))/(2(n-1)^2) is derived from Lemma 2.1's exact determinant identity and Lemma 2.2's constrained optimization over singular values, not chosen to match a target output. Lemma B.1, despite its sketched Lagrange-multiplier proof, is a standard optimization claim and is not assumed from prior work or from the desired convergence statement. The probabilistic arguments in Proposition 2.4 and Lemmas 2.5-2.7 use only the established supermartingale-type drift and Markov/telescoping arguments; no parameter is fitted to a subset of data and then renamed a prediction. The only related works cited, by Steinerberger and Strohmer-Vershynin, are context and are explicitly stated to be independent; they are not load-bearing for the main theorem. The identified weakness in Corollary 2.8 -- applying a tail bound stated for beta < 1 to beta = 1+epsilon and equating Phi >= 1+epsilon with the failure event for det(|A_t|) > 1-epsilon -- is a genuine correctness gap in the printed claim, but it is not circularity: the tail bound is derived from the drift estimate rather than assumed from the conclusion. Likewise, Lemma B.1's abbreviated proof affects rigor, not circularity. Therefore the paper receives score 0.
Assumptions & free parameters
assumptions (4)
- standard math The squared singular values of a matrix with unit-length columns are nonnegative, sum to n, and their product equals det(|A|)^2 (spectral theorem).
- standard math The minimizer of Σx_i^2 subject to fixed sum and product of squared singular values is of the form (b,a,...,a) with b ≤ 1 ≤ a (Lemma B.1).
- domain assumption The columns of A are unit length and linearly independent, and this property is preserved by the orth update.
- domain assumption Pairs (i,j) are sampled uniformly from ordered distinct pairs at each step.
Cite this review
Pith. "Pith review of A Kaczmarz-Inspired Method for Orthogonalization." pith.science (2026). https://pith.science/paper/JQG7KZUG
@misc{pith2026241116101,
author = {Pith},
title = {Pith review of: A Kaczmarz-Inspired Method for Orthogonalization},
year = {2026},
howpublished = {\url{https://pith.science/paper/JQG7KZUG}},
note = {Machine review of arXiv:2411.16101}
}
abstract
This paper asks if the following iterative procedure approximately orthogonalizes a set of $n$ linearly independent unit vectors while preserving their span: in each iteration, access a random pair of vectors and replace one with the component perpendicular to the other, renormalized to be a unit vector. We provide a positive answer: any given set of starting vectors converges almost surely to an orthonormal basis of their span. We specifically argue that the $n$-volume of the parallelepiped generated by the vectors approaches 1 (i.e. the parallelepiped approaches a hypercube). If $A$ is the matrix formed by taking these vectors as columns, this volume is simply $\det(|A|)$ where $|A|=(A^*A)^{1/2}$. We show that $O(n^2\log(1/(\det(|A|)\varepsilon)))$ iterations suffice to bring ${\det(|A|)}$ above $1-\varepsilon$ with constant probability.
Reference graph
Works this paper leans on
-
[1]
Sample a uniformly random forest consisting of a single edge
-
[2]
Sample a uniformly random perfect matching of the complete grap h and flip a coin to orient each edge
-
[3]
Sample a uniformly random permutation π : [ n]→ [n] and consider the path with edges ( it, jt) = (π(t), π(t + 1)) for t∈ [n− 1]
-
[4]
10 B Proof of claim in Lemma 2.2 Lemma B.1
Sample a uniformly random vertex and consider the star graph ro oted and centered at that selected vertex. 10 B Proof of claim in Lemma 2.2 Lemma B.1. If the program xj≥ 0 & ∑ j∈[n] xj = S & ∏ j∈[n] xj = P is feasible, then the minimizer of the objective ∑ j∈[n] x2 j occurs for xπ(1)≤ xπ(2) =··· = xπ(n) for some permutation π. Proof. Let y1, . . . , yn be...
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.