1
$\begingroup$

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.

$\endgroup$
  • 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 Blass Jul 7 '17 at 16:17
  • $\begingroup$ @Andreas, was a typo, fixed now. $\endgroup$ – johnny Jul 7 '17 at 16:55
1
$\begingroup$

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$.

$\endgroup$
  • $\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$ – johnny Jul 7 '17 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$ – Robert Israel Jul 7 '17 at 19:58

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.