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.