Gradient formula in CLOMP_CKM class

[lucgiffon]

Hello,

I have a few other questions/remarks regarding the computation of the gradient in the CLOMP_CKM algorithm, lines 307 and 308 in file compressive_learning.py:

• First question is about the normalization. I see that you normalize the product between the jacobian and the residual with the norm of the sketch. However, the normalization already occurs in the jacobian computation (division by the square root of the dimension, line 559 of file sketching.py). I wonder wether I am making a mistake in my own computation of the gradient or if it is on your side? I'd like to have your opinion on this.
• Second question regards the second part of the gradient computation, at the right hand side of the addition. There is a big divide there with embedded np.real calls. On paper, I see that this part is always equal to zero and this is verified numerically (values around 1e-18 in the current run) so I don't really understand where does it come from and why it is there. Maybe it is related to some other experiments you have conducted, in which it is different than zero?

I have a last, super minor, remark: line 304 of compressive_learning.py where you use the np.vdot function. I believe the two arguments are reversed. In order to be consistent with the gradient computation hereafter, I think that you should be using the conjugate of the residual and not the one of the sketch_theta variable (it's hidden in the vdot product, as you certainly know). It doesn't have any effect on the result however, because only the real part is relevant.

Thank you in advance Luc

[lucgiffon]

Hello again, I have made some advances on this question.

I believe the gradient is written in this form because it comes from a more general form that works for any sketching function, as we can see in keriven's thesis equation 4.14. In the case of the sketching function f(x) = e-iW^Tx, the right hand side cancels out but I can imagine there are some for which it wouldn't?

I still think the double normalization is a mistake though, inside and out the jacobian computation.

[schellekensv]

Hello Luc,

Thank you for your remarks.

• For your first question, your supposition in your second comment is indeed correct: the normalization by norm_sketch_theta is not useful for the case of K-Means (the task you considered I believe) because in that case, the norm of the atom is always the same. But it is however useful in the general case (and in particular for Gaussian mixture models). This is because the first step of CL-OMP seeks the normalized atom with the highest correlation with the residual. Note that the normalization in sketching.py is not sufficient, because (1) the c_norm parameter is a proportionality constant that can be arbitrarily chosen (it is called "normalization" because I mostly chose c_norm = 1/sqrt(d) but it could be something else, the default choice cnorm = 1), thus it doesn't guarantee anything; and (2) there is a difference between normalizing the feature map Phi(x) and normalizing the sketch that is built with this feature map Expectation{x ~ P_theta} Phi(x) (remark: if I take the average of several unit norm vectors, I don't necessarily obtain a unit normed vector). The purpose of lines 307 and 308 are to do the second kind of normalization. But as I said, for the case of K-Means the two kind of normalizations are the same so indeed in that case the additional normalization line 307, 308 are not needed.
• For your second question, I'm not so sure, but I think I did the two calls to np.real because I wanted to take the real part of jacobian_theta@np.conj(sketch_theta) and np.vdot(sketch_theta,self.residual) separately (btw indeed I'm not very consistent in my use of vdot and conj, oops). A more readable way to write it would be something like np.real(jacobian_theta@np.conj(sketch_theta)) * np.real( np.vdot(sketch_theta,self.residual)) However I don't have the precise expressions in mind of what the true gradient should be so it is possible I made a mistake.

Hope this helps, Vincent