5
$\begingroup$

I want to solve an underdetermined system of linear equations $A x = b$ with $A \in \mathbb{R}^{n \times r^2}, x \in \mathbb{R}^{r^2}, b \in \mathbb{R}^n$. The matrix $A$ has the following additional structure: each row of $A$ takes the form $v_i \otimes v_i$ for some $v_i \in \mathbb{R}^r$ (here $1 \le i \le n$). (I.e., each row is the tensor product of some vector with itself.) Furthermore, think of $r^2$ as being about the same magnitude as $n$, i.e., $n = \Theta(r^2)$.

There isn't any further structure. In particular, $A$ is likely dense. I will say that in my specific application, I am taking $b$ to be $\mathbf{0}$, and I want to find a nonzero vector in the kernel of $A$. Furthermore, this nonzero vector can't look (when converted to an $r \times r$ matrix) like a skew-symmetric matrix; it must have some symmetric component. This is because I am then projecting the solution onto the $r (r + 1)/2$-dimensional space of symmetric matrices (in $\mathbb{R}^{r^2}$), and I need it to still be nonzero. (But I thought it would be best to state the problem more generally above.)

I've spent a ton of time trying to figure out how to solve this faster than the naive $O(n^3)$. I've tried performing some version of Gaussian elimination on the rows, $QR$ decomposition, etc. I am currently looking back at iterative methods to see if I missed something that may be of use, but I'm not experienced in this area. Even pointing me towards things to possibly try would be extremely helpful! Thanks!

Edit: Per @Federico Poloni's comment, this could be better formulated as: find a symmetric matrix $X$ such that $v_i^T X v_i = 0$ for $1 \le i \le n, v_i \in \mathbb{R}^r, X \in \mathbb{R}^{r^2}$, where $r (r + 1) / 2 > n$ so that we know that there is a nonzero solution.

$\endgroup$
5
  • 1
    $\begingroup$ I have edited the title to bring in the reformulation suggested in the solution, which seems to be also OP's original one, given the edit with remarks on symmetry. $\endgroup$ – Federico Poloni Dec 3 '20 at 9:17
  • $\begingroup$ @FedericoPoloni Thanks! I also added a bit to the question at the end to go along with the change in the title. $\endgroup$ – nkyraf33 Dec 3 '20 at 15:49
  • 1
    $\begingroup$ related $\endgroup$ – Federico Poloni Dec 12 '20 at 8:21
  • $\begingroup$ How large is N for the problems you're interested in? $\endgroup$ – Richard Dec 14 '20 at 6:50
  • 1
    $\begingroup$ @Richard Very large I guess, as I am looking at it from a theoretical standpoint. (Not actually trying to implement it.) So cutting down the time by a factor of 2 would be interesting, but I'm really looking for better asymptotic guarantees. $\endgroup$ – nkyraf33 Dec 15 '20 at 0:33
1
$\begingroup$

If each row is a tensor product $v_i \otimes v_i$, then any vector $x$ that is a column-stacked version of a skew-symmetric matrix is in the kernel of $A$. For any $x$, you have $$(v_i \otimes v_i)x = v_i X v_i^T,$$ where $x = \mathrm{vec}(X)$ (see: https://en.wikipedia.org/wiki/Kronecker_product). If $X = -X^T$ then $$v_i X v_i^T = -v_i X^T v_i^T = -v_i X v_i^T = 0.$$

Note that this Kronecker-product structure is not equivalent to each row being a flattened version of a symmetric matrix. A symmetric matrix of size $n$ is determined by $\frac{1}{2}n(n+1)$ numbers whereas a matrix whose flattened version is the Kronecker-product of a vector of size $n$ with itself is determined by $n$ numbers.

$\endgroup$
1
  • 2
    $\begingroup$ Thank you for the correction regarding symmetric matrices vs. symmetric tensor products. I removed the reference in my question to the rows being symmetric matrices in general. As for the first part, I made the mistake of not specifying in my question that I need this vector in the kernel to not be skew-symmetric; it must have some symmetric component because I want it to remain nonzero after projection onto the space of symmetric matrices. Sorry for not specifying this in the first place; I still appreciate the answer. $\endgroup$ – nkyraf33 Dec 2 '20 at 13:32

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.