Fast verification of solution to x'Ax<C

Question

Assume we have some complex vector with N dimensions $\vec x$. We need to verify if this is a valid solution to:

$\vec x^HA\vec x<C$

where $A$ is a Hermitian matrix and $C$ is some real constant. The $^H$ denotes complex conjugate and transpose. The trivial solution of just multiplying everything together takes $\mathcal{O}(N^2)$.

I have many different vectors $\vec x$ to check, so this isn't an option. Since $A$ is known in advanced, I wanted to ask if there's some faster algorithm I can use for a large number of vectors. If it helps, the diagonal of $A$ is zeros and its eigenvalues are a mix of both positive and negative (but not zeros).

Edit: Since $A$ is known in advance, you can use any SVD, eigenvalue decomposition or other actions on it. Moreover, I can assume that the norm of $\vec x$ is 1 for all the vectors.

Answer 1

Take the eigenvalue decomposition and normalize the problem by dividing both sides by $\| x \|^2$. If now $C$ is larger than all eigenvalues, then the inequality holds; if it is smaller than all eigenvalues, then the inequality doesn't hold. Similarly, normalize the eigenvectors.

Suppose that $C$ is larger than all the nonzero eigenvalues except $\lambda_1,\dots,\lambda_k$. Begin by computing the projection coefficient $c_1$ onto $v_1$. If $c_1^2 \lambda_1+(1-c_1^2)\lambda_N \geq C$ then the inequality fails. Otherwise repeat: replace $x$ by $x-c_1 v_1$, $A$ by $A-\lambda_1 v_1 v_1^T$, and $C$ by $C-c_1^2\lambda_1$ and continue.

You can proceed from the other end if you anticipate the inequality succeeding. You could also proceed from both directions (perhaps in parallel, perhaps just alternating back and forth serially).

Answer 2

Let $d_i$ denote the eigenvalues of $A$ with $d_1>d_2> \cdots > d_n$. Let $v_i$ be the (orthonormal) associated eigenvectors.

Note that $$ x^HAx = \sum_{i=1}^n d_i |x^Hv_i|^2 \leq \sum_{i=1}^{k-1} d_i |x^H v_i|^2 + d_k\sum_{i=k}^n \left(x^Hx - \sum_{i=1}^{k-1}|x^H v_i|^2 \right) $$ It suffices to verify that for some value of $k$, the quantity on the right is smaller than $C$.