Ferkans — Interactive Telecom Tutor

The Computational Bottleneck

Every iterative reconstruction algorithm — ISTA, FISTA, ADMM, Chambolle--Pock — requires repeated evaluation of the forward operator $\mathbf{A}$ and its adjoint $\mathbf{A}^{H}$ . For a 2D imaging problem with $M$ measurements and $Q$ voxels, a naive matrix-vector product costs $O(MQ)$ floating-point operations. When $M = 2048$ and $Q = 16{,}384$ , this is manageable. But in 3D problems or dense multi-frequency configurations, $M$ and $Q$ can each exceed $10^6$ , and storing the full matrix — let alone multiplying by it — becomes infeasible.

The point is that the sensing operator in RF imaging is not an arbitrary dense matrix. It has structure inherited from the physics: separable array geometries produce Kronecker products, uniform grids produce Fourier structure, and the combination of both yields algorithms that are orders of magnitude faster than the naive approach.

Definition:
Kronecker Product

For $\mathbf{A}_{1} \in \mathbb{C}^{M_1 \times N_1}$ and $\mathbf{A}_{2} \in \mathbb{C}^{M_2 \times N_2}$ , the Kronecker product $\mathbf{A}_{1} \otimes \mathbf{A}_{2} \in \mathbb{C}^{M_1 M_2 \times N_1 N_2}$ is defined by

$(\mathbf{A}_{1} \otimes \mathbf{A}_{2})_{(i_1-1)M_2 + i_2,\;(j_1-1)N_2 + j_2} = [\mathbf{A}_{1}]_{i_1,j_1}\,[\mathbf{A}_{2}]_{i_2,j_2}.$

Equivalently, $\mathbf{A}_{1} \otimes \mathbf{A}_{2}$ is the block matrix whose $(i_1, j_1)$ -block is $[\mathbf{A}_{1}]_{i_1,j_1}\,\mathbf{A}_{2}$ .

The Kronecker product appears naturally whenever the sensing geometry is separable — for example, when the transmit array, receive array, and frequency grid factor independently. This is the typical situation in our RF imaging system (The Kronecker Structure and Sensing Operator Properties).

Theorem: The Vec Trick for Kronecker Products

Let $\mathbf{A}_{1} \in \mathbb{C}^{M_1 \times N_1}$ , $\mathbf{A}_{2} \in \mathbb{C}^{M_2 \times N_2}$ , and $\mathbf{X} \in \mathbb{C}^{N_2 \times N_1}$ . Then

$(\mathbf{A}_{1} \otimes \mathbf{A}_{2})\,\text{vec}(\mathbf{X}) = \text{vec}(\mathbf{A}_{2}\,\mathbf{X}\,\mathbf{A}_{1}^{T}).$

Instead of forming the $M_1 M_2 \times N_1 N_2$ Kronecker product and multiplying by the $N_1 N_2$ -dimensional vectorized image, we can reshape the image into a matrix and multiply from both sides. The right-hand side involves two smaller matrix products, which is dramatically cheaper.

Proof

Column permutation argument

Write $\text{vec}(\mathbf{X}) = \sum_{j=1}^{N_1} \mathbf{e}_{j}^{(N_1)} \otimes \mathbf{x}_j$ where $\mathbf{x}_j$ is the $j$ -th column of $\mathbf{X}$ . Applying $\mathbf{A}_{1} \otimes \mathbf{A}_{2}$ :

$(\mathbf{A}_{1} \otimes \mathbf{A}_{2})\,\text{vec}(\mathbf{X}) = \sum_{j=1}^{N_1} (\mathbf{A}_{1} \mathbf{e}_j^{(N_1)}) \otimes (\mathbf{A}_{2} \mathbf{x}_j).$

Recognize the vectorized product

The $j$ -th column of $\mathbf{A}_{2} \mathbf{X} \mathbf{A}_{1}^{T}$ is $\mathbf{A}_{2} \sum_{k} [\mathbf{A}_{1}^{T}]_{k,j} \mathbf{x}_k = \mathbf{A}_{2} \sum_k [\mathbf{A}_{1}]_{j,k} \mathbf{x}_k$ . Vectorizing this matrix yields exactly the expression above. $\blacksquare$

