3
$\begingroup$

Defining $ \mathcal{C}_{n} $ the set of Real Circulant Matrices.

The orthogonal projection of a given matrix $ Y \in \mathbb{R}^{n \times n} $ onto the set is given by the following minimization problem:

$$ \arg \min_{X \in \mathcal{C}_{n} } \frac{1}{2} {\left\| X - Y \right\|}_{F}^{2} $$

Where $ {\left\| \cdot \right\|}_{F} $ is the Frobenius Norm.

Since the set of Circulant Matrices is Convex Set and the objective function is convex the whole problem is a convex optimization problem.

$\endgroup$
2
  • $\begingroup$ Related: mathoverflow.net/a/295232/91764 $\endgroup$ – Rodrigo de Azevedo May 13 '18 at 10:52
  • $\begingroup$ @RodrigodeAzevedo, Lovely! Really nice solution there. I feel satisfied that my approach was similar to yours. $\endgroup$ – Royi May 13 '18 at 11:01
0
$\begingroup$

Solution 002

Since $ X $ is Circulant Matrix it is diagonalizable by the DFT Matrix.
Hence $ X = {F}^{H} \operatorname{diag} \left( x \right) F $ where $ x $ is the Fourier Transform of the first row of $ X $.
Now, Since $ F $ is Unitary Matrix and our objective function is Euclidean Distance which is invariant to multiplication by Unitary Matrix the problem can be rewritten as following:

$$ \arg \min_{X \in \mathcal{C}_{n} } \frac{1}{2} {\left\| X - Y \right\|}_{F}^{2} = \arg \min_{X \in \mathcal{C}_{n} } \frac{1}{2} {\left\| F X {F}^{H} - F Y {F}^{H} \right\|}_{F}^{2} = \arg \min_{x \in \mathbb{C}^{n} } \frac{1}{2} {\left\| \operatorname{diag} \left( x \right) - F Y {F}^{H} \right\|}_{F}^{2} $$

The above is clearly minimized by $ {x}_{i} = {\left( F Y {F}^{H} \right)}_{ii} $.
Namely $ x $ is the diagonal of $ F Y {F}^{H} $.

To generate the corresponding Real Circulant Matrix one should use the same deocmposition:

$$ X = {F}^{H} \operatorname{diag} \left( x \right) F $$

In cases $ Y $ is real matrix the above will yield a real matrix as well (Up to numerical issues due to quantization).

$\endgroup$
0
$\begingroup$

Solution 001

Defining the Forward Shift Matrix:

$$ \Pi = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 \\ 0 & 0 & 1 & & 0 \\ \vdots & & \ddots & \ddots & \vdots \\ 0 & & & & 1 \\ 1 & 0 & & \cdots & 0 \end{bmatrix} $$

One could see that the set $ \left\{ {\Pi}^{k} \mid k \in \left\{ 0, 1, \ldots, n - 1 \right\} \right\} $ is Orthogonal Basis (Can become Orthonormal with division by $ \sqrt{n} $) with respect to Frobenius Inner Product.

Since Circulant Matrix is composed by shifting forward the first row of the matrix one could see that any Circulant Matrix $ C $ with its first row given by $ c $ can be built as following:

$$ C = \sum_{k = 1}^{n} {c}_{k} {\Pi}^{k - 1} $$

Namely, this Shift Forward matrix is the basis of Circulant Matrices.
Hence, just like we build Fourier Series Coefficients by projection onto the basis, given a Matrix $ A $ we can create its projection by:

$$ {a}_{k} = \frac{1}{n} \left \langle A, {\Pi}^{k - 1} \right \rangle, \; k \in \left\{ 1, 2, \ldots, n \right\} $$

Where $ \left \langle \cdot, \cdot \right \rangle $ is the Frobenius Inner Product - $ \left \langle A, B \right \rangle = {A}^{H} B $.

Then the Circulant Matrix closest to A is given by:

$$ {P}_{\mathcal{C}^{n}} \left( A \right) = \sum_{k = 1}^{n} {a}_{k} {\Pi}^{k - 1} $$

The funny thing is this gives me better result than my solution above even if I allow Complex Matrices (Which means something isn't right).

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.