I was reading this article by Szegedy Quantum Speed-Up of Markov Chain based Algorithms, and understand the calculations. Yet I am missing an intuition about why the reflection about the column-space of the factorized matrices $A$ and $B$, with $M = A^*B$ lead to the singular values of $M$. More concretely, given the discriminant matrix $M$ and the above factorisation, one can perform reflections $\operatorname{ref}_A=2AA^*−I$ and $\operatorname{ref}_B=2BB^*−I$ (where $A^*A=B^∗B=I$), such that the operator $W=\operatorname{ref}_A\operatorname{ref}_B$ has eigenvalues that give the singular values of $M.$

It is clear to me that we obtain (at most) a two dimensional subspace (if we apply those to the corresponding right singular value) and hence obtain invariant subspaces, but I'd like to understand it more intuitively.

Here is another link for the file.

  • $\begingroup$ Unfortunately, the IEEE link you give is only accessible when your library is affiliated to IEEE... No other site were we can reach, say, an equivalent paper ? $\endgroup$ – Jean Marie May 16 '17 at 15:46
  • $\begingroup$ @JeanMarie, I added the link above, yes! I think this one is public available $\endgroup$ – LeoW. May 16 '17 at 15:53
  • $\begingroup$ No, it isn't... $\endgroup$ – Jean Marie May 16 '17 at 15:55
  • $\begingroup$ @JeanMarie I put it below the question, sorry! Here it is as well: cs.rutgers.edu/~szegedy/PUBLICATIONS/walk_focs.pdf $\endgroup$ – LeoW. May 16 '17 at 15:58

Your Answer

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

Browse other questions tagged or ask your own question.