Complexity Reduction via the Vec Trick

The naive product $(\mathbf{A}_{1} \otimes \mathbf{A}_{2})\, \text{vec}(\mathbf{X})$ costs $O(M_1 M_2 N_1 N_2)$ operations and requires storing the full Kronecker product.

The factored computation $\text{vec}(\mathbf{A}_{2}\,\mathbf{X}\,\mathbf{A}_{1}^{T})$ costs:

$\mathbf{A}_{2} \mathbf{X}$ : $O(M_2 N_2 N_1)$
Result $\times \mathbf{A}_{1}^{T}$ : $O(M_2 M_1 N_1)$
Total: $O(M_2 N_2 N_1 + M_1 M_2 N_1) = O(N_1(M_2 N_2 + M_1 M_2))$

For our RF imaging system with $M_1 = M_2 = 32$ and $N_1 = N_2 = 128$ , the naive approach requires $\sim 10^9$ operations. The factored approach requires $\sim 10^6$ — a three-orders-of-magnitude reduction.

Storage is equally dramatic: the full matrix occupies $M_1 M_2 N_1 N_2 = 2048 \times 16{,}384 \approx 33.5$ million complex entries, while the two factors together need only $M_1 N_1 + M_2 N_2 = 32 \times 128 + 32 \times 128 = 8{,}192$ entries.

Example: Kronecker Structure in the RF Imaging Sensing Operator

Consider a monostatic RF imaging system where the sensing operator for a single subcarrier has the form

$\mathbf{A} = \mathbf{D}_{\text{freq}} \cdot (\mathbf{X}^T \otimes \mathbf{I}_{N_r}) \cdot \text{diag}(\text{vec}(\mathbf{B} \odot \mathbf{C})),$

where $\mathbf{X}$ is the pilot matrix and $\mathbf{B}, \mathbf{C}$ contain steering vector entries.

For a uniform linear array imaging a rectangular grid, show that the core of the operator — the steering-vector part — has Kronecker structure, and identify the factors.

Solution

Identify the separable geometry

For a ULA with elements at positions $\{n d_{\text{ant}}\}_{n=0}^{N-1}$ imaging a 2D grid with coordinates $\{(p_{q_x}, p_{q_y})\}$ , the steering vector for voxel $(q_x, q_y)$ has elements

$[\mathbf{a}(\mathbf{p}_q)]_n = e^{+j\frac{2\pi f_0}{c} \|\mathbf{p}_n - \mathbf{p}_q\|}.$

In the far-field limit, this separates as

$e^{+j\kappa (n d_{\text{ant}} \sin\phi_q)}$

where $\phi_q$ depends on both $p_{q_x}$ and $p_{q_y}$ .

Kronecker factorization for 2D grid

When the grid is rectangular and the array is a UPA (uniform planar array) with $N_x \times N_y$ elements, the steering matrix factors as

$\mathbf{A}_{\text{steer}} = \mathbf{A}_{y} \otimes \mathbf{A}_{x}$

where $[\mathbf{A}_{x}]_{n_x, q_x} = e^{+j\kappa_x n_x d_x}$ and $[\mathbf{A}_{y}]_{n_y, q_y} = e^{+j\kappa_y n_y d_y}$ . Each factor is a partial DFT matrix.

Applying the vec trick

Reshape the image $\mathbf{c} \in \mathbb{C}^{Q_x Q_y}$ into $\mathbf{C} \in \mathbb{C}^{Q_y \times Q_x}$ . Then

$\mathbf{A}\,\mathbf{c} = \text{vec}(\mathbf{A}_{y}\,\mathbf{C}\,\mathbf{A}_{x}^{T}),$

which costs $O(N_y Q_y Q_x + N_x N_y Q_x)$ instead of $O(N_x N_y Q_x Q_y)$ .

Definition:
The Fast Fourier Transform (FFT)

The discrete Fourier transform (DFT) of $\mathbf{x} \in \mathbb{C}^N$ is

$[\mathbf{F}\mathbf{x}]_k = \sum_{n=0}^{N-1} x_n\,e^{-j 2\pi kn/N}, \quad k = 0, \ldots, N-1.$

