# Lower bound $x^TSA^TASx$

Let $A$ be an $n^2\times K$ matrix with $K = \frac{n(n-1)}{2}$. $A$ is not orthonormal but has linearly independent columns. Let $S$ be a diagonal sampling matrix(of zeros and ones). The diagonal entries are sampled uniformly at random. The goal is to lower bound the following quantity $$x^TSA^TASx$$ I know the structure of $A$ fairly well and can estimate coherences and such. Is there a concentration inequality that might be useful? I appreciate any suggestions.

• Your matrix has more columns ($n^2$) than rows ($\frac{n(n-1)}2$), so the columns can't all be linearly independent. – Andreas Blass Jul 7 '17 at 16:17
• @Andreas, was a typo, fixed now. – johnny Jul 7 '17 at 16:55

As far as we know from what you told us, $A^T A$ is an arbitrary $K \times K$ positive definite matrix. Thus there is some $c > 0$ such that $z^T A^T A z \ge c z^T z$ for all $z$, and that's really all we know about it. In particular, $x^T S A^T A S x \ge c x^T S x = c \sum_j S_{jj} x_j^2$. If $S_{jj}$ are iid Bernoulli($1/2$) random variables, then we can say something about the statistics of the right side, but of course it will depend on the $x_j$'s. For example, of course its expected value is $c \sum_j x_j^2/2$.
• @Thank you for the reply. I know some information about $x$, $x\cdot 1=0$ and I have a bound for the maximum entry of $x$. I was hoping to use a concentration inequality to be able to lower bound it. – johnny Jul 7 '17 at 18:47
• $x \cdot 1 = 0$ seems not particularly helpful, nor the maximum entry of $x$: maybe $x$ has two entries of $+M$ and $-M$ and all the rest $0$. Then $\sum_j S_jj x_j^2$ is $M^2$ times a Binomial($2,1/2$) random variable, which has probability $1/4$ of being $0$. If you want a nontrivial lower bound with high probability, you'll need to rule out the possibility that nearly all entries of $x$ are very close to $0$. – Robert Israel Jul 7 '17 at 19:58