indicates that has all 0s except 1 in the th position. The dictionary updating in SGK algorithm is also different. In SGK, equation 6 also holds. Instead of using SVD to minimize the objective function, which is computationally expensive, SGK turns to use least-squares method to solve the minimization problem. Taking the derivative of with respect to and setting the result to 0 gives the following equation:

solving equation 9 leads to

It can be derived further that

Here, has the same meaning as shown in equation 5 except for a smaller size due to the selection set that selects the entries in that are non-zero.

Since , as constrained in equation 8 then

Since is a smaller version of row vector and all its entries are all equal to 1, is simply a summation over all the column vectors in . Considering that ,

Following equation 13, equation 11 becomes

It is simple to derive that , where denotes the number of elements in the set , or the number of training signals associated with the atom . The th atom in is

Thus, in SGK, one can avoid the use of SVD. Instead the trained dictionary can be simply expressed as an average of several training signals. In this way, SGK can obtain significantly higher efficiency than K-SVD. In the next section, I will use several examples to show that the overall denoising performance does not degrade when one can obtain a much faster implementation.

2020-04-03