The FFT computes $\mathbf{F}\mathbf{x}$ in $O(N \log N)$ operations using the Cooley-Tukey divide-and-conquer factorization, compared to $O(N^2)$ for the direct sum.

When the Kronecker factor $\mathbf{A}_{x}$ is a DFT matrix (as occurs for uniform spatial sampling), the matrix-vector product $\mathbf{A}_{x}^{T} \mathbf{x}$ reduces to an FFT. This is the case whenever the imaging grid has uniform spacing in the direction corresponding to $\mathbf{A}_{x}$ .

In the Kronecker-factored computation $\text{vec}(\mathbf{A}_{y} \mathbf{C} \mathbf{A}_{x}^{T})$ , if both factors are DFT matrices, each column-wise or row-wise multiplication is an FFT. The total cost drops to $O(Q_x Q_y \log Q_x + Q_x Q_y \log Q_y) = O(Q \log \sqrt{Q})$ .

Definition:
Non-Uniform FFT (NUFFT)

The non-uniform FFT evaluates sums of the form

$f(\boldsymbol{\kappa}_m) = \sum_{q=1}^{Q} c_q\, e^{-j\,\boldsymbol{\kappa}_m^T \mathbf{p}_q}, \quad m = 1, \ldots, M,$

where the frequency points $\{\boldsymbol{\kappa}_m\}$ lie on a non-uniform grid, in $O(Q \log Q + M)$ operations.

The NUFFT proceeds in three steps:

Gridding: Convolve the non-uniform samples onto an oversampled uniform grid using a compactly supported kernel (e.g., Kaiser-Bessel or Gaussian).
FFT: Apply a standard FFT on the oversampled grid.
Deapodization: Correct for the convolution kernel in the transform domain.

Accuracy depends on the oversampling factor (typically $2\times$ ) and the kernel width (typically 6--12 points). For imaging applications, relative errors below $10^{-6}$ are standard.

The NUFFT is essential for RF imaging because the wavenumber samples $\{\boldsymbol{\kappa}_m\}$ determined by the array geometry and carrier frequencies rarely fall on a uniform grid. The NUFFT avoids the need to interpolate measurements onto a regular grid (which introduces additional approximation error).

Historical Note: The FFT: A Discovery Rediscovered

1805--1965

The Cooley-Tukey FFT algorithm, published in 1965, reduced the DFT from $O(N^2)$ to $O(N \log N)$ and is often cited as one of the ten most important algorithms of the twentieth century. But the idea was not new: Gauss had described an equivalent procedure in 1805 for interpolating asteroid orbits, and Runge published a similar scheme in 1903. The 1965 rediscovery by Cooley and Tukey was driven by Cold War signal processing needs — specifically, detecting nuclear tests from seismic data. The timing was perfect: digital computers had become fast enough to exploit the algorithm, and the applications were urgent enough to fund the research.

Theorem: Adjoint of a Kronecker-Structured Operator

If $\mathbf{A} = \mathbf{A}_{1} \otimes \mathbf{A}_{2}$ , then the adjoint (conjugate transpose) factors as

$\mathbf{A}^{H} = \mathbf{A}_{1}^{H} \otimes \mathbf{A}_{2}^{H},$

and the adjoint application satisfies

$\mathbf{A}^{H} \text{vec}(\mathbf{Y}) = \text{vec}(\mathbf{A}_{2}^{H} \mathbf{Y} \overline{\mathbf{A}_{1}}).$

In particular, both the forward operator $\mathbf{A}$ and the adjoint $\mathbf{A}^{H}$ can be evaluated using the vec trick, with no additional memory or algorithmic complexity.

The adjoint of a Kronecker product is the Kronecker product of the adjoints — the factorization is preserved. This is essential because every proximal algorithm requires both $\mathbf{A}\mathbf{c}$ (forward) and $\mathbf{A}^{H} \mathbf{y}$ (adjoint) at every iteration.

Proof

Mixed-product property

For any matrices of compatible sizes, $(\mathbf{A} \otimes \mathbf{B})(\mathbf{C} \otimes \mathbf{D}) = (\mathbf{AC}) \otimes (\mathbf{BD})$ . Taking $\mathbf{C} = \mathbf{A}_{1}^{H}$ , $\mathbf{D} = \mathbf{A}_{2}^{H}$ and applying the transpose to both sides yields the result.

