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