Have a question? Connect with the community at the TensorFlow Forum Visit Forum

tf.linalg.LinearOperatorCirculant3D

LinearOperator acting like a nested block circulant matrix.

Inherits From: LinearOperator, Module

This operator acts like a block 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 block circulant matrices

If A is nested block circulant, with block sizes N0, N1, N2 (N0 * N1 * N2 = N): A has a block structure, composed of N0 x N0 blocks, with each block an N1 x N1 block circulant matrix.

For example, with W, X, Y, Z each block circulant,

A = |W Z Y X|
    |X W Z Y|
    |Y X W Z|
    |Z Y X W|

Note that A itself will not in general be circulant.

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.

If H.shape = [N0, N1, N2], (N0 * N1 * N2 = N): Loosely speaking, matrix multiplication is equal to the action of a Fourier multiplier: A u = IDFT3[ H DFT3[u] ]. Precisely speaking, given [N, R] matrix u, let DFT3[u] be the [N0, N1, N2, R] Tensor defined by re-shaping u to [N0, N1, N2, R] and taking a three dimensional DFT across the first three dimensions. Let IDFT3 be the inverse of DFT3. Matrix multiplication may be expressed columnwise:

(A u)_r = IDFT3[ H * (DFT3[u])_r ]

Operator properties deduced from the spectrum.

  • 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, N0, N1, N2], we say that H is a Hermitian spectrum if, with % meaning modulus division,

H[..., n0 % N0, n1 % N1, n2 % N2]
  = ComplexConjugate[ H[..., (-n0) % N0, (-n1) % N1, (-n2) % N2] ].
  • 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.

Examples

See LinearOperatorCirculant and LinearOperatorCirculant2D for examples.

Performance

Suppose operator is a LinearOperatorCirculant of shape [N, N], and x.shape = [N, R]. Then

  • operator.matmul(x) is O(R*N*Log[N])
  • operator.solve(x) is O(R*N*Log[N])
  • operator.determinant() involves a size N reduce_prod.

If instead operator and x have shape [B1,...,Bb, N, N] and [B1,...,Bb, N, R], every operation increases in complexity by B1*...*Bb.

Matrix property hints

This LinearOperator is initialized with boolean flags of the form is_X, for X = non_singular, self_adjoint, positive_definite, square. These have the following meaning

  • If is_X == True, callers should expect the operator to have the property X. This is a promise that should be fulfilled, but is not a runtime assert. For example, finite floating point precision may result in these promises being violated.
  • If is_X == False, callers should expect the operator to not have X.
  • If is_X == None (the default), callers should have no expectation either way.

spectrum Shape [B1,...,Bb, N] Tensor. Allowed dtypes: float16, float32, float64, complex64, complex128. Type can be different than input_output_dtype
input_output_dtype dtype for input/output.
is_non_singular Expect that this operator is non-singular.
is_self_adjoint Expect that this operator is equal to its hermitian transpose. If spectrum is real, this will always be true.
is_positive_definite Expect that this operator is positive definite, meaning the real part of all eigenvalues is positive. We do not require the operator to be self-adjoint to be positive-definite. See: https://en.wikipedia.org/wiki/Positive-definite_matrix

Extension_for_non_symmetric_matrices

is_square Expect that this operator acts like square [batch] matrices.
name A name to prepend to all ops created by this class.

H Returns the adjoint of the current LinearOperator.

Given A representing this LinearOperator, return A*. Note that calling self.adjoint() and self.H are equivalent.

batch_shape TensorShape of batch dimensions of this LinearOperator.

If this operator acts like the batch matrix A with A.shape = [B1,...,Bb, M, N], then this returns TensorShape([B1,...,Bb]), equivalent to A.shape[:-2]

block_depth Depth of recursively defined circulant blocks defining this Operator.

With A the dense representation of this Operator,

block_depth = 1 means A is symmetric circulant. For example,

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

block_depth = 2 means A is block symmetric circulant with symmetric circulant blocks. For example, with W, X, Y, Z symmetric circulant,

A = |W Z Y X|
|X W Z Y|
|Y X W Z|
|Z Y X W|

block_depth = 3 means A is block symmetric circulant with block symmetric circulant blocks.

block_shape

domain_dimension Dimension (in the sense of vector spaces) of the domain of this operator.

If this operator acts like the batch matrix A with A.shape = [B1,...,Bb, M, N], then this returns N.

dtype The DType of Tensors handled by this LinearOperator.
graph_parents List of graph dependencies of this LinearOperator. (deprecated)

is_non_singular

is_positive_definite

is_self_adjoint

is_square Return True/False depending on if this operator is square.
parameters Dictionary of parameters used to instantiate this LinearOperator.
range_dimension Dimension (in the sense of vector spaces) of the range of this operator.

If this operator acts like the batch matrix A with A.shape = [B1,...,Bb, M, N], then this returns M.

shape TensorShape of this LinearOperator.

If this operator acts like the batch matrix A with A.shape = [B1,...,Bb, M, N], then this returns TensorShape([B1,...,Bb, M, N]), equivalent to A.shape.

spectrum

tensor_rank Rank (in the sense of tensors) of matrix corresponding to this operator.

If this operator acts like the batch matrix A with A.shape = [B1,...,Bb, M, N], then this returns b + 2.

Methods

add_to_tensor

View source

Add matrix represented by this operator to x. Equivalent to A + x.

Args
x Tensor with same dtype and shape broadcastable to self.shape.
name A name to give this Op.

Returns
A Tensor with broadcast shape and same dtype as self.

adjoint

View source

Returns the adjoint of the current LinearOperator.

Given A representing this LinearOperator, return A*. Note that calling self.adjoint() and self.H are equivalent.