Adjoint vec trick

Apply the vec trick (TThe Vec Trick for Kronecker Products) to $\mathbf{A}^{H} = \mathbf{A}_{1}^{H} \otimes \mathbf{A}_{2}^{H}$ with matrix $\mathbf{Y} \in \mathbb{C}^{M_2 \times M_1}$ :

$(\mathbf{A}_{1}^{H} \otimes \mathbf{A}_{2}^{H})\,\text{vec}(\mathbf{Y}) = \text{vec}(\mathbf{A}_{2}^{H} \mathbf{Y} (\mathbf{A}_{1}^{H})^T) = \text{vec}(\mathbf{A}_{2}^{H} \mathbf{Y} \overline{\mathbf{A}_{1}}).$

$\blacksquare$

Kronecker-Factored Forward and Adjoint Operations

Complexity:

O(N_1(M_2 N_2 + M_1 M_2))

for forward; same for adjoint

Input: Factors

\mathbf{A}_{1} \in \mathbb{C}^{M_1 \times N_1}

,

\mathbf{A}_{2} \in \mathbb{C}^{M_2 \times N_2}

;

image vector

\mathbf{c} \in \mathbb{C}^{N_1 N_2}

Output:

\mathbf{y} = (\mathbf{A}_{1} \otimes \mathbf{A}_{2})\mathbf{c}

1. Reshape

\mathbf{c}

into

\mathbf{C} \in \mathbb{C}^{N_2 \times N_1}

2.

\mathbf{T} \leftarrow \mathbf{A}_{2} \, \mathbf{C}

\qquad

(cost $O(M_2 N_2 N_1)$ )

3.

\mathbf{R} \leftarrow \mathbf{T} \, \mathbf{A}_{1}^{T}

\qquad

(cost $O(M_2 M_1 N_1)$ )

4.

\mathbf{y} \leftarrow \text{vec}(\mathbf{R})

---

Adjoint:

\hat{\mathbf{c}} = (\mathbf{A}_{1}^{H} \otimes \mathbf{A}_{2}^{H})\mathbf{y}

1. Reshape

\mathbf{y}

into

\mathbf{Y} \in \mathbb{C}^{M_2 \times M_1}

2.

\mathbf{T} \leftarrow \mathbf{A}_{2}^{H} \mathbf{Y}

3.

\mathbf{R} \leftarrow \mathbf{T} \, \overline{\mathbf{A}_{1}}

4.

\hat{\mathbf{c}} \leftarrow \text{vec}(\mathbf{R})

When $\mathbf{A}_{1}$ and $\mathbf{A}_{2}$ are DFT matrices, steps 2--3 reduce to batched FFTs, further lowering the cost to $O(N_1 N_2 \log \max(N_1, N_2))$ .

Kronecker Vec Trick: Speedup over Naive Product

Compare the wall-clock time of the naive dense matrix-vector product $(\mathbf{A}_{1} \otimes \mathbf{A}_{2})\mathbf{c}$ against the factored computation $\text{vec}(\mathbf{A}_{2} \mathbf{C} \mathbf{A}_{1}^{T})$ as the problem dimension grows. The speedup is most dramatic when the factor dimensions are balanced ( $M_1 \approx M_2$ , $N_1 \approx N_2$ ).

Parameters

Max factor dimension

N_1 = N_2

64

Maximum size of each Kronecker factor

Example: NUFFT vs DFT for Non-Uniform Wavenumber Samples

In a bistatic RF imaging configuration, the wavenumber samples $\{\boldsymbol{\kappa}_m\}$ are determined by the transmitter and receiver positions and do not lie on a uniform grid. Compare the direct evaluation

$[\mathbf{A}\mathbf{c}]_m = \sum_{q=1}^{Q} c_q\,e^{-j\boldsymbol{\kappa}_m^T \mathbf{p}_q}$

against the NUFFT approximation in terms of accuracy and computational cost for $Q = 128^2$ grid points and $M = 2048$ measurements.

Solution

Direct evaluation cost

Each of the $M$ outputs requires a sum over $Q$ terms, giving total cost $O(MQ) = O(2048 \times 16{,}384) \approx 3.4 \times 10^7$ .

