Chapter Summary

Chapter Summary: The Kronecker Structure and Sensing Operator Properties

Key Points

• 1.

  Under far-field and separable-grid assumptions, the sensing matrix factors as $\mathbf{A} = \mathbf{A}_{\text{Rx}} \otimes \mathbf{A}_{\text{Tx}} \otimes \mathbf{A}_{f}$, reducing storage from $O(MN)$ to $O(\sum m_k n_k)$ --- a factor of $\sim 10^5$ for typical 3D imaging parameters.

• 2.

  Matrix-vector products with the Kronecker-factored $\mathbf{A}$ cost $O(N^{4/3})$ for balanced factors (or $O(N \log N)$ when factors are DFT matrices), compared to $O(MN)$ for the full matrix, enabling iterative reconstruction in real time.

• 3.

  The singular values of $\mathbf{A}$ are all triple products of the factor singular values, and the condition number is the product of factor condition numbers: $\kappa(\mathbf{A}) = \kappa(\mathbf{A}_{\text{Rx}}) \cdot \kappa(\mathbf{A}_{\text{Tx}}) \cdot \kappa(\mathbf{A}_{f})$.

• 4.

  The Gram matrix $\mathbf{A}^{H}\mathbf{A}$ is the discrete point-spread function (PSF), and its off-diagonal elements determine the mutual coherence. The PSF inherits the Kronecker structure, so resolution can be analyzed dimension by dimension.

• 5.

  The physical sensing matrix has high coherence and dramatically different spectral properties from random matrices. Standard compressed sensing guarantees (RIP, coherence bounds) are pessimistic, and algorithms designed for random matrices (AMP) can fail. The Kronecker RIP bound (Jokar-Mehta) provides constructive guarantees.

• 6.

  Preconditioning exploits the Kronecker structure to reduce the effective condition number: Kronecker preconditioning inverts each factor separately at cost $O(n_k^3)$, reducing CG iterations from thousands to tens.

• 7.

  The LMMSE step in OAMP --- the computational bottleneck --- factors via joint eigendecomposition of the Kronecker factors, reducing cost from $O(N^3)$ to $O(N^{4/3})$. This makes model-based iterative reconstruction practical for real-time imaging.

• 8.

  When the far-field or separable-grid assumptions break down (near-field, non-Cartesian grids, mutual coupling), the sensing matrix is approximately Kronecker with a low-rank perturbation; computational savings are partially preserved via iterative refinement.