I have two rank-1 matrices $A = a_1 a_2^T$ and $B = b_1 b_2^T$, where $a_1, a_2, b_1, b_2 \in \mathbb{R}^N$ are vector-columns. I am interested in a fast way to compute the L1 distance between $A$ and $B$: $\sum_{i=1}^N \sum_{j=1}^N |A_{ij} - B_{ij}|$. Straightforwardly computing A and B and performing element-wise operations requires $O(N^2)$ time and memory.
For $L_2$ distance, however, there exists an $O(N)$ solution:
$$\sum_{i=1}^N \sum_{j=1}^N (A_{ij} - B_{ij})^2 = ||a_1||_2^2 \cdot||a_2||_2^2 + ||b_1||_2^2 \cdot||b_2||_2^2 - 2 <a_1, b_1>\cdot<a_2, b_2>$$
where $<\cdot, \cdot>$ is a scalar product.
Is there an O(N) algorithm for L1? Or at least some approximations/bounds?
If bounds are enough, you can compare with the Schatten 1-norm. Citing Equivalence inequality, we have
\begin{equation} \frac{1}{n}\|C\| \leq \|C\|_* \leq \|C\| \end{equation} where $\|\cdot\|$ is the $\ell_1$ norm on the entries of $C$ and $\|C\|_* $ is the Schatten 1-norm (sum of the singular values of $C$).
You can get the singular values as follows: \begin{align} A-B &= a_1 a_2^\top - b_1 b_2^\top\\ &= \begin{bmatrix} a_1 & -b_1 \end{bmatrix} \begin{bmatrix} a_2^\top \\ b_2^\top \end{bmatrix} \end{align} Find the QR-decomposition of these matrices to get \begin{align} A-B &= Q_1R_1 R_2^\top Q_2^\top \end{align} Then you can find the SVD of the $2\times 2$ matrix $R_1 R_2^\top$ to get the singular values.