NUFFT cost

With $2\times$ oversampling, the NUFFT evaluates on a $(2 \times 128)^2 = 65{,}536$ -point uniform grid via FFT ( $O(Q' \log Q') \approx 10^6$ ), then interpolates to the $M$ non-uniform points ( $O(MW) \approx 2048 \times 12 \approx 2.5 \times 10^4$ for kernel width $W = 12$ ). Total: $\sim 10^6$ operations.

Accuracy comparison

For kernel width $W = 12$ and oversampling $2\times$ , the NUFFT achieves relative error $< 10^{-6}$ compared to the direct sum. This is more than sufficient for imaging applications where the measurement noise floor is typically at $-30$ to $-60$ dB.

NUFFT Approximation Error vs Kernel Width

Evaluate the relative error of the NUFFT approximation compared to direct DFT evaluation as a function of the interpolation kernel width $W$ . Demonstrates that $W = 6$ -- $12$ suffices for imaging applications.

Parameters

Grid size

N

64

Oversampling factor2

Common Mistake: Kronecker Factor Ordering

Mistake:

Writing $\mathbf{A} = \mathbf{A}_{2} \otimes \mathbf{A}_{1}$ instead of $\mathbf{A} = \mathbf{A}_{1} \otimes \mathbf{A}_{2}$ and then applying the vec trick as $\text{vec}(\mathbf{A}_{2} \mathbf{X} \mathbf{A}_{1}^{T})$ .

Correction:

The Kronecker product is not commutative: $\mathbf{A}_{1} \otimes \mathbf{A}_{2} \neq \mathbf{A}_{2} \otimes \mathbf{A}_{1}$ in general. The vec trick maps the first factor to the right-multiplication and the second factor to the left-multiplication:

$(\mathbf{A}_{1} \otimes \mathbf{A}_{2})\text{vec}(\mathbf{X}) = \text{vec}(\mathbf{A}_{2} \mathbf{X} \mathbf{A}_{1}^{T}).$

