Hybrid Real-Complex Linear Attention: A Mathematical Framework for Sub-Quadratic Transformer Architectures

The quadratic computational complexity O(N²) of the self-attention mechanism in Transformer architectures presents a fundamental bottleneck for processing long sequences. This paper introduces a novel Hybrid Real-Complex Linear Attention (HRC-LA) architecture that reduces this complexity to O(N) while preserving model expressiveness. Our approach maintains multi-head projection matrices in real number space (ℝ) for hardware efficiency while modeling the softmax normalization mechanism in complex number space (ℂ) using Random Fourier Features (RFF). We derive the complete mathematical framework for this hybrid architecture, proving that the softmax kernel can be linearized through complex-valued feature maps φ: ℝ → ℂ based on Euler's formula. The key insight is exploiting matrix multiplication associativity to compute the Key-Value association matrix S = K̃ᴴV in O(N) rather than the full N×N attention matrix. Our theoretical analysis demonstrates that this formulation achieves a speedup factor of N/M (where M is the feature dimension), yielding approximately 40× improvement for N=10,000 sequences. We further analyze numerical stability properties, gradient flow through Wirtinger calculus, and discuss implications for signal processing applications where phase information is critical.