Suppose $A = UV^T$ where $U, V$ are $n$-by-$k$ matrices (say, $k=3$ or in general assume $k\ll n$).
Is it possible to find the row-wise minimum entries (with index) for all rows in $A$ in $O(n)$ complexity with the help of the factors $U,V$?
Example: Given $\begin{bmatrix} 2 & -1 & -1 \\ 2&-1&-1\\ 4&-2&-2\end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 2\end{bmatrix} \begin{bmatrix} 2 & -1 & -1\end{bmatrix}$, then the row min is $\begin{bmatrix} -1 \\ -1 \\ -2\end{bmatrix}$ with index $2,2,2$ in rows 1 to 3 (one index for each row is enough for repeated min values). For the rank-1 case, I know how to construct such an $O(n)$ algorithm, but I don't know how to handle the general rank-$k$ case. Is $O(n)$ complexity possible? Any ideas will be appreciated.
Since I saw your post I got very interested in this problem. Note that this is not a full answer but I feel like I have collected some things which might be worth writing down.
For simplicity I will usually assume that there is a unique minimum in every row.
I mainly thought of this as a geometry problem. In particular, note that we can reformulate this problem as: For every index $i \in [n]$ find $\arg \min_{j \in [n]} u_i^\top v_j$ where $u_i$ is the $i$-th row of $U$ and $v_j$ the $j$-th row of $V$. Note that we end up with the same problem if we look for the $\arg \max$ instead of the $\arg \min$. Hence I will from now on consider the problem of finding $\arg \max_{j \in [n]} u_i^\top v_j$ for every $i \in [n]$. This problem is called Maximum Inner Product Search (MIPS) and has been studied in the literature.
A first starting point might be: https://cstheory.stackexchange.com/questions/34503/maximizing-inner-product. Here it is explained how you can use convex hulls and query algorithms on convex hulls to solve the problem in $O(n\log n)$ for $k = 3$ (works for $k = 2$ too). A different approach is used for $k = 4$ yielding a runtime of $\tilde{O}(n^{\frac{4}{3}})$.
Another related thread is https://cs.stackexchange.com/questions/76736/algorithm-to-maximize-dot-product-between-two-sets-of-vectors. In particular, an interesting randomized procedure is proposed but I did not fully understand the analysis yet.
The online version of this problem (i.e. $U$ is not known beforehand and you receive each row of $U$ as an individual query-point) seems to have many applications including recommender systems. You can start here: https://arxiv.org/pdf/1202.6101.pdf https://arxiv.org/abs/1507.05910
There are probably many directions to explore here. In particular, it seems like using techniques similar to Johnson-Lindenstrauss embeddings could be applied to achieve approximate solutions.