# Using low rank property for maximal/minimal value search (or sorting)

I was thinking about the following problem:

Suppose there is a positive semidefinite matrix $X$ of size $n$ (for example, a kernel). Suppose $X$ can be approximated as a low rank matrix, $X\approx GG^T$.

Is there a way to find the $k$-largest/smallest values of each row of $X$ without computing it explicitly and going over all the $n^2$ entries?

Of course the solution can approximated or probabilistic... any ideas?

• Given the symmetry, one only has to go over $\binom{n+1}{2} = \frac{(n+1) n}{2}$ entries, which is not much of an improvement. – Rodrigo de Azevedo Mar 28 '17 at 12:11
• Yes, but I mean other than that... – Gil Mar 28 '17 at 12:52

The low-rank representation of $X_{n\times n}=A_{n\times r}B^T_{r\times n}$ with the rank $r$ does not lead to an easy way of finding the minimum and maximum entries.
However, for a particular case of $r=1$, $X_{n\times n}=uv^T$, $u,v\in \mathbb R^n$, you can find $k$ smallest and $k$ largest entries in $v$ in $\mathcal O(kn)$ and then taking into account the sign of $u_i$ find $k$ smallest or largest entries in the $i$th row in $\mathcal O(k)$, for $i=1,\ldots,n$. So, for $r=1$ you certainly can cut down the calculations to $\mathcal O(kn)$.
Unfortunately, when $r>1$, the things become tricky. The following question on MathOverflow discusses options to compute the max\min element of the whole matrix, which is a very similar problem. One of the answers gives an exact algorithm for $r=2,3$ that uses known techniques to find a convex hull in 2 and 3 dimensions that can be also adopted for your problem. But I doubt that this particular approach can be successfully generalized to higher dimensions in an efficient way ($r>3$).
The other answer mentions a pretty interesting idea of using an $\epsilon$-net of an $r$-dimensional sphere to map each of the rows/columns of matrices $A$ and $B$ to compute the minimum\maximum in $\mathcal O(nr+(1/\epsilon)^r)$ with $\epsilon$ error. I am yet to try this option, but it technically makes sense and should be extendible to finding $k$ values one row at a time (by mapping only 1 row of $A$ to the net at a time, while keeping records of $B$ there). But if any decent accuracy is required, the method cost increases very fast, as it is exponential in terms of $r$, which will make it practical only for $r\ll\ll\ll n$ for any decent $\epsilon$.