Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
For researchers in fast matrix multiplication, this work corrects a flawed proof and provides a conservative AMM framework with exactness guarantees on chosen subspaces, though the result is incremental as it builds on existing AMM techniques.
The paper withdraws an earlier claim of exact near-quadratic dense matrix multiplication via Graded Projection Recursion (GPR), identifying a fundamental obstruction involving an equality filter. It replaces this with a conservative approximate matrix multiplication (AMM) framework that computes low-rank parts exactly and applies unbiased AMM only to the residual, preserving exactness on protected subspaces.
Earlier versions proposed Graded Projection Recursion (GPR) as a deterministic packed-recursion framework for model-honest near-quadratic dense matrix multiplication. This revised version withdraws the exact dense matrix multiplication theorem and the downstream consequences that depended on it with a conservative AMM framework. The local ingredients remain useful as local tools: the three-band packing identity, scaled middle-band extraction under certified gaps, centering and reconstruction identities, and row/column normalization bounds. The gap in the earlier argument is global: the proof relied on a bounded active-state realization that would remove first-mismatch terms through the recursion. For arbitrary dense inputs this would require an exact equality filter over the inner index. We formulate this obstruction as a target-slice/equality-filter problem and give a rank/capacity argument against the natural separable active-state realization. The positive replacement is a conservative approximate matrix multiplication framework. For chosen protected left and right query subspaces, the low/marginal part of AB is computed exactly and an unbiased AMM primitive is applied only to the high/high residual. The resulting estimator is unbiased, preserves protected queries exactly in every realization, localizes stochastic error to the residual subspace, and inherits residual output-norm or query-risk guarantees from the underlying estimator.