ML Community Day is November 9! Join us for updates from TensorFlow, JAX, and more Learn more


LinearOperator acting like a circulant matrix.

Inherits From: LinearOperator, Module

This operator acts like a circulant matrix A with shape [B1,...,Bb, N, N] for some b >= 0. The first b indices index a batch member. For every batch index (i1,...,ib), A[i1,...,ib, : :] is an N x N matrix. This matrix A is not materialized, but for purposes of broadcasting this shape will be relevant.

Description in terms of circulant matrices

Circulant means the entries of A are generated by a single vector, the convolution kernel h: A_{mn} := h_{m-n mod N}. With h = [w, x, y, z],

A = |w z y x|
    |x w z y|
    |y x w z|
    |z y x w|

This means that the result of matrix multiplication v = Au has Lth column given circular convolution between h with the Lth column of u.

Description in terms of the frequency spectrum

There is an equivalent description in terms of the [batch] spectrum H and Fourier transforms. Here we consider A.shape = [N, N] and ignore batch dimensions. Define the discrete Fourier transform (DFT) and its inverse by

DFT[ h[n] ] = H[k] := sum_{n = 0}^{N - 1} h_n e^{-i 2pi k n / N}
IDFT[ H[k] ] = h[n] = N^{-1} sum_{k = 0}^{N - 1} H_k e^{i 2pi k n / N}

From these definitions, we see that

H[0] = sum_{n = 0}^{N - 1} h_n
H[1] = "the first positive frequency"
H[N - 1] = "the first negative frequency"

Loosely speaking, with * element-wise multiplication, matrix multiplication is equal to the action of a Fourier multiplier: A u = IDFT[ H * DFT[u] ]. Precisely speaking, given [N, R] matrix u, let DFT[u] be the [N, R] matrix with rth column equal to the DFT of the rth column of u. Define the IDFT similarly. Matrix multiplication may be expressed columnwise:

(A u)_r = IDFT[ H * (DFT[u])_r ]

Operator properties deduced from the spectrum.

Letting U be the kth Euclidean basis vector, and U = IDFT[u]. The above formulas show thatA U = H_k * U. We conclude that the elements of H are the eigenvalues of this operator. Therefore

  • This operator is positive definite if and only if Real{H} > 0.

A general property of Fourier transforms is the correspondence between Hermitian functions and real valued transforms.

Suppose H.shape = [B1,...,Bb, N]. We say that H is a Hermitian spectrum if, with % meaning modulus division,

H[..., n % N] = ComplexConjugate[ H[..., (-n) % N] ]

  • This operator corresponds to a real matrix if and only if H is Hermitian.
  • This operator is self-adjoint if and only if H is real.

See e.g. "Discrete-Time Signal Processing", Oppenheim and Schafer.

Example of a self-adjoint positive definite operator

# spectrum is real ==> operator is self-adjoint
# spectrum is positive ==> operator is positive definite
spectrum = [6., 4, 2]

operator = LinearOperatorCirculant(spectrum)

# IFFT[spectrum]
==> [4 + 0j, 1 + 0.58j, 1 - 0.58j]

==> [[4 + 0.0j, 1 - 0.6j, 1 + 0.6j],
     [1 + 0.6j, 4 + 0.0j, 1 - 0.6j],
     [1 - 0.6j, 1 + 0.6j, 4 + 0.0j]]