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}$. 


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 ?
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}}$.
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 &amp; 2 &amp; 3 \\
4 &amp; 5 &amp; 6 \\
7 &amp; 8 &amp; 9
\end{bmatrix}
$$
If we take only rows 1,2 and columns 1,3, then we get the matrix
$$
\begin{bmatrix}
1 &amp; 3 \\
4 &amp; 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.