2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rodrigo de Azevedo Mar 28 '17 at 12:11
  • $\begingroup$ Yes, but I mean other than that... $\endgroup$ – Gil Mar 28 '17 at 12:52
2
$\begingroup$

This problem is rather non-trivial.

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

$\endgroup$
2
$\begingroup$

A couple of possible approaches:

$\endgroup$

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.