Efficient convolutional sparse coding
Computationally efficient algorithms may be applied for fast dictionary learning solving the convolutional sparse coding problem in the Fourier domain. More specifically, efficient convolutional sparse coding may be derived within an alternating direction method of multipliers (ADMM) framework that utilizes fast Fourier transforms (FFT) to solve the main linear system in the frequency domain. Such algorithms may enable a significant reduction in computational cost over conventional approaches by implementing a linear solver for the most critical and computationally expensive component of the conventional iterative algorithm. The theoretical computational cost of the algorithm may be reduced from O(M 3 N) to O(MN log N), where N is the dimensionality of the data and M is the number of elements in the dictionary. This significant improvement in efficiency may greatly increase the range of problems that can practically be addressed via convolutional sparse representations.
1. A computer-implemented method, comprising:
deriving efficient convolutional sparse coding in a frequency domain, by a computing system, within an alternating direction method of multipliers (ADMM) framework using fast Fourier transforms (FFTs);
determining, by the computing system, coefficient maps of a signal or image vector s using the derived efficient convolutional sparse coding; and
when stopping criteria are met, outputting the coefficient maps, by the computing system, as a sparse representation of s.
2. The computer-implemented method of claim 1 , wherein the coefficient maps are determined with an efficiency of O(MN log N), where N is a dimensionality of the data and M is a number of elements in a dictionary.
3. The computer-implemented method of claim 1 , wherein the coefficient maps are computed using only inner products, element-wise addition, and scalar multiplication as vector operations.
4. The computer-implemented method of claim 1 , further comprising:
precomputing, by the computing system, FFTs of a dictionary D and the signal or image vector s.
5. The computer-implemented method of claim 1 , further comprising:
initializing auxiliary variables, by the computing system, to zero.
6. The computer-implemented method of claim 1 , wherein while the stopping criteria have not been met, the method further comprises:
computing, by the computing system, FFTs of auxiliary variables, frequency domain coefficient maps, inverse FFTs of the coefficient maps, and calculating the auxiliary variables; and
updating auxiliary parameter ρ when convergence to a desired accuracy has not occurred.
7. The computer-implemented method of claim 1 , wherein the computing system determines a set of coefficient maps in the frequency domain by
v
n
=
ρ
-
1
(
b
n
-
a
n
H
b
n
ρ
+
a
n
H
a
n
a
n
)
.
8. The computer-implemented method of claim 1 , further comprising:
learning a dictionary D from a set of training data, wherein a FFT of D yields a dictionary in the frequency domain {circumflex over (D)} such that
D
^
=
(
d
^
0
,
0
0
0
⋯
d
^
1
,
0
0
0
⋯
0
d
^
0
,
1
0
⋯
0
d
^
1
,
1
0
⋯
0
0
d
^
0
,
2
⋯
0
0
d
^
1
,
2
⋯
⋮
⋮
⋮
⋱
⋮
⋮
⋮
⋱
)
where {circumflex over (D)} is concatenated as a set of block matrices and each block matrix is a diagonal.
9. The computer-implemented method of claim 8 , wherein D is a multi-scale dictionary.
10. The computer-implemented method of claim 1 , further comprising:
computing, by the computing system, a dictionary in a frequency domain ĝ m ∀m using ŷ k,m as coefficient maps and using an iterated Sherman-Morrison algorithm for a dictionary update; and
outputting, by the computing system, a dictionary {g m } when stopping tolerances are met.
11. The computer-implemented method of claim 10 , further comprising:
interleaving, by the computing system, updates on sparse coding and dictionary learning such that g m represents the dictionary in sparse coding steps and y k,m represent sparse coding in dictionary steps; and
outputting, by the computing system, coefficient maps {y m } when the stopping tolerances are met.