next show that by choosing l to be linear in r and logarithmic in n we can can with very high probability guarantee that rank(W) = r**, and hence exactly**
recover the initial matrix.

## Probability Of Choosing A Good Subset

We start with a rank-r Gram matrix, G**, and a fixed**
distribution, D, over the columns of G**. Our goal is to**
calculate the probability of randomly choosing a subset
of l columns of G according to D such that rank(W) =
r. Recall that G = X⊤X, X = [X1 X2**] and** W =
X⊤
1 X1**. Then, by properties of SVD, we know that**
rank(G) = rank(X) and rank(W) = rank(X1**). Hence,**
the probability of this desired event is equivalent to the
probability of sampling l columns of X **according to** D
such that rank(X1) = r**, as shown in (10). Next, we**
can write the thin SVD of X as X = UrΣrV
⊤

r
, where
Ur ∈ R
m×r, Σr ∈ R
r×r and Vr ∈ R
n×r**. Since** Ur
contains orthonormal columns and Σr **is invertible, we**
know that
$$\Sigma_{r}^{-1}U_{r}^{\top}X=V_{r}^{\top}.$$
. (8)
Further, using the block representation of X**, we have**

 **Contation of $X$**, we 
$$X_{1}^{\top}U_{r}\Sigma_{r}^{-1}=V_{r,l},$$
r = Vr,l, (9)
where Vr,l ∈ R
l×rcorresponds to the first l components for each of the r **right singular vectors of** X.

Since rank(X1**) = rank(**X⊤
1 UrΣ
−1 r**), we obtain the**
equality of (11).

$$\Pr[\mbox{rank}(W)=r]=\Pr[\mbox{rank}(X_{1})=r]\tag{10}$$ $$=\Pr[\mbox{rank}(V_{r,l})=r].\tag{11}$$

In the next section we calculate this probability for a specific distribution in terms of l **as well as a measure**
of the coherence of Vr.

## Sampling Bound

Given the orthonormal matrix Vr**, we would like to**
find a choice of l such that Vr,l created by **uniform**
sampling has rank r **with high probability. As pointed** out in the previous section, a meaningful bound may not be possible for any l < n **if no assumption is made**
on Vr. Here we adopt the assumption that Vr **has low**
coherence, as defined in Definition 1. We then observe that by properties of SVD we have

$$\Pr\left(\text{rank}(V_{r,l})=r\right)=\Pr\left(\text{rank}(V_{r,l}^{\top}V_{r,l})=r\right).\tag{12}$$

Next, we define σ = kV
⊤

r,lVr,lk2 **and note that for 0** <
c < 1/σ, cV ⊤
r,lVr,l is an l×l **SPSD matrix with singular**
values less than one. Furthermore, I − cV ⊤
r,lVr,l **is also**
SPSD with

$$\Pr\left(\text{rank}(V_{r,l}^{\top}V_{r,l})=r\right)=\Pr\left(\|cV_{r,l}^{\top}V_{r,l}-I\|<1\right),\tag{13}$$  since $\|cV_{r,l}^{\top}V_{r,l}-I\|=1$ implies that the nullspace of 

cV ⊤
r,lVr,l is nonempty. Alternatively, if c ≥ 1/σ**, then**
$$\Pr\left(\text{rank}(V_{r,l}^{\top}V_{r,l})=r\right)\geq\Pr\left(\|cV_{r,l}^{\top}V_{r,l}-I\|<1\right),\tag{14}$$  since, for large enough $c$, we could have $\|cV_{r,l}^{\top}V_{r,l}-1$
r,lVr,l −
Ik ≥ **1 even if rank(**V
⊤

r,lVr,l) = r**. Thus the inequality**
in (14) holds for any constant c > **0, i.e., the probability on the RHS of (14) serves as a lower bound for the**
probability of interest to us.

$$({\boldsymbol{\delta}})$$

The probability on the RHS of (14) has been studied in previous compressive sampling literature. Specifically, Cand`es and Romberg (2007) makes use of a main lemma of Rudelson (1999) to derive Theorem 2, which provides us with our desired lower bound.

Theorem 2 **( (Cand`es and Romberg, 2007) Thm.**
1.2). **Define** Vr ∈ R
n×r**such that** V
⊤

r Vr = I **and let**
Vr,l ∈ R
l×rbe generated from Vr **by sampling rows**
uniformly at random. Then, the following holds with probability at least 1 − δ,

$$\|\frac{n}{l}V_{r,l}^{\top}V_{r,l}-I\|<\frac{1}{2}\,,$$
$$(15)$$

$$(16)$$

, **(15)**
$\left(\underset{\text{}}{\mathrm{9}}\right)$. 

$$\begin{array}{l}{{f o r\ a n y\ l\ {t h a t\ s a t i s f i e s,}}}\end{array}$$
$$l\geq r\mu^{2}(V_{r})\operatorname*{max}{\big(}C_{1}\log(r),C_{2}\log(3/\delta){\big)},$$
, **(16)**
 *where $C_1$ and $C_2$ are positive constants*. 
Note that our definition of coherence and statement of Theorem 2 are modified to account for the fact that V
⊤

r Vr = I as oppose to nI**, as in Cand`es and Romberg**
(2007). Also, Vr **is not square as assumed in the original theorem, however it can be verified that the proof**
holds even for this case. By making use of Theorem 2, we can now answer the question regarding the number of columns needed to sample from G **in order to obtain an exact reconstruction via the Nystr¨om method. Theorem 3 presents a**
bound on l **for matrix completion in terms of** µ.

Theorem 3. Let G ∈ R
n×n be a rank-r **SPSD matrix**
and assume r ∈ O(1/δ)**, then it suffices to sample** l ≥
O(rµ2(Vr**) log(**δ
−1)
**columns to have with probability**
at least 1 − δ,

$$\|G-\tilde{G}_{k}\|=0\,.$$
$$(17)$$

Proof. **Theorem 1 states sufficient conditions for exact matrix completion. Equations (10) and (11) reduce these sufficient conditions to a condition on the**
rank of Vr,l. Equations (12) and (14) further reduce