The projective residual update (PRU) is an approximate data deletion method that projects the exact parameter update vector onto the subspace spanned by the deleted data points. It achieves O(k²d) computational cost — linear in the feature dimension d and independent of dataset size n — making it the most efficient deletion method for high-dimensional data with small deletion batches.
The key insight is that the exact update θ^{\k} - θ^{full} lies primarily in the span of the deleted points’ features {x₁, …, x_k}, so projecting any gradient-based update onto this subspace captures the most relevant information. The method computes leave-k-out predictions using the hat matrix without computing the LKO model parameters explicitly.
Algorithm
- Compute LKO predictions: ŷ’₁, …, ŷ’_k ← LKO(X, Y, H, θ^{full}, k)
- Compute pseudoinverse: S⁻¹ ← PseudoInverse(Σ x_i x_i^T)
- Compute projected gradient: ∇L ← Σ(θ^{full^T}x_i - ŷ’_i)x_i
- Return θ^{res} = θ^{full} - FastMult(S⁻¹, ∇L)
Key Properties
- Optimality: Achieves maximum improvement in span(x₁,…,x_k) among all gradient-based updates (Corollary 3)
- Cost comparison: O(k²d) vs O(kd²) for Newton, O(d²) for influence functions
- Outlier advantage: PRU outperforms influence for large outlier deletions because the exact update approaches a finite limit while influence diverges
- Sparse data advantage: In sparse regimes, deleted points’ span is more likely to contain the standard basis, enabling complete removal of sensitive features
- FIT metric: PRU excels on the Feature Injection Test, completely removing injected sensitive features for large k