Swapping the factors produces a permuted result. Always verify by checking the dimensions: $\mathbf{X}$ must be $N_2 \times N_1$ (rows match the second factor's columns).

Theorem: Spectral Properties of Kronecker Products

Let $\mathbf{A}_{1}$ and $\mathbf{A}_{2}$ have singular values $\{\sigma_i^{(1)}\}$ and $\{\sigma_j^{(2)}\}$ respectively. Then:

The singular values of $\mathbf{A}_{1} \otimes \mathbf{A}_{2}$ are $\{\sigma_i^{(1)} \sigma_j^{(2)}\}$ for all pairs $(i,j)$ .
$\|\mathbf{A}_{1} \otimes \mathbf{A}_{2}\| = \|\mathbf{A}_{1}\| \cdot \|\mathbf{A}_{2}\|$ .
$\kappa(\mathbf{A}_{1} \otimes \mathbf{A}_{2}) = \kappa(\mathbf{A}_{1}) \cdot \kappa(\mathbf{A}_{2})$ , where $\kappa$ denotes the condition number.

The condition number of the full sensing operator is the product of the condition numbers of the factors. If each factor is moderately ill-conditioned (say $\kappa = 100$ ), the Kronecker product can be severely ill-conditioned ( $\kappa = 10^4$ ). This multiplicative growth of ill-conditioning is a fundamental challenge in structured inverse problems.

Proof

SVD of the Kronecker product

Write $\mathbf{A}_{1} = \mathbf{U}_1 \boldsymbol{\Sigma}_1 \mathbf{V}_1^H$ and $\mathbf{A}_{2} = \mathbf{U}_2 \boldsymbol{\Sigma}_2 \mathbf{V}_2^H$ . By the mixed-product property,

$\mathbf{A}_{1} \otimes \mathbf{A}_{2} = (\mathbf{U}_1 \otimes \mathbf{U}_2) (\boldsymbol{\Sigma}_1 \otimes \boldsymbol{\Sigma}_2) (\mathbf{V}_1 \otimes \mathbf{V}_2)^H.$

Since Kronecker products of unitary matrices are unitary, this is a valid SVD. The diagonal entries of $\boldsymbol{\Sigma}_1 \otimes \boldsymbol{\Sigma}_2$ are all products $\sigma_i^{(1)} \sigma_j^{(2)}$ .

Spectral norm and condition number

$\|\mathbf{A}_{1} \otimes \mathbf{A}_{2}\| = \max_{i,j} \sigma_i^{(1)} \sigma_j^{(2)} = \sigma_{\max}^{(1)} \sigma_{\max}^{(2)} = \|\mathbf{A}_{1}\| \cdot \|\mathbf{A}_{2}\|$ .

Similarly, $\sigma_{\min}(\mathbf{A}_{1} \otimes \mathbf{A}_{2}) = \sigma_{\min}^{(1)} \sigma_{\min}^{(2)}$ . The ratio gives $\kappa = \kappa_1 \cdot \kappa_2$ . $\blacksquare$

Quick Check

For $\mathbf{A}_{1} \in \mathbb{C}^{32 \times 128}$ and $\mathbf{A}_{2} \in \mathbb{C}^{64 \times 128}$ , the Kronecker product $\mathbf{A}_{1} \otimes \mathbf{A}_{2}$ is a matrix of size:

$2048 \times 16{,}384$

$96 \times 256$

$4096 \times 32{,}768$

$64 \times 128$

Correction:

2048 \times 16{,}384

$M_1 M_2 \times N_1 N_2 = 32 \times 64 \times 128 \times 128 = 2048 \times 16{,}384$ .

Quick Check

When applying the vec trick to compute $(\mathbf{A}_{1} \otimes \mathbf{A}_{2})\text{vec}(\mathbf{X})$ with $\mathbf{A}_{1} \in \mathbb{C}^{32 \times 128}$ and $\mathbf{A}_{2} \in \mathbb{C}^{64 \times 128}$ , what shape should $\mathbf{X}$ be?

$128 \times 128$

$128 \times 32$

$64 \times 32$

$32 \times 128$

Correction:

128 \times 128

$\mathbf{X} \in \mathbb{C}^{N_2 \times N_1} = \mathbb{C}^{128 \times 128}$ . The number of rows matches $\mathbf{A}_{2}$ 's columns; the number of columns matches $\mathbf{A}_{1}$ 's columns.

Definition:
Multi-Factor Kronecker Products

For three or more factors, the Kronecker product extends associatively:

$\mathbf{A}_{1} \otimes \mathbf{A}_{2} \otimes \mathbf{A}_{3} = (\mathbf{A}_{1} \otimes \mathbf{A}_{2}) \otimes \mathbf{A}_{3}.$

The vec trick generalizes to tensor contractions. For the three-factor case (e.g., frequency $\times$ Rx $\times$ Tx in the RF imaging model), reshape $\mathbf{c}$ into a 3D tensor $\mathcal{C} \in \mathbb{C}^{N_3 \times N_2 \times N_1}$ and apply each factor along the corresponding mode:

$\mathcal{Y} = \mathcal{C} \times_1 \mathbf{A}_{3} \times_2 \mathbf{A}_{2} \times_3 \mathbf{A}_{1},$

where $\times_k$ denotes the mode- $k$ product. The total cost is $O(N_1 N_2 N_3 (M_1 + M_2 + M_3))$ instead of $O(M_1 M_2 M_3 \cdot N_1 N_2 N_3)$ .

In the RF imaging system of The Kronecker Structure and Sensing Operator Properties, the three factors correspond to the transmit steering ( $\mathbf{A}_{\text{Tx}}$ ), receive steering ( $\mathbf{A}_{\text{Rx}}$ ), and frequency phase ( $\mathbf{A}_{\text{freq}}$ ) components.

Common Mistake: Near-Field Breaks Exact Kronecker Structure

Mistake:

Assuming that the sensing operator always has exact Kronecker structure, even when the array is in the near-field of the imaging region.

Correction:

The Kronecker factorization $\mathbf{A} = \mathbf{A}_{1} \otimes \mathbf{A}_{2}$ is exact only in the far-field regime, where the steering vector separates into azimuth and elevation components. In the near-field, the steering vector for each antenna depends on the full 3D distance $\|\mathbf{p}_n - \mathbf{p}_q\|$ , which does not factor.

For our system with Fresnel number $\approx 0.36$ (Section 5 of the code reference), near-field effects are non-negligible. In practice, one can:

Use the Kronecker structure as a preconditioner (fast approximate inverse).
Store and apply the exact operator, but use the Kronecker approximation for gradient computations where high accuracy is less critical.
Apply a NUFFT-based approach that handles the non-uniform sampling directly.

Why This Matters: Kronecker Structure in MIMO Channel Estimation

The Kronecker structure exploited here for RF imaging is the same structure that appears in MIMO channel estimation. When the transmit and receive correlation matrices are separable ( $\mathbf{R} = \mathbf{R}_r \otimes \mathbf{R}_t$ ), the vectorized channel $\text{vec}(\mathbf{H})$ has a Kronecker-structured covariance. The LMMSE channel estimator then exploits this factorization in exactly the same way as our vec trick — the two-sided matrix multiplication replaces a large matrix inversion.

The insight that separable structure reduces computational cost from $O(N^4)$ to $O(N^3)$ in MIMO estimation (Kronecker Channel Models) is the same insight applied here to reduce the imaging operator cost.

Kronecker product

The tensor product of two matrices $\mathbf{A} \otimes \mathbf{B}$ , formed by replacing each entry $a_{ij}$ with the block $a_{ij}\mathbf{B}$ . The result has dimensions $(M_1 M_2) \times (N_1 N_2)$ .

Related: {{Ref:Gloss Vec Operator}}

Vec operator

The vectorization $\text{vec}(\mathbf{X})$ stacks the columns of $\mathbf{X} \in \mathbb{C}^{m \times n}$ into a single vector in $\mathbb{C}^{mn}$ . The inverse operation reshapes a vector back into a matrix.

Non-uniform FFT (NUFFT)

An algorithm that evaluates Fourier sums at non-uniformly spaced frequency points in $O(N \log N + M)$ time, where $N$ is the number of source points and $M$ is the number of target points. Uses gridding, FFT, and deapodization.

Key Takeaway

The sensing operator $\mathbf{A}$ in RF imaging inherits Kronecker structure from the separable array geometry. The vec trick converts a dense matrix-vector product into two smaller matrix multiplications, reducing cost by orders of magnitude. When the factors are DFT matrices (uniform grids), the FFT provides an additional logarithmic speedup. For non-uniform wavenumber sampling, the NUFFT achieves near-optimal complexity with controllable approximation error. Every iterative reconstruction algorithm benefits directly from these fast operator evaluations.

Fast Algorithms for Structured Operators

The Computational Bottleneck

Definition: Kronecker Product

Theorem: The Vec Trick for Kronecker Products

Column permutation argument

Recognize the vectorized product

Complexity Reduction via the Vec Trick

Example: Kronecker Structure in the RF Imaging Sensing Operator

Identify the separable geometry

Kronecker factorization for 2D grid

Applying the vec trick

Definition: The Fast Fourier Transform (FFT)

Definition: Non-Uniform FFT (NUFFT)

Historical Note: The FFT: A Discovery Rediscovered

Theorem: Adjoint of a Kronecker-Structured Operator

Mixed-product property

Adjoint vec trick

Kronecker-Factored Forward and Adjoint Operations

Kronecker Vec Trick: Speedup over Naive Product

Parameters

Example: NUFFT vs DFT for Non-Uniform Wavenumber Samples

Direct evaluation cost

NUFFT cost

Accuracy comparison

NUFFT Approximation Error vs Kernel Width

Parameters

Common Mistake: Kronecker Factor Ordering

Theorem: Spectral Properties of Kronecker Products

SVD of the Kronecker product

Spectral norm and condition number

Quick Check

Quick Check

Definition: Multi-Factor Kronecker Products

Common Mistake: Near-Field Breaks Exact Kronecker Structure

Why This Matters: Kronecker Structure in MIMO Channel Estimation

Kronecker product

Vec operator

Non-uniform FFT (NUFFT)

Key Takeaway

Definition:
Kronecker Product

Definition:
The Fast Fourier Transform (FFT)

Definition:
Non-Uniform FFT (NUFFT)

Definition:
Multi-Factor Kronecker Products