2
$\begingroup$

Due to V.Chandrasekaran., et al‎ (p.11) : In general for any $k$-dimensional subspace of $A_{n×n}$ we have that:

$$\sqrt{(k/n)} \leq incoherence(A)\leq 1$$

where the lower bound is achieved (for example) if the row/column spaces span any $k$ columns of a $n × n$ orthonormal Hadamard matrix, while the upper bound is achieved if the row or column space contains a standard basis vector.

We measure the incoherence of a subspace $A \subseteq R^n$ as follows: $$incoherence(A)=max_i ||P_Ae_i||_2$$ where $e_i$ is the $i$'th standard basis vector and $P_A$ denotes the projection onto the subspace A.

1) What is the relationship between incoherence(A) and matrix rank of the matrix such that can obtain very tight bounds on above inequality?

2) If the rank of $A$ is not known in advance, what alternative can be found (minimum error replacement) that preserves inequality? Is there a randomized methods to find it?

P.S. We shall be primarily interested in subspace with low coherence (incoherence) as matrices whose column and row spaces have low coherence cannot really be in the null space of the sampling operator.

$\endgroup$
2
  • $\begingroup$ edited. please review it. $\endgroup$
    – hoom
    Feb 3, 2014 at 0:39
  • $\begingroup$ The subspaces which are optimally incoherent in your sense are spanned by the rows of something called a unit norm tight frame. See the introduction of this paper and references therein: arxiv.org/abs/1106.0921 $\endgroup$ Feb 4, 2014 at 1:14

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.