Circulant Matrix Nuclear Norm Minimization for Image Inpainting in Python

Introduce what is the circulant matrix and its nuclear norm minimization and give an efficient implementation through fast Fourier transform for image inpainting.

In machine learning, we have some special algebraic structures, such as Hankel matrix, circulant matrix, and Toeplitz matrix. By utilizing these structures, we can discover the inherent correlations of data. In this story, we introduce a circulant matrix nuclear norm minimization problem for reconstructing missing values in the image inpainting task. Since the circulant matrix shows theoretical connection with discrete Fourier transform, the algorithm can be implemented by using fast Fourier transform.

What is Circulant Matrix?

For any vector x=(x1, x2, …, xT) of length T, its circulant matrix can be written as follows,

where the first column of the circulant matrix is the vector x itself.

Circulant Matrix Nuclear Norm Minimization

Since the eigenvalue decomposition of the circulant matrix is given by