Is my interpretation correct?

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

This is the algorithm:

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}}$.
• I doubt this algorithm is useful in practice. For example, the constant $10^7$ in the definition of $p$ is rather large. – Yuval Filmus Aug 6 '18 at 13:00

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.
• 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. – papabiceps Aug 6 '18 at 13:07
• 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. – Yuval Filmus Aug 6 '18 at 13:11
• 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 ? – papabiceps Aug 6 '18 at 18:36
• 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$. – Yuval Filmus Aug 6 '18 at 23:51
• How is the distribution $\mathcal{F}$ formed ? – papabiceps Aug 7 '18 at 5:52