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.
2
-
3$\begingroup$ Your matrix has more columns ($n^2$) than rows ($\frac{n(n-1)}2$), so the columns can't all be linearly independent. $\endgroup$– Andreas BlassCommented Jul 7, 2017 at 16:17
-
$\begingroup$ @Andreas, was a typo, fixed now. $\endgroup$– johnnyCommented Jul 7, 2017 at 16:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
answered Jul 7, 2017 at 17:52
-
$\begingroup$ @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. $\endgroup$– johnnyCommented Jul 7, 2017 at 18:47
-
$\begingroup$ $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$. $\endgroup$ Commented Jul 7, 2017 at 19:58