Symmetric matrix which satisfies conditions of the form $v_i^T X v_i = 0$

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}^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.