2
$\begingroup$

I am trying to implement the algorithm described in the paper A quantum-inspired classical algorithm for recommendation systems.

This is the algorithm:

enter image description here

These are the necessary definitions for mathematical notations used in the algorithm to understand the algorithm.

The distribution is defined as, for a nonzero vector $x \in R^n$, we denote by $\mathrm{D}_x$ the distribution over [1, ..., n] whose probability density function is $$\mathrm{D}_x(i) =\frac{x^{2}_{i}}{\lVert{x}\rVert ^2} $$.

If a matrix $A \in R^{m \times n}$, and let $A_i$ refer to the $i$th row of $A$. Let $\tilde{A} \in R^m$ be a vector whose $i$th entry is $\lVert A_i \rVert$.

$[p] denotes [1, 2, ... p]$

$s \sim _u [p]$ denotes pulling an $s$ uniformly at random.

I am having a problem understanding the Let the resulting p x p submatrix ... step of the algorithm. According to the algorithm the rows of the submatrix are sampled from a distribution $\mathrm{D}_{\tilde{A}}$ and the columns of the submatrix are sampled from a distribution $\mathcal{F}$.

  1. I can't understand how can we form a submatrix with both rows and colums given ? I think we just need either rows or columns. Can someone clarify this to me, please ?
  2. And I also don't understand the definition of $\mathcal{F}$. According to definition of $\mathcal{D}_x$, $x$ has to be a vector then how can we choose a column from $D_ \tilde{A_{i_s}}$.
$\endgroup$
  • $\begingroup$ I doubt this algorithm is useful in practice. For example, the constant $10^7$ in the definition of $p$ is rather large. $\endgroup$ – Yuval Filmus Aug 6 '18 at 13:00
2
$\begingroup$

Given a matrix $A$, you can form another matrix by taking only some of the rows and columns of $A$, possibly repeated. For example, suppose that $A$ is the following matrix: $$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} $$ If we take only rows 1,2 and columns 1,3, then we get the matrix $$ \begin{bmatrix} 1 & 3 \\ 4 & 6 \end{bmatrix} $$

For your second question, $\mathcal{D}_x$ is a distribution on column indices. You don't choose a column directly – you only choose an index. This corresponds to 1,3 in the example above.

$\endgroup$
  • $\begingroup$ I forgot to mention that my idea of forming a submatrix from a larger matrix is selecting rows and columns at random without replacement and in increasing order. So what does $sample$ $ rows$ $ i_1, ..., i_p$ $from $ $\mathcal{D}_{\tilde{A}}$ mean ? Are we sampling indices at random or sampling from $\mathcal{D}_{\tilde{A}}$ distribution. $\endgroup$ – papabiceps Aug 6 '18 at 13:07
  • $\begingroup$ It means to sample indices of rows, according to the distribution $\mathcal{D}_{\tilde{A}}$. Rows can repeat, and they don't need to be in increasing order. $\endgroup$ – Yuval Filmus Aug 6 '18 at 13:11
  • $\begingroup$ How can we sample a column from $\mathcal{D}_{\tilde{A}}$. The contents of $\tilde{A_{i_s}}$ is l2 norms of row vectors. Can you clarify to me Let F denote the distribution given.... step ? $\endgroup$ – papabiceps Aug 6 '18 at 18:36
  • $\begingroup$ You use the definition of $\mathcal{D}_x$, which applies for any vector $x$, for example $x=\tilde{A}$, whose entries are the norms of the rows of $A$. $\endgroup$ – Yuval Filmus Aug 6 '18 at 23:51
  • $\begingroup$ How is the distribution $\mathcal{F}$ formed ? $\endgroup$ – papabiceps Aug 7 '18 at 5:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.