ilqar Ramazanli<EMAIL_ADDRESS>
Barnabas Poczos<EMAIL_ADDRESS>
Carnegie Mellon University

# Optimal Adaptive Matrix Completion

###### Abstract

We study the problem of exact completion for $m\times n$ sized matrix of rank
$r$ with the adaptive sampling method. We introduce a relation of the exact
completion problem with the sparsest vector of column and row spaces (which we
call sparsity-number here). Using this relation, we propose matrix completion
algorithms that exactly recovers the target matrix. These algorithms are
superior to previous works in two important ways. First, our algorithms
exactly recovers $\mu_{0}$-coherent column space matrices by probability at
least $1−\epsilon$ using much smaller observations complexity than -
$\mathcal{O}(\mu_{0}rn\mathrm{log}\frac{r}{\epsilon})$—the state of art
(Balcan and Zhang (2016)). Specifically, many of the previous adaptive
sampling methods require to observe the entire matrix when the column space is
highly coherent. However, we show that our method is still able to recover
this type of matrices by observing a small fraction of entries under many
scenarios. Second, we propose an exact completion algorithm, which requires
minimal pre-information as either row or column space is not being highly
coherent. We provide an extension of these algorithms that is robust to sparse
random noise. Besides, we propose an additional low-rank estimation algorithm
that is robust to any small noise by adaptively studying the shape of column
space. At the end of the paper, we provide experimental results that
illustrate the strength of the algorithms proposed here.

###### keywords:

Low rank completion, exact recovery, active learning, combinatorial analysis

##  1 Introduction

In this paper, we illustrate how adaptivity helps us to reach theoretical
lower bounds concerning observation count in the matrix completion problem. In
modern data analysis, it has been presented that in many scenarios, adaptive
sensing and sampling can work more efficiently than passive methods (Haupt et
al., 2011; Warmuth and Kuzmin, 2008). Our main objective is to further
optimize adaptive sampling by minimizing the number of observations needed to
recover the target matrix entirely. We show how to recover the entire low-rank
matrix by observing information-theoretically least number of entries in
various settings.
Low-rank matrix completion plays a significant role in many real-world
applications, including camera motion inferring, multi-class learning,
positioning of sensors, and gene expression analysis (Balcan and Zhang, 2016;
Krishnamurthy and Singh, 2013). In gene expression analysis, the target matrix
represents expression levels for various genes across several conditions.
Measuring gene expression, however, is expensive, and we would like to
estimate the target matrix with a few observations as possible. In this paper,
we provide an algorithm that can be used for matrix completion from limited
data. Roughly speaking, to find each unknown expression level, we are supposed
to do multiple measurements. Each of the additional measurements has its extra
cost. Naturally, we aim to solve the entire problem using the least possible
measurement cost.
Krishnamurthy and Singh (2013, 2014) illustrated how adaptive sampling reduces
observation complexity compared to passive sampling. These results were two of
the earliest algorithms that were robust against coherent row space. Like many
other results in the literature, these algorithms also heavily rely on the
incoherence of the column space. At first, authors showed for an $n\times n$
sized, rank $r$ matrix, with column space coherence of $\mu_{0}$, can be
exactly recovered using just $\mathcal{O}(n\mu_{0}r^{1.5}\log{r})$
observations (2013), then this result optimized to
$\mathcal{O}(n\mu_{0}r\log^{2}{r})$ in the later work (2014). Recently, Balcan
and Zhang (2016) further improved previous results by proposing algorithm that
performs $\mathcal{O}(n\mu_{0}r\log{r})$ observations to accomplish the task.
The main goal of this paper to give a new approach to the exact recovery
problem using the sparsest vector of column and row spaces instead of
coherence. Finding sparsest vector has been in the focus of the research
attention for a long time (McCormick (1983), Qing Qu and Wright (2015),
Coleman and Pothen (1986)). However, to the best of our knowledge, it is the
first time applied to active matrix completion in this paper.
In this particular work, we approach the exact completion problem in various
given pre-information settings. Our first algorithm requires the precise value
of the rank and no other information. Our second algorithm does not request
any information except knowing that either column or row space is not highly
coherent. For comparison, as we discuss in the next sections, previous
adaptive sampling recovery algorithms require the value of
$nr\mu_{0}\mathrm{polylog}{\frac{r}{\epsilon}}$, which implicitly requests
estimation or exact value of $r$ and $\mu_{0}$.

##### Our Contributions.

In light of the above discussion, we state the main contributions of this
work.

  * •

Relation of the sparsest vector of the column and row space and the problem of
exact recovery has been studied in detail. An exact completion algorithm is
proposed with respect to these vectors. Moreover, using the relation of the
sparsest vector to coherence number, we show that the proposed method exactly
recovers the underlying low-rank matrix using less observation than the state
of the art.

  * •

We provide efficient algorithms that require minimal information as
$\mathbf{ERR}$ (rank), $\mathbf{ERRE}$ (either row or column space is not
coherent). Moreover, we show the observation complexity of these algorithms is
upper bounded by $\mathcal{O}(nr\mu_{0}\log{\frac{r}{\epsilon}})$. (the
expression for observation complexity is provided in the next sections after
all the necessary definitions are given).

  * •

To the best of our knowledge, all previous adaptive sampling methods need to
observe entire matrix if the underlying matrix has a highly coherent column
space. In the algorithm $\mathbf{EREI}$ we show that having incoherent row
space can be a backup and we can still recover these matrices using a small
fraction of entries even it has highly coherent column space.

  * •

We extend our exact recovery method to make it robust to sparse random noise
in columns similar to Balcan and Zhang (2016). Besides, we provide a low-rank
estimation method that is robust to any small noise, relying on the adaptive
estimation of the angle between the underlying subspace and estimated
subspace.

##### Related Work.

The power of adaptive sampling had been illustrated even earlier than
Krishnamurthy and Singh (2013). (Haupt et al., 2011; Malloy and Nowak, 2011;
Balakrishnan and Singh, 2012; T‘anczos and Castro, 2013) showed that under
certain hypothesis, adaptive sampling outperforms all passive schemes.
Exact recovery and matrix completion has been studied extensively under
passive schemes as well. Nuclear norm minimization is one of the most popular
methods Gross (2011). Candes and Recht (2009) and Recht (2011) showed that
$\Omega((m+n)r\mathrm{max}(\mu_{0}^{2},\mu_{1}^{2})\log^{2}{n_{2}})$
observations are enough to recover an $m\times n$ matrix of rank $r$ using
nuclear norm minimization, where $\mu_{0}$ and $\mu_{1}$ correspond to column
and row space coherence parameters. Using the same technique, Candés and Tao
(2010) showed that under the uniform sampling setting we need at least
$\Omega(mr\mu_{0}\log{n})$ observations to recover the matrix exactly. This
result implies the near optimality of nuclear norm minimization. Another work
using nuclear norm minimization is due to Chen et al. (2014), in which they
show how to recover coherent $n\times n$ sized matrix of rank $r$ using just
$\mathcal{O}(nr\log^{2}r)$ observations.
Koltchinskii et al. (2011) showed how to use a nuclear norm minimization
approach to approximate noisy low-rank matrices under some global information
conditions. This work assumes that $\mu_{0}$ (coherence of column space) is
below a given threshold. This result has a similar flavor to ours in that it
works even when there is less initial knowledge about the target matrix.
Later, this result was extended to a point where without any assumption on
$\mu_{0}$ the target matrix could be approximated. However, the reconstruction
error of approximation becomes worse in this case Mai and Alquier (2015).
There are other approaches for noisy matrix completion which they mainly focus
on parameters that describe how much information an observation reveals
Keshavan and Oh (2010); Negahban and Wainwright (2012).

##  2 Preliminaries

##### Notations.

Let $\mathbf{M}$ denote the underlying $m\times n$ sized rank-$r$ matrix that
we target to recover. For any positive integer $n$, let $[n]$ represent the
set $\\{1,2,...,n\\}$. For any vector $x=(x_{1},x_{2},...,x_{n})$ of size $n$,
$\|x\|_{p}$ will denote the $L_{p}$ norm of it. We call $x_{i}$ the $i$’th
coordinate of $x$. For any, $\Omega\subset[n]$ let $x_{\Omega}$ denote the
induced subvector of $x$ from coordinates $\Omega$. For instance, for the
vector $x=(1,2,4,8,9)$ and $\Omega=\\{1,3\\}$, $x_{\Omega}$ represents the
vector $(1,4)$. For any $\mathbf{R}\subset[m]$, $\mathbf{M}_{\mathbf{R}:}$
stands for an $|\mathbf{R}|\times n$ sized submatrix of $\mathbf{M}$ that rows
are restricted by $\mathbf{R}$. We define $\mathbf{M}_{:\mathbf{C}}$ in a
similar way for restriction with respect to columns. Intuitively,
$\mathbf{M}_{\mathbf{R}:\mathbf{C}}$ defined for
$|\mathbf{R}|\times|\mathbf{C}|$ sized submatrix of $\mathbf{M}$ with rows
restricted to $\mathbf{R}$ and columns restriced to $\mathbf{C}$. Moreover,
for the special case $\mathbf{M}_{i:}$ stands for $i$-th row and
$\mathbf{M}_{:j}$ stands for the $j$’th column. Similarly,
$\mathbf{M}_{i:\mathbf{C}}$ will represent the restriction of the row $i$ by
$C$ and $\mathbf{M}_{\mathbf{R}:j}$ represents restriction of the column $j$
by $\mathbf{R}$. $\theta(u,v)$ stands the angle between vectors $u$ and $v$.
Moreover, $\theta(u,\mathbb{V})=\mathrm{min}\\{\theta(u,v)|v\in\mathbb{V}\\}$
and
$\theta(\mathbb{U},\mathbb{V})=\mathrm{max}\\{\theta(u,\mathbb{V})|u\in\mathbb{U}\\}$
for subspaces $\mathbb{U}$ and $\mathbb{V}$. The projection operator to
subspace $\mathbb{U}$ will be represented by $\mathcal{P}_{\mathbb{U}}$.

###  2.1 Problem Setup

##### Coherence.

One of the critical factors in the matrix completion problem is due to the
coherence parameter of the target matrix (H.Zhang, 2015; Cand‘es and Plan,
2010). We define the coherence of an $r$-dimensional subspace $\mathbb{U}$ of
$\mathbb{R}^{n}$ in the following way:

$\displaystyle\mu(\mathbb{U})=\frac{n}{r}\underset{1\leq j\leq
n}{\max}||\mathcal{P}_{\mathbb{U}}e_{j}||^{2},\vspace*{-3mm}$

where $e_{j}$ denotes the j-th standard basis element and
$\mathcal{P}_{\mathbb{U}}$ represents the orthogonal projection operator onto
the subspace $\mathbb{U}$. It is easy to see that if $e_{j}\in\mathbb{U}$ for
some $j\in[n]$, then the coherence will attain its maximum value:
$\mu(\mathbb{U})=\frac{n}{r}$. We can see that if $\mathbb{U}$ is equally
distant from each standard basis vectors, then $\mu(\mathbb{U})$ will be close
to $1$, and additionally, it is lower bounded by $1$.

##### Sparsest vector / sparsity number.

We unify $L_{0}$ norm of a vector, $L_{0}$ semi-norm of a matrix, $L_{0}$
semi-norm of the basis matrix of a subspace under the name of nonsparsity-
number for ease of readability. Furthermore, we call completion of these norms
as sparsity-number. We can see precise definitions below :
Nonsparsity-number of a vector $x\in\mathbb{R}^{m}$ represented by $\psi(x)$
and defined as $\psi(x)=\|x\|_{0}$. Nonsparsity-number of an $m\times n$ sized
matrix $\mathbf{M}$ and a subspace $\mathbb{U}\subseteq\mathbb{R}^{m}$ also
represented by $\psi$ and defined as:

$\displaystyle\psi(\mathbf{M})=\mathrm{min}\\{\psi(x)|x=\mathbf{M}z\text{ and
}z\notin\mathrm{null}(\mathbf{M})\\}\hskip
42.67912pt\psi(\mathbb{U})=\mathrm{min}\\{\psi(x)|x\in\mathbb{U}\text{ and
}x\neq 0\\}$

Similarly, sparsity-number of vectors, matrices and subspaces all are
represented by $\overline{\psi}$ and they are just completion of nonsparsity-
nunmber.

$\displaystyle\overline{\psi}(x)=m-\psi(x)\hskip
56.9055pt\overline{\psi}(\mathbf{M})=m-\psi(\mathbf{M})\hskip
56.9055pt\overline{\psi}(\mathbb{U})=m-\psi(\mathbb{U})$

The space sparsity-number for matrices provides a novel and easy way to
analyze adaptive matrix completion algorithms. In many adaptive matrix
completion methods, a crucial step is to decide whether a column is (or is
not) contained in a given subspace. Ideally, we would like to make this
decision as soon as possible before observing the entire column vector. In
this paper, we show that sparsity-number helps us to decide whether a
partially observed vector can be contained in a given subspace or not. In
lemma 3.1, we provide an answer to this question simply.

###  2.2 Matrix Completion with Adaptive Sampling

We want to present an algorithm due to Krishnamurthy and Singh (2013) here
before providing our main results in the next section. Authors proposed an
adaptive algorithm that can recover $n\times n$ sized rank-$r$ matrices using
$\mathcal{O}(n\mu_{0}r^{1.5}\log{r})$ observations, which was indeed better
than known state of the art $\mathcal{O}(n\mu_{0}r^{2}\log^{2}{n})$ for
passive algorithms (2011). The algorithm studies column space by deciding
whether the partially observed column is linearly independent with previously
fully observed columns. Authors show observing
$\mathcal{O}(\mu_{0}r^{1.5}\log{\frac{r}{\epsilon}})$ observations for each
column is enough to make the decision for linear independence with probability
$1-\epsilon$. The algorithm below describes the details of the proposed
algorithm.

KS2013: Exact recovery Krishnamurthy and Singh (2013).

Input: $d=\mathcal{O}(\mu_{0}r^{1.5}\log{\frac{r}{\epsilon}})$
Initialize: $k=0,\widehat{\mathbf{U}}^{0}=\emptyset$

1: Draw uniformly random entries $\Omega\subset[m]$ of size $d$

2: for $i$ from $1$ to $n$ do

3: if
$\|\mathbf{M}_{\Omega:i}-{\mathcal{P}_{\mathbf{\widehat{U}_{\Omega}^{k}}}}\mathbf{M}_{\Omega:i}\|>0$

4: Fully observe $\mathbf{M}_{:i}$

5:
$\widehat{\mathbf{U}}^{k+1}\leftarrow\widehat{\mathbf{U}}^{k}\cup\mathbf{M_{:i}}$,
Orthogonalize $\widehat{\mathbf{U}}^{k+1}$, $k=k+1$

6: otherwise:
$\widehat{\mathbf{M}}_{:i}=\widehat{\mathbf{U}}^{k}{\widehat{\mathbf{U}}^{k^{+}}_{\Omega}}\widehat{\mathbf{M}}_{\Omega:i}$

Output: $\widehat{\mathbf{M}}$

Later, authors improved the observation complexity to
$\mathcal{O}(n\mu_{0}r\log^{2}{\frac{r}{\epsilon}})$ in a proceeding work
(2014). Then, another improvement due to Balcan and Zhang (2016) further
reduced this complexity to
$\mathcal{O}(n\mu_{0}r\log{\frac{r}{\epsilon}})$-current state of the art
using similar setting and algorithm.

##  3 Main Results

In this section, we provide the theoretical results of this paper. First, we
build the bridge between space sparsity-number and the exact completion
problem. Then, we show using this connection its possible to give efficient
algorithms.

###  3.1 Optimal Observation for Each Column

Before proceeding to more advanced algorithms, we target to answer one
fundamental question. What is the specific number of entries in
$\mathbf{KS2013}$ to observe in a column that allows us to deterministically
decide whether it is independent or dependent on previous columns? In what
follows, we prove sparsity-number of the column space answers this question :

######  Lemma 3.1.

Let $\mathbb{U}$ be a subspace of $\mathbb{R}^{m}$ and $x^{1},x^{2},...,x^{n}$
be any set of vectors from $\mathbb{U}$. Then the linear dependence of
$x^{1}_{\Omega},x^{2}_{\Omega},...,x^{n}_{\Omega}$ implies linear dependence
of $x^{1},x^{2},...,x^{n}$, for any $\Omega\subset[m]$ such that
$|\Omega|>\overline{\psi}(\mathbb{U})$.

Merging the idea of the algorithm $\mathbf{KS2013}$ with lemma 1 we get an
algorithm that is presented and discussed in the Supplementary Materials,
whose can recover low-rank matrices deterministically ($\mathbf{ERCS}$).
Shortly, setting $d=\psi(\mathbf{M})+1$ is enough to ensure the underlying
matrix will be recovered with probability $1$. Moreover, we analyze the
following properties of the algorithm :

  * •

Lemma 1 is tight. Setting $d=\psi(\mathbb{U})$ would fail statement of the
lemma for some matrices.

  * •

If $\overline{\psi}(\mathbb{U})+1=r$ satisfied, then the observation
complexity of the algorithm is equal to $(n+m-r)r$ which is degree of freedom
of rank-$r$ matrices.

Moreover, we suggest an exact completion problem where each entry has
heterogeneous observation cost and proposed an efficient solution to that
given that sparsity number of row space is known.
Due to the challenge of finding space sparsity-number of the column/row space
of the underlying matrix, we didn’t provide the algorithm and analysis in the
main text. However, having any lower bound to the sparsity-numbers would also
be enough successful termination of the algorithm.

###  3.2 Exact Completion Problem

Here, we provide an algorithm that exactly recovers a target matrix under the
active setting. As we discussed before, one of the strengths of the results of
Krishnamurthy and Singh (2013, 2014); Balcan and Zhang (2016) is that the
algorithm is its robustness to highly coherent row space compared to previous
results as Recht (2011). However, we notice that these algorithms are
independent of row space and treat any row space equally. This phenomenon
arises a natural question, whether there is an algorithm which enjoys
properties of row space to optimize these algorithms further. For example, we
can see the following matrices having the same rank $r=2$ and column space
coherence $\mu_{0}=2$. The only difference is due to the coherence of row
space, which is $3$ for $\mathbf{A}$ and near to $1$ for matrix $\mathbf{B}$.
Similarly, row space sparsity-number is $1$ for the matrix A and $4$ for the
matrix B.

$\mathbf{A}=\begin{bmatrix}1&2&2&2&2&2\\\ 0&2&2&2&2&2\\\ 0&2&2&2&2&2\\\
0&2&2&2&2&2\\\ \end{bmatrix}\hskip
56.9055pt\mathbf{B}=\begin{bmatrix}1&0&1&2&3&4\\\ 0&1&2&3&4&5\\\
0&1&2&3&4&5\\\ 0&1&2&3&4&5\\\ \end{bmatrix}$

As previous methods are mainly based on the value of the size of the matrix,
$r$, and $\mu_{0}$, these methods treat both these matrices equally. Indeed
the first column of the matrix $\mathbf{A}$ is crucial to study the column
space. That’s why we don’t want to take the risk of missing the necessary
information on this column. That’s why we end up observing many entries in
each column to make sure we will not miss this column. However, it is entirely
different for the matrix $\mathbf{B}$; any missed column can be replaced by
any other one in the study of the column space. That’s why it should give us
the flexibility of observing less number of entries in each column.

####  3.2.1 Exact completion for rank r matrices

In the following algorithm, we propose a method that exactly recovers the
$m\times n$ sized rank $r$ underlying matrix, using just exact information of
rank $r$. The idea of the algorithm is to find $r$-many linearly independent
rows and columns and recover the remaining entries based on them. Finding the
linearly independent columns is rely on simple linear algebra fact that if
columns of $\mathbf{M}_{R:C}$ are linearly independent, then so are columns of
$\mathbf{M}_{:C}$. The statement is valid for rows as well symmetrically.
Then, all we need to do is to wait for detecting $r$ many independent columns
and rows. Indeed the algorithm does not require an estimate or exact
information of coherence as opposed to $\mathbf{KS2013}$, 2016; 2014
(coherence is crucial to compute $d$ in input phase). The improvement for
observation complexity can be observed in the following theorem and corollary.

ERR: Exact recovery for rank $r$ matrices.

Input: Rank of the target matrix - $r$
Initialize: $R=\emptyset$, $C=\emptyset$, $\widehat{r}=0$

1: while $\widehat{r}<r$ do

2: for $j$ from $1$ to $n$ do

3: Uniformly pick an unobserved entry $i$ from $\mathbf{M}_{:j}$

4: $\widehat{R}={R}\cup\\{i\\},\widehat{C}={C}\cup\\{j\\}$

5: If $\mathbf{M}_{\widehat{R}:\widehat{C}}$ is nonsingular

6: Fully observe $\mathbf{M}_{:j}$ and $\mathbf{M}_{i:}$ and set
$R=\widehat{R}$ , $C=\widehat{C}$ , $\widehat{r}=\widehat{r}+1$

7: Orthogonalize column vectors in $C$ and assign to $\widehat{\mathbf{U}}$

8: for each column $j\in[n]\setminus C$ do

9:
$\widehat{\mathbf{M}}_{:j}=\widehat{\mathbf{U}}{\widehat{\mathbf{U}}_{R:}}^{+}\widehat{\mathbf{M}}_{R:j}$

Output: $\widehat{\mathbf{M}}$

######  Theorem 3.2.

Let $r$ be the rank of underlying $m\times n$ sized matrix $\mathbf{M}$ with
column space $\mathbb{U}$ and row space $\mathbb{V}$. Then, $\mathbf{ERR}$
exactly recovers the underlying matrix $\mathbf{M}$ with probability at least
$1-\epsilon$ using number of observations at most:

$(m+n-r)r+\mathrm{min}\Big{(}2\frac{mn}{{\psi}(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n\Big{)}.$

######  Corollary 3.3.

Observation complexity of $\mathbf{ERR}$ studied for three different case
below:

  * •

if $\psi(\mathbb{V})=\mathcal{O}(1)$ then observation complexity is upper
bounded by $(m+n-r)r+2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})}\\\
=(m+n-r)r+\mathcal{O}\big{(}nr\mu_{0}\log{(\frac{r}{\epsilon})}\big{)}$. (
this bound matches with Balcan and Zhang (2016), however in Supplementary
Material we discuss why many times it is smaller quantity)

  * •

if $\psi(\mathbb{V})=\Theta(r)$ then observation count is upper bounded by
$(m+n-r)r+\mathcal{O}\Big{(}\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{r}n\Big{)}\\\
=(m+n-r)r+\mathcal{O}\big{(}n\mu_{0}(r+\log{\frac{1}{\epsilon}})\big{)}$.
Selecting $\epsilon=\frac{1}{2^{\mathcal{O}(r)}}$ gives bound of
$mr+\mathcal{O}(n\mu_{0}r)$

  * •

if $\psi(\mathbb{V})=\Theta(n)$ then observation count is upper bounded by
$(m+n-r)r+\mathcal{O}\Big{(}\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{n}n\Big{)}\\\
=(m+n-r)r+\mathcal{O}\big{(}\mu_{0}r(r+\log{\frac{1}{\epsilon}})\big{)}$
Selecting $\epsilon=\frac{1}{2^{\mathcal{O}(r)}}$ gives bound:
$\mathcal{O}((m+n-r)r)$

Note that, for the last case, observation complexity is bounded by
$\mathcal{O}((m+n-r)r)$, which is absolute lower bound for any algorithm.

####  3.2.2 Exact Recovery While Rank Estimation

In this section, we solve the exact completion problem in a slightly different
setup. $\mathbf{ERR}$ assumes that we know the exact rank of the underlying
matrix. However, here we assume that we don’t have this information. Therefore
we don’t know precisely at which point the process of searching a new
independent row/column should stop. In what follows, we show that if at a
given state new independent column/row not detected for long enough time, then
it means that it is likely no more one exists. We formalize this statement in
the following theorem.

ERRE: Exact recovery while rank estimation.

Input: $T$-delay parameter at the end of algorithm
Initialize: $R=\emptyset,C=\emptyset,\widehat{r}=0,delay=0$

1: while $delay<T$ do

2: $delay=delay+1$

3: for $j$ from $1$ to $n$ do

4: Uniformly pick an unobserved entry $i$ from $\mathbf{M}_{:j}$

5: $\widehat{R}={R}\cup\\{i\\},\widehat{C}={C}\cup\\{j\\}$

6: If $\mathbf{M}_{\widehat{R}:\widehat{C}}$ is nonsingular :

7: Fully observe $\mathbf{M}_{:j}$ and $\mathbf{M}_{i:}$ and set
$R=\widehat{R}$ , $C=\widehat{C}$ , $\widehat{r}=\widehat{r}+1,delay=0$

8: Orthogonalize column vectors in $C$ and assign to $\mathbf{U}$

9: for each column $j\in[n]\setminus C$ do

10:
$\widehat{\mathbf{M}}_{:j}=\widehat{\mathbf{U}}{\widehat{\mathbf{U}}_{R:}}^{+}\widehat{\mathbf{M}}_{R:j}$

Output: $\widehat{\mathbf{M}},\widehat{r}$

######  Theorem 3.4.

Let $r$ be the rank of underlying $m\times n$ sized matrix $\mathbf{M}$ with
column space $\mathbb{U}$ and row space $\mathbb{V}$. Then, $\mathbf{ERRE}$
exactly recovers the underlying matrix $\mathbf{M}$ while estimating rank with
probability at least
$1-(\epsilon+e^{-T\frac{\psi(\mathbb{U})\psi(\mathbb{V})}{m}})$ using number
of observations at most:

$\displaystyle(m+n-r)r+Tn+\mathrm{min}\Big{(}2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n)\Big{)}$

######  Corollary 3.5.

Lets assume that either $\psi(\mathbb{U})$ or $\psi(\mathbb{V})$ is big enough
i.e. $\psi(\mathbb{U})\psi(\mathbb{V})\geq m$. For a given $\epsilon$ set
$T=\log{\frac{1}{\epsilon}}$, then $\mathbf{ERRE}$ recovers underlying matrix
with probability $1-2\epsilon$ using just

$\displaystyle(m+n-r)r+n\log{\frac{1}{\epsilon}}+\mathrm{min}\Big{(}2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n\Big{)}$

We refer to the analysis of corollary 3.3 to understand this expression
better.

####  3.2.3 Exact Recovery with Estimated Information

In this section, we approach the exact completion problem under the scenario
we have estimated pre-information, using ideas from previous sections. This
setting is similar to $\mathbf{KS2013}$, Balcan and Zhang (2016) and 2014 that
estimated values of rank $r$ and $\mu_{0}$ \- coherence of column space got
used. Methods proposed in these papers work efficiently under the condition
row spaces are highly coherent. An in-depth analysis of these methods tells us
that these algorithms designed for the highest value of row space coherence,
and they also work perfectly well for remaining cases. In the following
algorithm, we somehow extend these algorithms to a method that can enjoy the
properties of row space; meanwhile, performing similarly good for highly
coherent row space matrices.
Note that the algorithm below designed and analyzed under the condition that
estimated r, $\psi(\mathbb{U})$, and $\psi(\mathbb{V})$ provided. However,
under the condition just estimated $r$ and $\mu_{0}$ provided, we can set
$\psi(\mathbb{V})$ to be equal to 1 and use the inequality
$\mu_{0}r>\frac{m}{k}$ (proved in the Supplementary Material) to transfer the
information of $\mu_{0}$ to $\psi(\mathbb{U})$. Then the algorithm below will
perform as good as Balcan and Zhang (2016) with observation complexity of
$mr+\mathcal{O}(nr\mu_{0}\log{\frac{r}{\epsilon}})$.

EREI: Exact recovery with estimated information

Input: $r,\psi(\mathbb{U}),\psi(\mathbb{V})$
Initialize:
$R=\emptyset,k=0,\widehat{\mathbf{U}}^{0}=\emptyset,d=\mathrm{min}\Big{(}2\frac{m}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U}}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}\Big{)}$

1: Draw uniformly random entries $\Omega\subset[m]$ of size $d$

2: for $i$ from $1$ to $n$ do

3: if
$\|\mathbf{M}_{\Omega:i}-{\mathcal{P}_{\mathbf{\widehat{U}_{\Omega}^{k}}}}\mathbf{M}_{\Omega:i}\|>0$

4: Fully observe $\mathbf{M}_{:i}$

5:
$\widehat{\mathbf{U}}^{k+1}\leftarrow\widehat{\mathbf{U}}^{k}\cup\mathbf{M_{:i}}$,
Orthogonalize $\widehat{\mathbf{U}}^{k+1}$, $k=k+1$

6: Select a row $a\in\Omega\setminus R$ that,
$\mathbf{\widehat{U}_{R\cup\\{a\\}}^{k+1}}$ is rank $k+1$ then $R\leftarrow
R\cup\\{a\\}$

7: Draw uniformly random entries $\Delta\subset[m]\setminus R$ of size $d$ and
$\Omega=\Delta\cup R$

8: Observe entire $\mathbf{M}_{R:}$

9: for $i$ from $1$ to $n$ do

10: if $\mathbf{M}_{:i}$ not fully observed then :
$\widehat{\mathbf{M}}_{:i}=\widehat{\mathbf{U}}^{k}{\widehat{\mathbf{U}}^{k^{+}}_{R:}}\widehat{\mathbf{M}}_{R:i}$

Output: $\widehat{\mathbf{M}}$

Below we show the execution of the algorithm for $d=2$ and $r=1$. $a$ stands
for entries that is observed randomly, $a$ stands for entries that is observed
deterministically and $a$ stands for recovered entries without observing. Note
that $\Omega_{1}=\\{1,5\\},\Omega_{2}=\\{2,5\\},\Omega_{3}=\\{1,3\\}$ and
after 3-rd iteration $R$ becomes $\\{3\\}$ therefore, in fourth column
$\mathbf{M}_{3:4}$ observed deterministically, besides together random
observations $\Omega_{4}=\\{5,6\\}$. After all of the iterations completed, we
observe the entire $\mathbf{M}_{3:}$, and in the next step, we recover
remaining entries.

$\left[\begin{array}[]{cccc}\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}1}&\hbox{\pagecolor{white}3}&\hbox{\pagecolor{white}2}&\hbox{\pagecolor{white}3}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}2}&\hbox{\pagecolor{white}6}&\hbox{\pagecolor{white}4}&\hbox{\pagecolor{white}6}\\\
\end{array}\right]\left[\begin{array}[]{cccc}\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}1}&\hbox{\pagecolor{white}3}&\hbox{\pagecolor{white}2}&\hbox{\pagecolor{white}3}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}2}&\hbox{\pagecolor{white}6}&\hbox{\pagecolor{white}4}&\hbox{\pagecolor{white}6}\\\
\end{array}\right]\left[\begin{array}[]{cccc}\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}1}&\hbox{\pagecolor{white}3}&\hbox{\pagecolor{gray}2}&\hbox{\pagecolor{white}3}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}2}&\hbox{\pagecolor{white}6}&\hbox{\pagecolor{white}4}&\hbox{\pagecolor{white}6}\\\
\end{array}\right]\left[\begin{array}[]{cccc}\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}1}&\hbox{\pagecolor{white}3}&\hbox{\pagecolor{darkgray}2}&\hbox{\pagecolor{darkgray}3}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{gray}0}\\\
\hbox{\pagecolor{white}2}&\hbox{\pagecolor{white}6}&\hbox{\pagecolor{darkgray}4}&\hbox{\pagecolor{gray}6}\\\
\end{array}\right]\left[\begin{array}[]{cccc}\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{darkgray}1}&\hbox{\pagecolor{darkgray}3}&\hbox{\pagecolor{darkgray}2}&\hbox{\pagecolor{darkgray}3}\\\
\hbox{\pagecolor{white}0}&\hbox{\pagecolor{white}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{white}0}\\\
\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{gray}0}\\\
\hbox{\pagecolor{white}2}&\hbox{\pagecolor{white}6}&\hbox{\pagecolor{darkgray}4}&\hbox{\pagecolor{gray}6}\\\
\end{array}\right]\left[\begin{array}[]{cccc}\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{lightgray}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{lightgray}0}\\\
\hbox{\pagecolor{lightgray}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{lightgray}0}\\\
\hbox{\pagecolor{darkgray}1}&\hbox{\pagecolor{darkgray}3}&\hbox{\pagecolor{darkgray}2}&\hbox{\pagecolor{darkgray}3}\\\
\hbox{\pagecolor{lightgray}0}&\hbox{\pagecolor{lightgray}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{lightgray}0}\\\
\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{gray}0}&\hbox{\pagecolor{darkgray}0}&\hbox{\pagecolor{gray}0}\\\
\hbox{\pagecolor{lightgray}2}&\hbox{\pagecolor{lightgray}6}&\hbox{\pagecolor{darkgray}4}&\hbox{\pagecolor{gray}6}\\\
\end{array}\right]$

######  Theorem 3.6.

Let $r$ be the rank of underlying $m\times n$ sized matrix $\mathbf{M}$ with
column space $\mathbb{U}$ and row space $\mathbb{V}$. Then, with probability
$1-\epsilon$ the algorithm $\mathbf{EREI}$ exactly recovers the underlying
matrix $\mathbf{M}$ using number of observations at most

$\displaystyle(m+n-r)r+\mathrm{min}\Big{(}2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n\Big{)}$

######  Corollary 3.7.

Lets assume that we have estimated values of rank $r$, column space coherence
number $\mu_{0}$ and estimated row space sparsity-number is
$\psi(\mathbb{V})$. Then, if $\psi(\mathbb{V})$ is $\mathcal{O}(1)$ then
observation complexity is buounded by
$(m+n-r)r+\mathcal{O}(nr\mu_{0}\log{\frac{r}{\epsilon}})$ and if
$\psi(\mathbb{V})$ is $\mathcal{O}(n)$ then with probabiliy
$\frac{1}{2^{\mathcal{O}(r)}}$ the bound is $\mathcal{O}((m+n-r)r)$ which is
theoretical lower bound for exact completion problem.

###  3.3  Noisy Matrix Completion

Starting here, we analyze the completion problem with the condition that
entries of the underlying matrix can be noisy. Similar to Balcan and Zhang
(2016), we focus on two types of noise model: sparse random noise and bounded
noise. First, we assume that several columns of the matrix are completely
noisy, and we target to recover clean entries using as little as possible
observations. We show how to extend exact completion algorithms proposed here
to handle this type of noise. Second, we assume that each entry of the
underlying matrix can contain some small noise.

####  3.3.1 Sparse Random Noise

In this section, we discuss how to extend exact completion algorithms proposed
in this paper to the case that some of the columns have random noise that is
coming from the non-degenerate distribution $\mathcal{U}$. Here, we extend the
algorithm $\mathbf{EREI}$ to make it robust to this type of noise. AAs it is
discussed in 2016, if a column is an entirely random noise, then it should be
linearly dependent with the rest of the columns. It is trivial to notice that
a non-degenerate random noise will not be in a predefined subspace as much as
the subspace is not full-dimensional. Therefore, intuitively to clean noisy
columns, we should detect columns that without them the rank of the matrix
decrements. Surprisingly, this phenomenon can be related to space sparsity-
number. Given that  sparsity-number of row space is higher than one, none of
the columns of the underlying matrix satisfies this condition. This topic
further discussed in the Supplementary Material.
Therefore, we propose the method that whenever the underlying matrix having
coherent row space (or low value of $\psi(\mathbb{V})$). However, it is given
that the column space is recoverable, we run $\mathbf{EREI}$ with
$d=2\frac{m}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})}$ and at the end, all
of the columns that their deletion causes rank decrement are detected as
noise. For matrices that have highly incoherent row space or high value of
nonsparsity-number, we approach little differently because noise can immensely
effect $\psi(\mathbb{V})$. However, this quantity can be affected at most by
the number of noisy columns, and this fact is proven in the supplementary
material. Therefore, it is safe to condition if the number of noisy
columns-$a<\frac{\psi(\mathbf{V})}{2}$, we can safely use the same method as
$\mathbf{EREI}$ however, here $d$ will be twice larger $d$ than noise-free
case:
$d={\frac{4m}{\psi(\mathbb{U}{\psi(\mathbb{V})}}(r+2+\log{\frac{1}{\epsilon}})}$.
However, if the number of noisy columns-$a$ get closer to $\psi(\mathbf{V})$,
using $d=2\frac{m}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})}$ is more safe
as much as no further information provided. We detect noise columns similar to
the previous case. The advantage of this method is due to the efficiency of
the exact completion method. Furthermore, we plan to extend this result to
non-sparse noise in future works. The technical details of this method
provided in Supplementary Materials.

####  3.3.2 Bounded Deterministic Noise

In this section, we propose an algorithm that gives a low-rank estimation to a
matrix with small noise additional to a low-rank structure. Specifically, we
assume that the observed matrix $\mathbf{M}$ is created by adding small noise
to the underlying low-rank matrix $\mathbf{L}$.

$\displaystyle\mathbf{M}=\mathbf{L}+\zeta\hskip 14.22636pt\text{such
that}\hskip 14.22636pt\|\mathbf{L}_{:i}\|_{2}=1\hskip 8.53581ptand\hskip
8.53581pt\|\zeta_{:i}\|_{2}\leq\epsilon\hskip 8.53581pt\forall i\in[n]$

The main novelty of the algorithm provided here is to decide the number of
entries to be observed adaptively depending on the angle between estimated
column space and actual column space. This approach to observation complexity
opens further space for future improvements. In lemma 25 we show that the
angle between estimated space and actual space cannot be too much different
using similar argument to Balcan and Zhang (2016), and the angle between them
is upper bounded by $3\frac{\pi}{2}\sqrt{k\epsilon}$, which gives the worst
observation complexity for $\mathbf{LREBN}$ with
$d=\mathcal{O}(\mu(\mathbf{U})r\log^{2}{\frac{1}{\delta}}+mk\epsilon\log\frac{1}{\delta})$
which improves the previous rate
$\mathcal{O}(\mu(\mathbf{U})r\log^{2}{\frac{1}{\delta}}+mk\epsilon\log^{2}\frac{1}{\delta})$,
especially when $\epsilon$ is relatively big that the term $mk\epsilon$ is
dominating over $\mu(\mathbf{U})r\log^{2}{\frac{1}{\epsilon}}$.
Moreover, there are many cases that estimated angle is much smaller than
$\sqrt{k\epsilon}$. especially, when the basis vectors of the matrix
$\mathbf{L}$ are far enough by each other (the angles between them is big
enough) this quantity can be as small as $k\epsilon$, which in this case
observation complexity for a given column would be
$d=72\mu(\mathbf{U})r\log^{2}{\frac{1}{\delta}}+8mk^{2}\epsilon^{2}\log{\frac{r}{\delta}}$
which is further smaller.

LREBN: Low-rank estimation for bounded noise.

Input: $d=72\mu(\mathbf{U})r\log^{2}{\frac{1}{\delta}}$
Initialize:
$k=0,\widetilde{\mathbf{U}}^{0}=\emptyset,\tilde{\theta}(\widetilde{\mathbf{U}}^{0},\mathbf{U}^{0})=0$

1: Draw uniformly random entries $\Omega\subset[m]$ of size $d$

2: for $i$ from $1$ to $n$ do

3: if
$\|\mathbf{M}_{\Omega:i}-{\mathcal{P}_{\mathbf{\widehat{U}_{\Omega}^{k}}}}\mathbf{M}_{\Omega:i}\|>(1+\epsilon)\Big{(}\sqrt{\frac{3d}{2m}}\tilde{\theta}({\mathbf{U}}^{k},\widetilde{\mathbf{U}}^{k})+\sqrt{\frac{3dk\epsilon}{2m}}\Big{)}$

4: Fully observe $\mathbf{M}_{:i}$

5:
$\widetilde{\mathbf{U}}^{k+1}\leftarrow\widetilde{\mathbf{U}}^{k}\cup\mathbf{M_{:i}}$,
Orthogonalize $\widehat{\mathbf{U}}^{k+1}$

6: Estimate $\tilde{\theta}({\mathbf{U}}^{k},\widetilde{\mathbf{U}}^{k})$ the
upper bound for $\theta({\mathbf{U}}^{k},\widetilde{\mathbf{U}}^{k})$

7:
$d=72\mu(\mathbf{U})r\log^{2}{\frac{1}{\delta}}+8m\tilde{\theta}(\widetilde{\mathbf{U}}^{k},\mathbf{U}^{k})^{2}\log{\frac{r}{\delta}}$
and set $k=k+1$

8: Draw uniformly random entries $\Omega\subset[m]$ of size $d$

9: otherwise:
$\widetilde{\mathbf{M}}_{:i}=\widehat{\mathbf{U}}^{k}{\widehat{\mathbf{U}}^{k^{+}}_{\Omega}}\widetilde{\mathbf{M}}_{\Omega:i}$

Output: $\widetilde{\mathbf{M}}$

To estimate the upper bound
$\tilde{\theta}({\mathbf{U}}^{k},\widetilde{\mathbf{U}}^{k})$ for
$\theta({\mathbf{U}}^{k},\widetilde{\mathbf{U}}^{k})$ we use the idea due to
blum:

$\displaystyle\tilde{\theta}(\widetilde{\mathbf{U}}^{k},\mathbf{U}^{k})=\frac{\pi}{2}\frac{\theta(u_{k},\widetilde{u}_{k})}{\theta(\widetilde{u}_{k},\widetilde{\mathbf{U}}^{k-1})-\tilde{\theta}(\widetilde{\mathbf{U}}^{k-1},{\mathbf{U}}^{k-1})}+\tilde{\theta}(\widetilde{\mathbf{U}}^{k-1},{\mathbf{U}}^{k-1})$

######  Theorem 3.8.

Given the $\mathbf{L}$ be an $m\times n$ sized underlying rank-$r$ matrix
where each column has $\ell_{2}$ norm of 1. Moreover, $\mathbf{M}$ is a full
rank matrix where each column is created by adding at most $\ell_{2}$
norm$-\epsilon$ noise to the corresponding column of $\mathbf{L}$. Then the
algorithm $\mathbf{LREBN}$ estimates underlying matrix with $\ell_{2}$ norm of
error is $\Theta(\frac{m}{d}\sqrt{k\epsilon})$ by sampling
$d=72\mu(\mathbf{U})r\log^{2}{\frac{1}{\delta}}+8m\tilde{\theta}(\widetilde{\mathbf{U}}^{k},\mathbf{U}^{k})^{2}\log{\frac{r}{\delta}}$
entries in each column

##  4 Experimental Results

Experiments for Synthetic Data: We tested all of our exact completion
algorithms-$\mathbf{ERR}$,$\mathbf{ERRE}$ and $\mathbf{EREI}$ for
synthetically generated low-rank matrices. To generate $m\times n$ sized
underlying low-rank matrix $\mathbf{M}$, we created $m\times r$ and $r\times
n$ sized matrices $\mathbf{X,Y}$, where
$\mathbf{X}_{i,j},\mathbf{Y}_{i,j}\sim\mathcal{N}(0,1)$ and we set
$\mathbf{M}=\mathbf{XY}$. We test our method for fixed $r=5$ and $r=10$ with
$n$ varying over $\\{1000,2000,\ldots,12000\\}$. Similarly, we fixed $n=3000$
and varied $r$ over $\\{1,2,\ldots,12\\}$. Moreover, we classified matrices
into four types for coherence/incoherence of the column and row space. From
the table below, we can get the comparison of the performance of our
algorithms to previous methods (Balcan and Zhang (2016); Krishnamurthy and
Singh (2013, 2014); chenexp). We refer to Supplementary Material regarding
generation method of coherent/incoherent, row/column subspace matrices.

|  |
---|---|---
|  |
|  |
|  |

##### Experiments for real data:

We tested the low-rank estimation method using adaptive sampling with respect
to the angle between estimated and underlying subspace. Experiments run on
Hopkins 155 dataset. Hopkins dataset contains 155 images, and each of them
represents two or three motion objects. The trajectory of motion of each
object lies in a low-rank subspace. We reshape 3-dimensional tensor data to
2-dimensional matrix. Almost all reshaped matrices are smaller than the size
$500\times 50$. As the constants are high in the algorithm LREBN and works of
previous authors together with the multiplicative term of $\log(1/\epsilon)$,
applying for these numbers here concludes observing the entire column.
Therefore, instead of sampling precisely these numbers, we use other numbers
that generated using a similar idea. If a newly added independent column has a
high angle with the estimated subspace, then we don’t increase the number of
samples for the next columns. Otherwise, we increase the value of the
d-observation count parameter. We compare this method to the method that no
matter what is the angle, we always increase $d$ once a new independent column
detected. $\epsilon$ set to $0.0003$, and the $\ell_{2}$ norm of the column
normalized using $\ell_{2}$ norm of observed entries. We run each of the
experiments 20 times and take the average of them to compute corresponding
error and sample size. On the left side, we see plots for $\ell_{\infty}$-norm
of estimation error in a given column. In the right, we see the number of
observations used during the execution. Each row below corresponds to
different images. Computing average error over columns and average sample
sizes conclude that the adaptive method roughly gives $8-12\%$ benefit on
reducing observation complexity. However, the average $\ell_{\infty}$ norm of
error doesn’t change significantly.

|
---|---
|
|

## References

  * Balakrishnan and Singh (2012) Kolar M. Rinaldo A. Balakrishnan, S. and A. Singh.  Recovering block-structured activations using compressive measurements.  _arXiv:1209.3431_ , 2012.
  * Balcan and Zhang (2016) M.F Balcan and H. Zhang.  Noise-tolerant life-long matrix completion via adaptive sampling.  _Advances in Neural Information Processing Systems_ , 2016.
  * Cand‘es and Plan (2010) E. J. Cand‘es and Y. Plan.  Matrix completion with noise.  _Proceedings of the IEEE._ , 2010.
  * Candes and Recht (2009) E. J. Candes and B. Recht.  Exact matrix completion via convex optimization.  _Foundations of Computational Mathematics_ , 2009.
  * Candés and Tao (2010) E. J. Candés and T. Tao.  The power of convex relaxation: Near-optimal matrix completion.  _IEEE Transactions on Information Theory_ , 2010.
  * Chen et al. (2014) Y. Chen, S. Bhojanapalli, S. Sanghavi, and R. Ward.  Coherent matrix completion.  In _In Proceedings of The 31st International Conference on Machine Learning_ , 2014.
  * Coleman and Pothen (1986) T. F. Coleman and A. Pothen.  The null space problem i. complexity.  _SIAM Journal on Algebraic Discrete Methods_ , 1986.
  * Gross (2011) D. Gross.  Recovering low-rank matrices from few coefficients in any basis.  _Information Theory, IEEE Transactions on._ , 2011.
  * Haupt et al. (2011) J. Haupt, R. Castro, and R. Nowak.  Adaptive sampling for sparse detection and estimation.  _IEEE Transactions on Information Theory_ , 2011.
  * H.Zhang (2015) C. a. E. H.Zhang, Z.Lin.  Exact recoverability of robust pca via outlier pursuit with tight recovery bounds.  _In AAAI Conference on Artificial Intelligence._ , 2015.
  * Keshavan and Oh (2010) AndreaMontanari Keshavan, R. H. and S. Oh.  Matrix completion from noisy entries.  _The Journal of Machine Learning Research._ , 2010.
  * Koltchinskii et al. (2011) V. Koltchinskii, K. Lounici, and A. B. Tsybakov.  Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion.  _The Annals of Statistics_ , 2011.
  * Krishnamurthy and Singh (2013) A. Krishnamurthy and A. Singh.  Low-rank matrix and tensor completion via adaptive sampling.  In _Advances in Neural Information Processing Systems_ , 2013.
  * Krishnamurthy and Singh (2014) A. Krishnamurthy and A. Singh.  On the power of adaptivity in matrix completion and approximation.  _arXiv preprint_ , 2014.
  * Mai and Alquier (2015) T. T. Mai and P. Alquier.  A bayesian approach for noisy matrix completion: Optimal rate under general sampling distribution.  _Electronic Journal of Statistics_ , 2015.
  * Malloy and Nowak (2011) M. Malloy and R. Nowak.  Sequential analysis in high-dimensional multiple testing and sparse recovery.  _IEEE International Symposium on Information Theory._ , 2011.
  * McCormick (1983) S. T. McCormick.  A combinatorial approach to some sparse matrix problems.  _DTIC Document_ , 1983.
  * Negahban and Wainwright (2012) S. Negahban and M. J. Wainwright.  Restricted strong convexity and weighted matrix completion: Optimal bounds with noise.  _The Journal of Machine Learning Research._ , 2012.
  * Qing Qu and Wright (2015) Ju Sun Qing Qu and John Wright.  Finding a sparse vector in a subspace: linear sparsity using alternating directions.  _IEEE TransactionRANSACTION onON information theoryINFORMATION THEORY_ , 2015.
  * Recht (2011) B. Recht.  A simpler approach to matrix completion.  _The Journal of Machine Learning Research_ , 2011.
  * T‘anczos and Castro (2013) E. T‘anczos and R. Castro.  Adaptive sensing for estimation of structured sparse signals.  _arXiv:1311.7118_ , 2013.
  * Warmuth and Kuzmin (2008) M. K. Warmuth and D. Kuzmin.  Randomized online pca algorithms with regret bounds that are logarithmic in the dimension.  _Journal of Machine Learning Research_ , 2008.

A Simple Theory for Adaptive Matrix Completion

##  Appendix A Proof of the Lemma 3.1, Exact Recovery with Sparsity Number

We start with rephrasing the lemma 1 and provide further discussions regarding
space sparsity. Later, we are using the idea of the lemma and design an
algorithm that has similar flavor to $\mathbf{KS2013}$ with the difference
that this method recovers the underlying matrix deterministically.

###  A.1 Proof of lemma 3.1

######  Lemma.

Let $\mathbb{U}$ be a subspace of $\mathbb{R}^{m}$ and $x^{1},x^{2},...,x^{n}$
be any set of vectors from $\mathbb{U}$. Then the linear dependence of
$x^{1}_{\Omega},x^{2}_{\Omega},...,x^{n}_{\Omega}$ implies linear dependence
of $x^{1},x^{2},...,x^{n}$ for any $\Omega\subset[m]$ such that
$|\Omega|>\overline{\psi}(\mathbb{U})$.

######  Proof A.1.

By the hypothesis of linear dependence, there are coefficients
$\alpha_{1},...,\alpha_{n}$, not all zero, such that

$\displaystyle\alpha_{1}x^{1}_{\Omega}+...+\alpha_{n}x^{n}_{\Omega}=0.$

To show linear dependence of $x^{1},\ldots,x^{n}$ we prove the following
equation also satisfies

$\displaystyle\alpha_{1}{x^{1}}+...+\alpha_{n}{x^{n}}=0$

Assume by contradiction $y=\sum_{i=1}^{k}\alpha_{i}{x_{i}}$ is a nonzero
vector. But, we have

$\displaystyle y_{\Omega}=\sum_{i=1}^{k}\alpha_{i}{x_{i}}_{\Omega}=0$

which implies $\overline{\psi}(\mathbb{U})\geq|\Omega|$ from the definition of
space sparsity number. However, $|\Omega|>\overline{\psi}(\mathbb{U})$ from
the hypothesis of the lemma which concludes a contradiction. Therefore, the
assumption the vector $y$ being nonzero vector cannot be true, then the
following satisfies :

$\displaystyle y=\sum_{i=1}^{k}\alpha_{i}{x_{i}}=0$

In the following lemma we prove somewhat reverse statement of the lemma 1.

######  Lemma A.2.

Let $\mathbb{U}$ be a subspace of $\mathbb{R}^{m}$ and $x^{1},x^{2},...,x^{n}$
be any set of vectors from $\mathbb{U}$. Then the linear dependence of
${x^{1}},{x^{2}},...,{x^{n}}$ implies linear dependence of
$x^{1}_{\Omega},x^{2}_{\Omega},...,x^{n}_{\Omega}$, for any
$\Omega\subset[m]$.

######  Proof A.3.

The proof of the statement is straightforward observation of the fact that

$\alpha_{1}{x^{1}}+...+\alpha_{n}{x^{n}}=0$

implies

$\alpha_{1}x^{1}_{\Omega}+...+\alpha_{n}x^{n}_{\Omega}=0_{\Omega}=0$

Tightness of lemma 1: We show example for tightness of the lemma with the
following matrix:

$\mathbf{M}=\begin{bmatrix}1&2&5\\\ 1&2&4\\\ 1&0&4\\\ 1&0&4\end{bmatrix}$

First observation here is columns of $\mathbf{M}$ is linearly independent.
Then, the next observation is that $e_{1}=(1,0,0,0)$ is contained in the
column space. Therefore, the space sparsity number of the column space of
$\mathbf{M}$ is at least equal to $3$. Using the fact that space sparsity
number is less then 4 we conclude that column space sparsity number is exactly
equal to $3$. Lets check the submatirx $\textbf{M}_{\Omega:}$ where
$\Omega=\\{2,3,4\\}$:

$\mathbf{M_{\Omega:}}=\begin{bmatrix}1&2&4\\\ 1&0&4\\\ 1&0&4\end{bmatrix}$

Columns of $\mathbf{M_{\Omega:}}$ is linearly dependent (first and third
column), however columns of $\mathbf{M}$ is not. Then, it follows that there
is an example that when $\|\Omega\|=\overline{\psi}(\mathbb{U})$ but the
hypothesis of the lemma 1 not satisfied. Therefore, the statement of the lemma
1 is tight.

######  Lemma A.4.

For the column space $\mathbb{U}$ of $m\times n$ sized matrix $\mathbf{M}$
with rank-$r$, the following inequality is satisfied

$r-1\leq\overline{\psi}(\mathbb{U})\leq m-1.$

######  Proof A.5.

$\overline{\psi}(\mathbb{U})<m$ is straightforward because any nonzero vector
in $\mathbb{R}^{m}$ has at most $m-1$ coordinates equal to zero. Then, it
follows from the definition of the space sparsity number,
$\overline{\psi}(\mathbb{U})\leq m-1$.
In the rest of the proof we prove $r-1\leq\overline{\psi}(\mathbf{M})$.
$\mathbf{M}$ having rank $r$ implies that we can choose $r$ rows from it that
are the basis for the row space of it. Technically, we may find $R\subset[m]$
such that $|R|=r$ and $\mathbf{M}_{R:}$ is rank $r$. Similarly, we can find
$C\subset[n]$ such that $|C|=r$ and $\mathbf{M}_{R:C}$ is an $r\times r$-sized
matrix of rank $r$. It follows that there exists $\alpha\in\mathbb{R}^{r}$
such that

$\mathbf{M}_{R:C}\alpha=e_{1}=\big{(}1,0,\ldots,0\big{)}.$

Consequently, $\mathbf{M}_{:C}\alpha\neq 0$ but has zero components in $r-1$
of the indices given by $R$. Thus $\overline{\psi}(\mathbf{M}_{:C})\geq r-1$.
Finally:

$r-1\leq\overline{\psi}(\mathbf{M}_{:C})\leq\overline{\psi}(\mathbb{U})$

##### Discussion for lemma A.4:

It is easy to construct examples to show both sides of the inequality is tight
(i.e. equality satisfied). For any matrix that
$e_{1}=\big{(}1,0,0,\ldots,0\big{)}$ is contained in the column space,
$\overline{\psi}(\mathbb{U})=m-1$ is trivially correct.
Moreover, column space of the general rank-$r$ matrices creasted as
$\mathbf{M}=\mathbf{X}\mathbf{Y}$ where $\mathbf{X}\in\mathbb{R}^{m\times r}$
and $\mathbf{X}_{i,j}\sim\mathcal{N}(0,1)$, $\mathbf{Y}\in\mathbb{R}^{r\times
n}$ and $\mathbf{Y}_{i,j}\sim\mathcal{N}(0,1)$ left side of the inequality is
tight (i.e. $r-1=\overline{\psi}(\mathbb{U})$).

###  A.2 Exact Recovery with Sparsity Number

The algorithm below-$\mathbf{ERCS}$ is just modification of the algorithm
KS2013 in the input phase. We show observing just
$d=\overline{\psi}(\mathbb{U})+1$ many entries in each column is enough te
decide whether partially observed column is contained in the subspace or not.
Under the condition that the column space $\mathbb{U}$ of the underlying
matrix satisfies $r-1=\overline{\psi}(\mathbb{U})$, the observation complexity
of the algorithm $\mathbf{ERCS}$ becomes $m\times r+(n-r)\times r=(m+n-r)r$
which is the degree of freedom of the set of $m\times n$ sized rank-$r$
matrices. Therefore, under this condition $\mathbf{ERCS}$ is absolutely
optimal

ERCS: Exact recovery with column sparsity

Input: $d=\overline{\psi}(\mathbb{U})+1$

Initialize: $k=0,\widehat{\mathbf{U}}^{0}=\emptyset$

1: Draw uniformly random entries $\Omega\subset[m]$ of size $d$

2: Observe entire $\mathbf{M}_{\Omega:}$

3: for $i$ from $1$ to $n$ do

4: if
$\|\mathbf{M}_{\Omega:i}-\mathcal{P_{U}}_{\Omega}\mathbf{M}_{\Omega:i}\|>0$

5: Fully observe $\mathbf{M}_{:i}$

6:
$\widehat{\mathbf{U}}^{k+1}\leftarrow\widehat{\mathbf{U}}^{k}\cup\mathbf{M_{:i}}$

7: Orthogonalize $\widehat{\mathbf{U}}^{k+1}$

8: $k=k+1$

9: otherwise:
$\widehat{\mathbf{M}}_{:i}=\widehat{\mathbf{U}}^{k}\widehat{\mathbf{U}}^{k^{+}}_{\Omega:}\widehat{\mathbf{M}}_{\Omega:i}$

Output: Underlying matrix $\widehat{\mathbf{M}}$

######  Theorem A.6.

Let $\mathbb{U}$ represent the column space of the $m\times n$ sized matrix
$\mathbf{M}$ of rank $r$. Then, ERCS exactly recovers $\mathbf{M}$ by

$m\times r+(n-r)(\overline{\psi}(\mathbb{U})+1)$

observations.

######  Proof A.7.

We start by showing $\mathbf{ERCS}$ recovers $\mathbf{M}$ exactly and later we
focus on observation count. To prove correctness of exact recovery we use
mathematical induction as follow:
$Hypothesis$ : after $i$-th iteration $\mathbf{ERCS}$ already correctly
recovered first $i$ columns.
$Base$ $case$ : $i=1$ is trivial as if at least one of the observed entries is
nonzero we completely observe the column, which guarantees correctness. On the
other hand, if it happens all of $\overline{\psi}(\mathbb{U})+1$ entries are
zero, then the first column is indeed completely zero because the definition
of the space sparsity number implies there can be at most $\psi(\mathbb{U})$
many zero coordinates in a nonzero vector in the column space.
$Hypothesis$ $proof$ : Let assume after step $i-1$, $\mathbf{ERCS}$ recovered
first $i-1$ columns correctly and we want to show the algorithm exactly
recovers $i$-th column too.
From the design of the algorithm $\mathbf{M}_{\Omega:{i}}$ is already
observed. Then, if in the line 4, $\mathbf{ERCS}$ decides the column is
linearly independent with previous columns, as in the next line we completely
observe the column there is no chance that the algorithm can do mistake under
this case. Therefore, the only remaining case is, if in the line 4 the
algorithm decides the column $i$ is linearly dependent.
From the statement of lemma 1, if a set of vectors from a subspace
$\mathbb{U}$ are linearly dependent on a given subset of coordinates, then
they are indeed linearly dependent. We conclude that the algorithm’s decision
is correct and by just back projection method, the algorithm recovers
remaining entries of the partially observed column. Therefore, column $i$ also
recovered correctly and we are done with the proof of induction hypothesis.
Our next goal is to show the observation complexity is $m\times
r+(n-r)(\overline{\psi}(\mathbb{U})+1)$. From the lemma 1, we conclude that
whenever current column is indeed linearly independent with previous columns,
the $\mathbf{ERCS}$ also decides it is linearly independent. Moreover, from
the lemma 10, we conclude that if the current column is linearly dependent
with previous columns, then in this case $\mathbf{ERCS}$ decides it is
linearly dependent. As there are $r$ many linearly independent columns in the
underlying matrix $\mathbf{M}$, the algorithm decides independence exactly $r$
times and in each of them it does complete observations. However, in remaining
$n-r$ columns, number of observations is exactly
$\overline{\psi}(\mathbb{U})+1$. As a conclusion, number of total observations
is: $rm+(n-r)(\overline{\psi}(\mathbb{U})+1)$

######  Corollary A.8.

$\mathbf{ERCS}$ still performs correctly under the case in each column, number
of observed entries is lower bounded by $\overline{\psi}(\mathbb{U})$ :
$d\geq\overline{\psi}(\mathbb{U})+1$. Moreover, the number of observations
will be $m\times r+(n-r)d$

######  Proof A.9.

The proof is exactly proceeds as proof of the theorem. The key point is to
notice, lemma 1 and lemma 10 are still satisfying.

##### Optimality of $\mathbf{ERCS}$:

We notice that both of algorithms KS2013 and ERCS has two stages of
observation.

  * $i:$

Select subset of rows and observe them completely.

  * $ii:$

Detect linearly independent columns and observe them completely.

The discussion for tightness of the lemma 1 above implies that $\mathbf{ERCS}$
is optimal deterministic two stage observation, low-rank exact recovery
algorithm. Moreover, in the corollary above we discussed for any
$d\geq\overline{\psi}(\mathbb{U})$ the $\mathbf{ERCS}$ algorithm would still
perform correctly. Therefore, having constant factor approximation of the
space sparsity number of the column space would lead asymptotically optimal
algorithm:

$\displaystyle\widehat{d}\leq Kd$ $\displaystyle\implies\widehat{d}+1\leq
K(d+1)$ $\displaystyle\implies(n-r)(\widehat{d}+1)\leq(n-r)K(d+1)$

adding $mr$ to both side leads to

$\displaystyle rm+(n-r)(\widehat{d}+1)$ $\displaystyle\leq rm+(n-r)K(d+1)$
$\displaystyle\leq Krm+K(n-r)(d+1)$
$\displaystyle=K\big{(}rm+(n-r)(d+1)\big{)}$

Notice that $rm+(n-r)(\widehat{d}+1)$ is the observation complexity we have
and $\big{(}rm+(n-r)(d+1)\big{)}$ is optimal two stage as we discussed here.
All together, the inequality above implies constanct approximation to space
sparsity number gives as constant approximation to optimal solution.

##  Appendix B Exact Recovery with Heterogeneous Cost

Here, we discuss matrix completion problem with relatively different setting.
Previously, we focused on the case, where each of the entry of underlying
matrix $\mathbf{M}$ has the same observation cost. In this section we discuss
the completion problem where entries of the matrix has non uniform cost to
observe. We tackle with two type of non uniformity here:

  * •

Entries has uniform cost across the same column, but different columns has
different costs.

  * •

Each entry of the matrix has different cost.

###  B.1 Uniform Cost Across Columns

Problem: For any fixed $j$, the cost of observing $\mathbf{M}_{i:j}$ is equal
to $\chi_{j}$ for any $1\leq i\leq m$, and $\chi_{1},\chi_{2},\ldots,\chi_{n}$
are arbitrary positive numbers and we target to recover the matrix
$\mathbf{M}$ as cheap as possible.
Solution: We propose a slight modification of the $\mathbf{ERCS}$ to solve
optimally among the two staged methods as we discussed before. Lets remind
that in the algorithm we show that selecting any
$d=\overline{\psi}(\mathbb{U})+1$ many rows is enough to guarantee exact
recovery deterministically. In the next stage, we iteratively go through
columns one by one starting with the first column, and if we detect a column
is linearly independent with previous ones, we completely observe it. If not,
we recover it using the pre-determined subspace.
To adapt the solution for this problem, we just need to change the order of
the columns we start to check. Basically, instead of starting with the first
column, we should start with the cheapest one. If we decide its not contained
in the current subspace, we completely observe all entries and if it is
contained then we just recover with the current subspace. Then, we move to
second cheapest column and so on so forth with the increasing order of cost.
Correctness: We can see that the proof of the correctness of $\mathbf{ERCS}$
is independent of the order of the columns. Therefore, selecting columns with
increasing order of the cost would not change the correctness of the
algorithm.
Optimality: The set of two stage algorithm can be parametrized by two numbers.
First one is - $d$\- the number of rows fully observed and the second is the
subset of indices of columns to observe fully. We analyse the optimal
algorithm for three cases of values of $d$:

1\. $d\leq\overline{\psi}(\mathbb{U})$. It is obvious that optimal algorithm
cannot have $d\leq\overline{\psi}(\mathbb{U})$, because from the discussion
for tightness of the lemma 3.1 and optimality of $\mathbf{ERCS}$, there are
matrices that selection of $d=\overline{\psi}(\mathbb{U})$ rows is not enough
to guarantee the existence of $r$ linearly independent rows.
2\. $d=\overline{\psi}(\mathbb{U})+1$ It is a well known fact that the set of
column basises are matroids and Greedy algorithms gives the optimal solution
for matroids matroid. Note that the algorithm designed above is efficient way
of giving greedy solution.
3\. $d>\overline{\psi}(\mathbb{U})+1$. Lets assume that the optimal algorithm
takes $\tilde{d}>d$ rows in the first phases and columns:
$i_{1},i_{2},\ldots,i_{\tilde{r}}$. We first note that, $\tilde{r}=r$, it is
because if $\tilde{r}<r$ then selected columns are not enough to learn the
column space and if $\tilde{r}>r$ we can pick subset of these columns that is
basis for column space and selecting this basis has less cost which
contradicts to optimality. Therefore, $\tilde{r}=r$ for optimal case.
Moreover, we can use the same subset selection argument to pick
$\overline{\psi}(\mathbb{U})+1$ sized subset of rows then select the same set
of columns and it will be cheaper. Therefore, for optimality we should select
exactly $d=\overline{\psi}(\mathbb{U})+1$ rows.

###  B.2 Exact recovery with full heterogeneity

Problem: For any $i,j$, the cost of observing $\mathbf{M}_{i:j}$ is equal to
$\chi_{ij}$ and $\chi_{11},\chi_{12},\ldots,\chi_{mn}$ are arbitrary positive
numbers and similar to the previous problem we target to recover the matrix
$\mathbf{M}$ as cheap as possible.
Solution: We describe the solution in the following algorithm:

ERHC:  Exact recovery with heterogeneous cost

Input: $d=\overline{\psi}(\mathbb{U})+1$ here $\mathbb{U}$ is the column space
of the underlying matrix
Initialize: $\widehat{\mathbf{M}}$ set to $m\times n$ sized null matrix,
$\widehat{\mathbf{U}}^{0}=\emptyset$, $k=0$

1: for $i$ from $1$ to $m$, do

2: $\chi^{i}=\sum_{j=1}^{n}\chi_{ij}$

3: Sort $\chi^{i}$s with increasing order and select first $d$ and denote
their index set by$-R$

4: Observe entire $\mathbf{M}_{R:}$

5: for $i$ from $1$ to $m$, do

6: $\overline{\chi}^{i}=\sum_{j\in[n]\setminus R}\chi_{ij}$

7: Sort $\overline{\chi}^{i}$s with increasing order and lets denote
$\\{i_{1},i_{2},\ldots,i_{n}\\}$ as
$\overline{\chi}^{i_{1}}\leq\overline{\chi}^{i_{2}}\leq\ldots\leq\overline{\chi}^{i_{n}}$

8: for $h$ from $1$ to $m$, do

9: If
$\|\mathbf{M}_{R:i_{h}}-\mathcal{P}_{\widehat{\mathbf{U}}^{k}_{R}}\mathbf{M}_{R:i_{h}}\|^{2}>0$

10: Fully observe $\mathbf{M}_{:i_{h}}$ add it to the basis
$\widehat{\mathbf{U}}^{k}$

11: Orthogonalize $\widehat{\mathbf{U}}^{k}$

12: $k=k+1$

13: Otherwise:
$\widehat{\mathbf{M}}_{:i_{h}}=\widehat{\mathbf{U}}^{k}\widehat{\mathbf{U}}^{k^{+}}_{R:}\widehat{\mathbf{M}}_{R:i_{h}}$

14: return $\widehat{\mathbf{M}}$

Output: Underlying matrix $\widehat{\mathbf{M}}$

##### Correctness:

We can see the correctness of $\mathbf{ERHC}$ is due to the correctness of
$\mathbf{ERCS}$ as selecting cheapest $\overline{\psi}(\mathbb{U})+1$ is
special case of selecting any $\overline{\psi}(\mathbb{U})+1$ many columns and
iteration order over the columns doesn’t matter similarly for this case too.

##### Optimality:

Unlike to the previous case, greedy algorithm doesn’t give us the cheapest
combination of columns and rows. Following example provides a matrix and entry
costs that shows that greedy algorithm is not optimal.

$\mathbf{M}=\begin{bmatrix}1&1&2&3\\\ 1&2&3&4\\\ 1&3&4&5\\\
1&4&5&6\end{bmatrix}\hskip 28.45274pt\mathbf{\chi}=\begin{bmatrix}1&1&4&1\\\
1&5&3&4\\\ 4&3&4&4\\\ 1&4&4&8\end{bmatrix}$

The greedy algorithm for this case observes rows $R=\\{1,2\\}$ and columns
$C=\\{1,2\\}$ which has overall cost of:

$\displaystyle(1+1+4+1)+(1+5$ $\displaystyle+3+4)+(4+1)+(3+4)=32$

However, observing ${R}=\\{1,3\\}$ and columns ${C}=\\{1,3\\}$ would give us
overall cost of:

$\displaystyle(1+1+4+1)+(4+3+4+4)+(1+1)+(3+4)=31$

which is cheaper than greedy algorithm.

However, with the same cost matrix, there are other matrices that shares the
same column space as $\mathbf{M}$ (therefore the same column space sparsity
number) but greedy algorithm is still optimal. For the same cost matrix with a
slightly modified underlying matrix, we can give an example:

$\overline{\mathbf{M}}=\begin{bmatrix}1&1&2&2\\\ 1&2&2&3\\\ 1&3&2&4\\\
1&4&2&5\end{bmatrix}\hskip 28.45274pt\mathbf{\chi}=\begin{bmatrix}1&1&4&1\\\
1&5&3&4\\\ 4&3&4&4\\\ 1&4&4&8\end{bmatrix}$

This gives us the conclusion, with just information of the observation cost
matrix and column space sparsity number, we cannot pick theoretical optimal
set of rows and columns that is guaranteed carrying all of information of the
underlying matrix.

##### 2-Optimality:

Even though greedy algorithm cannot return the optimal set of rows and
columns, here we show that the overall cost of the cost oof the algorithm is
at most twice expensive than optimal.
We denote the row set and column set parameter of optimal 2-stage algorithm
$\tilde{R}$ and $\tilde{C}$ and cost of it by $\sigma_{OPT}$. Then, we can
decompose optimal soluton into its parts as following:

$\sigma_{OPT}=\chi(\mathbf{M}_{\tilde{R}:})+\chi(\mathbf{M}_{:\tilde{C}})-\chi(\mathbf{M}_{\tilde{R}:\tilde{C}})$

. Trivially, both of the following inequalities satisfied

$\chi(\mathbf{M}_{\tilde{R}:\tilde{C}})\leq\chi(\mathbf{M}_{:\tilde{C}})$
$\chi(\mathbf{M}_{\tilde{R}:\tilde{C}})\leq\chi(\mathbf{M}_{\tilde{R}:})$

which these inequalities implies that

$\sigma_{OPT}\geq\mathrm{max}(\chi(\mathbf{M}_{:\tilde{C}}),\chi(\mathbf{M}_{\tilde{R}:})).$

Now lets decompose cost of greedy algorithm to its pieces:

$\sigma_{G}=\chi(\mathbf{M}_{R:})+\chi(\mathbf{M}_{:C})-\chi(\mathbf{M}_{R:C})$

Note that the greedy algorithm doesn’t necessarily selects cheapest basis
columns, however selected columns minimizes the overall cost after rows
selected. Therefore, we conclude that if we denote the set of cheapest columns
by $C^{B}$, then the following inequality satisfied:

$\displaystyle\sigma_{G}=\chi(\mathbf{M}_{R:})+\chi(\mathbf{M}_{:C})-\chi(\mathbf{M}_{R:C})$
$\displaystyle\leq\chi(\mathbf{M}_{R:})+\chi(\mathbf{M}_{:C^{B}})-\chi(\mathbf{M}_{R:C^{C}})$
$\displaystyle\leq 2\hskip
2.84526pt\mathrm{max}\big{(}\chi(\mathbf{M}_{R:}),\chi(\mathbf{M}_{:C^{B}})\big{)}$

As we discussed before in order to have guarantee that we will be able to have
full information to detect linearly independent columns we need to observe at
least $\psi(\mathbb{U})+1$ many rows.
Moreover, as greedy algorithm observe exactly
$\overline{\psi}({\mathbb{U}})+1$ many rows by choosing cheapest columns we
are guaranteed to have:

$\chi(\mathbf{M}_{R:})\leq\chi(\mathbf{M}_{\tilde{R}:})$

Similarly as $C^{B}$ represents the set of cheapest columns, we have:

$\chi(\mathbf{M}_{:C^{B}})\leq\chi(\mathbf{M}_{:\tilde{C}})$

which together implies

$\mathrm{max}\big{(}\chi(\mathbf{M}_{R:}),\chi(\mathbf{M}_{:C^{B}})\big{)}\leq\mathrm{max}\big{(}\chi(\mathbf{M}_{\tilde{R}:}),\chi(\mathbf{M}_{:\tilde{C}})\big{)}.$

Putting all inequalities together we conclude:

$\displaystyle\sigma_{G}\leq 2\hskip
2.84526pt\mathrm{max}\big{(}\chi(\mathbf{M}_{R:}),\chi(\mathbf{M}_{:C^{B}})\big{)}\leq
2\hskip
2.84526pt\mathrm{max}\big{(}\chi(\mathbf{M}_{\tilde{R}:}),\chi(\mathbf{M}_{:\tilde{C}})\big{)}\leq
2\sigma_{OPT}$

Therefore, we conclude that greedy algorithm gives us 2-optimal algorithm.

##### Tightness:

In the following example, we see that greedy algorithm cannot guarantee better
than 2-optimality:

$\mathbf{\chi}=\begin{bmatrix}\frac{\epsilon}{100}&\frac{\epsilon}{100}&\frac{\epsilon}{100}&\frac{\epsilon}{100}&10-\epsilon&10-\epsilon\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
\frac{\epsilon}{100}&\frac{\epsilon}{100}&\frac{\epsilon}{100}&\frac{\epsilon}{100}&10-\epsilon&10-\epsilon\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
10&10&\frac{\epsilon}{100}&\frac{\epsilon}{100}&\frac{\epsilon}{100}&\frac{\epsilon}{100}\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
10&10&\frac{\epsilon}{100}&\frac{\epsilon}{100}&\frac{\epsilon}{100}&\frac{\epsilon}{100}\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
\frac{\epsilon}{100}&\frac{\epsilon}{100}&10&10&10-\epsilon&10-\epsilon\vskip
6.0pt plus 2.0pt minus 2.0pt\\\
\frac{\epsilon}{100}&\frac{\epsilon}{100}&10&10&10-\epsilon&10-\epsilon\vskip
6.0pt plus 2.0pt minus 2.0pt\\\ \end{bmatrix}$

It is clear that optimal choice is ${C}=\\{1,2\\}$ and ${R}=\\{3,4\\}$ which
gives the cost of :

$\sigma_{OPT}=10+10+10+10+16\times\frac{\epsilon}{100}=40+\frac{\epsilon}{6.25}$

However, greedy algortihm will pick ${R}=\\{1,2\\}$ in the first stage which
has overall cost of

$(10-\epsilon)+(10-\epsilon)+(10-\epsilon)+(10-\epsilon)+8\times\frac{\epsilon}{100}=40-4\epsilon+\frac{\epsilon}{12.5}$

Then in the next stage it choose columns ${C}=\\{5,6\\}$ which also has cost
of

$(10-\epsilon)+(10-\epsilon)+(10-\epsilon)+(10-\epsilon)+4\times\frac{\epsilon}{100}=40-4\epsilon+\frac{\epsilon}{25}$

which all together cumulative cost is

$(40-4\epsilon)+\frac{\epsilon}{12.5}+(40-4\epsilon)+\frac{\epsilon}{25}=80-8\epsilon+\frac{3}{25}\epsilon.$

To find the fraction of this cost to optimal cost we get

$\frac{\sigma_{G}}{\sigma_{OPT}}=\frac{80-8\epsilon+\frac{2\epsilon}{25}}{40+\frac{\epsilon}{6.25}}\approx
2-\frac{\epsilon}{5}.$

Therefore for any number smaller than $2$, we can choose an $\epsilon$ which
ratio of the cost of greedy algorithm to optimal set is larger than that
number. This implies that, 2-optimality of the algorithm $\mathbf{ERHC}$ is
tight.

##  Appendix C Proof of Theorem 3.2. Exact Recovery for Low Rank Matrices.

We start with rephrasing the theorem 2 and then divide the theorem into two
parts and prove them separately.

######  Theorem.

(Exact Recovery for Low-Rank Matrices) Let $r$ be the rank of underlying
$m\times n$ sized matrix $\mathbf{M}$ with column space $\mathbb{U}$ and row
space $\mathbb{V}$. Then, $\mathbf{ERR}$ exactly recovers the underlying
matrix $\mathbf{M}$ with probability at least $1-\epsilon$ using at most

$(m+n-r)r+\mathrm{min}\Big{(}2\frac{mn}{{\psi}(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n\Big{)}$

observations.

We split the statement of the theorem above into two and prove each of them
separately. First, we show that observation complexity is upper bounded by
$(m+n-r)r+2\frac{mn}{{\psi}(\mathbb{U})}\log{(\frac{r}{\epsilon})}$. Then, in
another theorem we show that the observation complexity is bounded by

$(m+n-r)r+\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}$

and the statement of theorem follows from these two results.

###  C.1 Matrices with Incoherent Row Space

######  Theorem ( Highly coherent row space).

Let $r$ be the rank of underlying $m\times n$ sized matrix $\mathbf{M}$ with
column space $\mathbb{U}$. Then, $\mathbf{ERR}$ exactly recovers the
underlying matrix $\mathbf{M}$ with probability at least $1-\epsilon$ using at
most

$(m+n-r)r+2\frac{mn}{{\psi}(\mathbb{U})}\log{(\frac{r}{\epsilon})}$

observations.

######  Proof C.1.

The proof is consisting following steps:

  * •

step 1. Give terminology will be used throughout the proof. Identifying type
of observations to two classes : informative and non-informative.

  * •

step 2. Provide a bound to number of informative observations.

  * •

step 3. In remaining steps, we try to give bound to non-informative
observations. We start by giving upper bound to the unsuccessful observations
in line 5.

  * •

step 4. We model the execution of $\mathbf{ERR}$ with a stochastic process and
design another process which terminates faster than this.

  * •

step 5. We relate the problem to basic combinatorial counting problem and
analyse

  * •

step 6. Conclude that total number of observations is

$\displaystyle(m+n-r)r+2\frac{mn}{{\psi}(\mathbb{U})}\log{(\frac{r}{\epsilon})}.$

Step 1: For ease of readability we denote $\psi(\mathbb{U})$ by $k$ during the
proof. Lets start a process in the beginning of the algorithm for each column.
We call process of the column $\mathbf{M}_{:j}$ dies in one of the following
cases happens:

  * a.

$\mathbf{M}_{:j}$ is fully observed in line 6 in some intermediate step of
$\mathbf{ERR}$

  * b.

$\mathbf{M}_{:j}$ is contained in the column space of the already fully
observed columns in underlying matrix $\mathbf{M}$ (i.e. columns in $C$).

  * c.

Algorithm already learns entire column space : $\widehat{r}=r$

If a column/process is not dead then we call it is active. We call an
observation is informative if it is observed at line 6 (i.e. it contributes to
the studied column/row space learned by $\mathbf{ERR}$ and uninformative if it
observed at line 3. Obviously some entries are observed both at line 3 and 6,
so they count in both non-informative and informative observations.

Step 2: We can simply observe that the number of informative observations is
exactly $mr+nr-r^{2}$. Because, at the end of the algorithm set of informative
observations is just set of $r$ many linearly independent columns (we have
$mr$ observations here) and $r$ many linearly independent rows (we have $nr$
observations here). By observing that entries in $r\times r$ sub-matrix is
counted twice, we conclude that overall observations is just

$\displaystyle mr+nr-r^{2}$

Step 3: In order to give upper bound to the number of non-informative
observations, we see it is enough to bound the number of phases the algorithm
$\mathbf{ERR}$ passes through. Specifically, if the number of phases is
bounded by $T$ then overall number of non-informative observations is bounded
by $Tn_{2}$. In order to give upper bound to $T$, we first explore the
probability of an detecting independence of an observation in line 3 for an
active column:

######  Lemma C.2.

The probability of detecting independence of an active column in the $j$’th
phase of the algorithm $\mathbf{ERR}$ is lower bounded by $\frac{k}{m-j}$

######  Proof C.3.

In an intermediate step of $\mathbf{ERR}$ we have $|C|=|R|=\widehat{r}$ and
$M_{R:C}$ is $\widehat{r}\times\widehat{r}$ matrix of rank $\widehat{r}$.
Then, for any $i\in[n]$, $\mathbf{M}_{R:i}$ is in the column space of
$\mathbf{M}_{R:C}$ as the matrix is full rank and therefore its column space
is entire $\mathbb{R}^{\widehat{r}}$. Then there exists unique coefficients
$\alpha_{1},\alpha_{2},...,\alpha_{\widehat{r}}$ for columns
$C=\\{c_{1},...,c_{\widehat{r}}\\}$ that following equality satisfied.

$\displaystyle\alpha_{1}\mathbf{M}_{R:c_{1}}+\ldots+\alpha_{\widehat{r}}\mathbf{M}_{R:c_{\widehat{r}}}=\mathbf{M}_{R:i}\hskip
14.22636pt\implies\hskip
14.22636pt\alpha_{1}\mathbf{M}_{R:c_{1}}+\ldots+\alpha_{\widehat{r}}\mathbf{M}_{R:c_{\widehat{r}}}-\mathbf{M}_{R:i}=0$

Now, let observe the vector

$\displaystyle
y=\alpha_{1}\mathbf{M}_{:c_{1}}+\alpha_{2}\mathbf{M}_{:c_{2}}+...+\alpha_{\widehat{r}}\mathbf{M}_{:c_{\widehat{r}}}-\mathbf{M}_{:i}$

We know that $y\neq 0$ because we know column $i$ is linearly independent with
previous observed columns -
$\mathbf{M}_{:c_{1}},\mathbf{M}_{:c_{2}},...,\mathbf{M}_{:c_{\widehat{r}}}$.
Moreover for any row index $a\in R$, $y_{a}=0$ because $y_{R}=0$ from the
definition of $\alpha_{j}$’s. As $y$ is in the column space of $M$ it has at
most $m-k$-many zero coordinates. Moreover, for any $a\notin R$ but
$\mathbf{M}_{i_{a}:i}$ observed in line 6 $y_{i_{a}}=0$ should satisfy,
because otherwise in one of previous iterations we would already decide
$\mathbf{M}_{:i}$ is linearly independent and we would add index $i$ to $C$,
but here we know $i\notin C$.
Basically we conclude that all known coordinates of $y$ is 0 and number of
known coordinates is represented by $observed$. We know at least $k$ many
coordinates of $y$ is nonzero and we already have $m-observed$ many
coordinates of $y$ is zero, then with probability at least:
$\frac{k}{m-observed}$ uniformly selected next observation will be zero. Being
nonzero of $y_{a}$ implies non-singularity of the matrix
$\mathbf{\widehat{M}}_{\widehat{R}:\widehat{C}}$ where
$\widehat{R}=R\cup\\{a\\}$ and $\widehat{C}=C\cup\\{i\\}$. It is because if
this matrix was not invertible then there would be coefficients
$\beta_{1},...,\beta_{r^{\prime}+1}$ (not all of them are zero) such that

$\displaystyle\beta_{1}\mathbf{M}_{\widehat{R}:c_{1}}+...+\beta_{\widehat{r}}\mathbf{M}_{\widehat{R}:c_{\widehat{r}}}+\beta_{\widehat{r}+1}\mathbf{M}_{\widehat{R}:i}=0.$

From lemma 2, linear independence of
$\mathbf{M}_{R:c_{1}},\mathbf{M}_{R:c_{\widehat{r}}}$ implies linear
independence of
$\mathbf{M}_{\widehat{R}:c_{1}},\mathbf{M}_{\widehat{R}:c_{\widehat{r}}}$.
which concludes $\beta_{\widehat{r}+1}$ is nonzero, so we can simply assume it
is $-1$. Then

$\displaystyle\beta_{1}\mathbf{M}_{\widehat{R}:c_{1}}+...+\beta_{\widehat{r}}\mathbf{M}_{\widehat{R}:c_{\widehat{r}}}=\mathbf{M}_{\widehat{R}:i}\hskip
14.22636pt\implies\hskip
14.22636pt\beta_{1}\mathbf{M}_{R:c_{1}}+...+\beta_{\widehat{r}}\mathbf{M}_{R:c_{\widehat{r}}}=\mathbf{M}_{R:i}$

Due to uniqueness of $\alpha_{j}$’s above, we can tell that

$\displaystyle\alpha_{1}=\beta_{1}\hskip 28.45274pt\alpha_{2}=\beta_{2}\hskip
28.45274pt\ldots\hskip
28.45274pt\alpha_{\widehat{r}}=\beta_{\widehat{r}}\hskip
28.45274pt\alpha_{\widehat{r}}=\beta_{\widehat{r}}$

Then the vector
$y_{\widehat{R}}=\alpha_{1}\mathbf{M}_{\widehat{R}:c_{1}}+\ldots+\alpha_{\widehat{r}}\mathbf{M}_{\widehat{R}:c_{\widehat{r}}}-\mathbf{M}_{\widehat{R}:i}=0$
is a zero vector. However it is a contradiction because if $y_{\widehat{R}}$
is zero vector then $y_{a}=0$ due to $a\in\widehat{R}$ which we already know
$y_{a}\neq 0$.
Therefore, being nonzero of $y_{a}$ implies non-singularity of
$\mathbf{M}_{\widehat{R}:\widehat{C}}$ which is equivalent to the detection of
the independence of column $\mathbf{M}_{:i}$ due to lemma 2. As a conclusion,
probability of detection of independence of an active column is at least
$\frac{k}{m-observed}$ and considering the fact that $observed\geq j$ it
follows that $\frac{k}{m-observed}>\frac{k}{m-j}$ and it give the final
conclusion of the desired probability is lower bounded by: $\frac{k}{m-j}$. As
desired.

Step 4 : We can model execution of $\mathbf{ERR}$ as following stochastic
process:

$\displaystyle S_{0}=X_{0,1}+X_{0,2}+...+X_{0,n}$

where each of the $X_{0,j}$ corresponds to the indicator variable of the
activeness of the column $\mathbf{M}_{:j}$. Obviously, initially at least $r$
of these random variables are equal to 1. We define $S_{1}$ similarly:

$\displaystyle S_{1}=X_{1,1}+X_{1,2}+...+X_{1,n}$

and for any j that $X_{0,j}=1$ satisfied, at this phase $X_{1,j}$ will be
equal to 0 with probability at least $\frac{k}{m-0}$ from lemma C.2. For
remaining $j$’s that $X_{0,j}=0$ satisfied then $X_{1,j}=0$ also to be
satisfied. For the next step $S_{2}$ defined as:

$S_{2}=S_{1}+X_{2,1}+X_{2,2}+...+X_{2,n_{2}}$

where again for any $j$ that $X_{0,j}=1$ satisfied, at this phase $X_{1,j}$
will be equal to $0$ with probability at least $\frac{k}{m-1}$ from lemma C.2.
Remaining $j$’s will stay as $X_{2,j}$ to be equal to 0. In general

$\displaystyle S_{iter}=X_{iter,1}+X_{iter,2}+...+X_{iter,n_{2}}$

where again for any j that $X_{iter-1,j}=1$ satisfied, at this phase
$X_{iter,j}$ will be equal to 0 with probability at least
$\frac{k}{m-(iter-1)}$ from lemma C.2. The termination of algorithm is
equivalent to the point $S_{p}=0$ in this model. One can see termination of
this process is upper bounded by termination of the following process :

$\displaystyle
S^{\prime}_{0}=X^{\prime}_{0,1}+X^{\prime}_{0,2}+...+X^{\prime}_{0,r}$

where each of the $X^{\prime}_{0,j}$ is set to be equal to $1$. we define
$S^{\prime}_{1}$ in a similar way:

$\displaystyle
S^{\prime}_{1}=X^{\prime}_{1,1}+X^{\prime}_{1,2}+...+X^{\prime}_{1,r}$

where each of $X^{\prime}_{1,j}$ is equal to $0$ with probability
$\frac{k}{m}$. Then:

$\displaystyle
S^{\prime}_{2}=X^{\prime}_{2,1}+X^{\prime}_{2,2}+...+X^{\prime}_{2,r}.$

Similarly $X^{\prime}_{2,j}$ is set to be $0$ if $X^{\prime}_{1,j}=0$ and
$X^{\prime}_{2,j}$ is equal to $0$ with probability $\frac{k}{m-1}$ otherwise.
In general:

$\displaystyle
S^{\prime}_{iter}=X^{\prime}_{iter,1}+X^{\prime}_{iter,2}+...+X^{\prime}_{iter,r}$

again $X^{\prime}_{iter,j}=0$ if $X^{\prime}_{iter-1,j}=0$ and,
$X^{\prime}_{iter,j}=0$ with probability $\frac{k}{m-(iter-1)}$ otherwise.

Step 5: Here we use a combinatorial argument to bound number of observation in
each column.

######  Lemma C.4.

Let $X^{\prime}$ be a process that is zero initially: $X^{\prime}_{0}=1$ and
remaining entries defined as

$\displaystyle X^{\prime}_{i+1}=\begin{cases}\begin{cases}0&\text{with
probability }\frac{k}{m-i}\\\ 1&\text{otherwise}\end{cases}&\hskip
8.53581pt\text{if }\hskip 8.53581ptX^{\prime}_{i}=1\\\ 0&\hskip
8.53581pt\text{if }\hskip 8.53581ptX^{\prime}_{i}=0\end{cases}$

Then expected point that $X^{\prime}$ to switch to 0 is $\frac{m+1}{k+1}$.

######  Proof C.5.

Lets denote the expected switch time with $st$ and write the expression for
it:

$\displaystyle\mathbb{E}[st]=\sum
iP(st=i)=1\frac{k}{m}+2\frac{k}{m-1}\Big{(}1-\frac{k}{m}\Big{)}+3\frac{k}{m-2}\Big{(}1-\frac{k}{m}\Big{)}\Big{(}1-\frac{k}{m-1}\Big{)}+\dots$

We claim that this sum is equal to the expected position of the first $1$ in a
random binary string with $k$ many $1$ and $m-k$ many $0$. To observe truth of
the claim we notice followings:

  * •

First $1$ being in the first position is obviously $\frac{k}{m}$ as there are
$k$ many $1$’s out of $m$ many characters.

  * •

The probability of the first $1$ being in the second place is
$(1-\frac{k}{m})\frac{k}{m-1}$. The first entry being zero has probability:
$1-\frac{k}{m}$ and the second entry being one is $\frac{k}{m-1}$

  * •

The probability of the first $1$ being in the $i$-th place is

$\Big{(}1-\frac{k}{m}\Big{)}\Big{(}1-\frac{k}{m-1}\Big{)}\ldots\Big{(}1-\frac{k}{m-(i-1)}\Big{)}\Big{(}\frac{k}{m-(i-1)}\Big{)}.$

The first entry being zero has probability: $1-\frac{k}{m}$, the second entry
being zero has probability $1-\frac{k}{m-1}$ and so on so forth. Finally out
of remaining $m-i+1$ entries the next one being $1$ is equal to
$\frac{k}{m-(i-1)}$.

Then expected position of the first 1 is equal to

$\displaystyle
1\frac{k}{m}+2\frac{k}{m-1}\Big{(}1-\frac{k}{m}\Big{)}+3\frac{k}{m-2}\Big{(}1-\frac{k}{m}\Big{)}\Big{(}1-\frac{k}{m-1}\Big{)}+\ldots$

which is equal to $\mathbf{E}[st]$. Lets find the position of the first $1$ by
double counting technique. A word with $k$ number of $1$ and $m-k$ number of
$0$ can be represented as $a_{0}1a_{1}1a_{2}...1a_{k}$ where $a_{i}$
represents number of zeros between two $1$’s. Now, lets find number of first 1
in the $k+1$ sized set of following words

$\displaystyle a_{0}1a_{1}1a_{2}...1a_{k},$ $\displaystyle
a_{1}1a_{2},...,a_{k}1a_{0},$ $\displaystyle a_{2}1a_{3},...,a_{0}1a_{1},$
$\displaystyle\vdots$ $\displaystyle a_{k}1a_{0},...,a_{k}1a_{0}$

Expected number of first 1 here is simply

$\displaystyle\frac{a_{0}+1}{k+1}+\frac{a_{1}+1}{k+1}+\ldots+\frac{a_{k}+1}{k+1}=\frac{a_{0}+a_{1}+...+a_{k}+k+1}{k+1}=\frac{m+1}{k+1}.$

So, we can divide set of all words with $k$ many $1$’s and $m-k$ many $0$’s
into $k+1$-sized sets. For each group the average position of the first 1 will
be $\frac{m+1}{k+1}$. Therefore, in overall the average position of the first
$1$ is $\frac{m+1}{k+1}$.

A simple followup of this lemma is to notice:

$\mathbb{E}[st]=\frac{m+1}{k+1}<\frac{m}{k}$

due to $m>k$. Then, we can use the Markov inequality to get:

$P\Big{(}st>2\frac{m}{k}\Big{)}<\frac{1}{2}.$

Moreover, from the combinatorial counting argument we can imply that the
probability of $st>a$ will be given as

$\displaystyle P(st>a)=\frac{\binom{m-a}{k}}{\binom{m}{k}}$

using the previous inequality we can observe that:

$\displaystyle
P\Big{(}st>\frac{2m}{k}\Big{)}=\frac{\binom{m-2m/k}{k}}{\binom{m}{k}}<\frac{1}{2}$

Considering the fact

$\displaystyle f(x)=\frac{\binom{x-2m/k}{k}}{\binom{x}{k}}$

is an increasing function and

$\displaystyle P\Big{(}st>\frac{\alpha
m}{k}\Big{)}=\frac{\binom{m-2m/k}{k}}{\binom{m}{k}}\frac{\binom{m-4m/k}{k}}{\binom{m-2m/k}{k}}\cdots\frac{\binom{m-2\alpha
m/k}{k}}{\binom{m-2(\alpha-1)m/k}{k}}<(\frac{1}{2})^{\alpha}$

For a given $\epsilon$, if we set $\alpha=\log{\frac{1}{\epsilon}}$ we
conclude that with probability at least $1-\epsilon$ the following inequality
satisfied:

$\displaystyle st>2\frac{m}{k}\log{\frac{1}{\epsilon}}.$

Step 6: So, we can tell

$\displaystyle P\Big{(}X^{\prime}\geq
2\log{(\frac{1}{\epsilon})}\frac{m}{k}\Big{)}\leq\epsilon.$

Which means for a given $j$, with probability more than $1-\epsilon$,
$X^{\prime}_{i,j}$ will switch to zero before
$2\log(\frac{1}{\epsilon})\frac{m}{k}$ for any $j\in[r]$. Using union bound
argument, after $2\log(\frac{1}{\epsilon})\frac{m}{k}$ iteration with
probability more than $1-\epsilon r$, for any $i\in[r]$, $X^{\prime}_{i,j}$
will switch to zero.

Therefore, the process $S$ will stop before
$2\log{\frac{r}{\epsilon}}\frac{m}{k}$ iteration with probability
$1-\epsilon$. Remind that, termination time of $S$ corresponds to the value of
$T$ and number of total red points is bounded by $Tn$. Then number of total
red observations is bounded by:

$2\frac{mn}{k}\log{\frac{r}{\epsilon}}.$

Finaly, total number of observations is equal to the number of red
observations plus number of blue observations which gives the bound:

$\displaystyle(m+n-r)r+2\frac{mn}{k}\log{\frac{r}{\epsilon}}.$

To translate this result to coherence number rather than space sparsity
number, we use the following lemma:

######  Lemma C.6.

Let $\mathbb{U}$ be an $r$-dimensional subspace of $\mathbb{R}^{m}$. Then the
below relation between $\psi(\mathbb{U})$ and $\mu(U)$ holds:

$\displaystyle\mu(U)\geq\frac{m}{r}\frac{1}{\psi(\mathbb{U})}.$

######  Proof C.7.

We again denote $\psi(\mathbb{U})$ with $k$ for ease of reading. By the
definition of the space sparsity number, we see that there exists a vector
$v\in U$ and $k$ different indices $i_{1},i_{2},...,i_{k}$ such that the only
nonzero components of $v$ are $v_{i_{1}},v_{i_{2}},...,v_{i_{k}}$. Up to
scaling, we may assume that $v$ is a unit vector. This is equivalent to

$\displaystyle{v_{i_{1}}}^{2}+...+{v_{i_{k}}}^{2}=1$

Therefore, we observe that there is an index $i_{a}$ satisfies
${v_{i_{a}}}^{2}\geq\frac{1}{k}$. If this was not the case, then for all $j$
with $1\leq j\leq k$, ${v_{i_{j}}}^{2}<\frac{1}{k}$ should satisfy, and this
implies

$1={v_{i_{1}}}^{2}+...+{v_{i_{k}}}^{2}<k\frac{1}{k}=1$

and this is a contradiction. Using these facts, we can see that

$\displaystyle||P_{U}e_{i_{a}}||^{2}\geq||v\cdot e_{i_{a}}||^{2}=|v\cdot
e_{i_{a}}|^{2}={v_{i_{a}}}^{2}\geq\frac{1}{k}$

where $e_{i_{a}}$ is $i_{a}$’th standard basis of $\mathbb{R}^{m}$. The first
inequality follows from the fact that the length of projection of any vector
to the subspace $\mathbb{U}$ is always greater or equal than the length of the
projection onto a vector of that subspace. Thus, we have

$\displaystyle\mu(U)=\frac{m}{r}\underset{1\leq j\leq
m}{\max}||P_{U}e_{j}||^{2}\geq\frac{m}{r}||P_{U}e_{i_{a}}||^{2}\geq\frac{m}{r}\frac{1}{k}=\frac{m}{r}\frac{1}{\psi(\mathbb{U})}$

###  C.2 Discussion for Incoherent Row Spaces:

In the lemma C.6 we show that

$\mu(\mathbb{U})\geq\frac{m}{r}\frac{1}{\psi(\mathbb{U})}.$

and in the theorem above we prove that the observation complexity of
$\mathbf{ERR}$ is upper bounded by
$(m+n-r)r+2\frac{mn}{\psi(\mathbb{U})}\log{\frac{r}{\epsilon}}$ where
$\mathbb{U}$ is column space of the matrix $\mathbf{M}$.

Lets denote the fraction

$\gamma=\frac{m}{\psi(\mathbb{U})}\frac{1}{\mu(\mathbb{U})r}$

then lemma C.6 is equivalent to $\gamma\leq 1$. Lets transfer observation
complexity of $\mathbf{ERR}$ with respect to $\mu(\mathbb{U})$ using $\gamma$.
Then we get the observation complexity is

$(m+n-r)r+2\gamma\mu(\mathbb{U})r\log{r/\epsilon}$

and using the fact that $\gamma\leq 1$ this number is smaller than bound due
to Balcan and Zhang (2016):

$(m+n-r)+2\mu(\mathbb{U})r\log{r/\epsilon}$

In many cases $\gamma$ can be very small. For any matrix that has high value
of-$\psi(\mathbb{U})$ or low value of $\mu(\mathbb{U})$, $\gamma$ is
guaranteed to be very small. Specifically, if $\psi(\mathbb{U})$ is
$\Theta(m)$ or $\mu(\mathbb{U})$ is $\Theta{\frac{m}{r}}$ then $\gamma$ is
$\mathcal{O}(\frac{1}{r})$. Proofs for each case provided below:

$\psi(\mathbb{U})$ is $\Theta(m)$: Assigning $\psi(\mathbb{U})$ being
$\Theta(m)$ in the definition of $\gamma$, we conclude that $\gamma$ is
$\Theta(\frac{1}{\mu(U)r})$. Remember from the definition of the coherence,
$\mu(\mathbb{U})\geq 1$ for any subspace, which gives the final conclusion of
$\gamma$ is $\mathcal{O}(\frac{1}{r})$.
$\mu(\mathbb{U})$ is $\Theta{\frac{m}{r}}$: Assigning $\mu(\mathbb{U})$ being
$\Theta(\frac{m}{r})$ in the definition of $\gamma$, we conclude that $\gamma$
is $\Theta(\frac{1}{\psi(\mathbb{U})})$. Moreover, remember that from lemma
A.4, we know that $\psi(\mathbb{U})$ is $\Omega(r)$ which gives final
conclusion of $\mathcal{O}(\frac{1}{r})$.

###  C.3 Coherent Row Spaces

######  Theorem ( Coherent row space).

Let $r$ be the rank of underlying $m\times n$ sized matrix $\mathbf{M}$ with
column space $\mathbb{U}$ and row space $\mathbb{V}$. Then, $\mathbf{ERR}$
exactly recovers the underlying matrix $\mathbf{M}$ with probability at least
$1-\epsilon$ using at most

$(m+n-r)r+\frac{\frac{2m}{\psi(\mathbb{U})}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}}{\psi(\mathbb{V})}n$

observations.

######  Proof C.8.

We use the same terminology as previous theorem and $k$ and $t$ stands for
$\psi(\mathbb{U})$ and $\psi(\mathbb{V})$ correspondingly. So, if a column is
not in the column space of $C$ then we call it active.
From lemma C.2, we know that at any step if a column is still active, then
probability of its detection is at least $\frac{k}{m}$ where $k$ is the space
non-sparsity number for column space. Let’s just focus on active observations,
and estimate the number of required active observations to detect $r$-th
linearly independent column. We can see that, under the condition of each
observation being active observation and the probability of detection being
exactly $\frac{k}{m}$ the process of the detection of $r$-th independent
column can be modelled as negative binomial distribution.
Lets remind the formula of the probability mass function negative binomial
distribution as getting $a$-th success in the $a+b$’th step while success
probability being $p$ :

$f(a,b,p)=\binom{a+b-1}{a}p^{a}(1-p)^{b}$

For this problem, we are interested to find the probability for finding $r$-th
success at $N$-th trial which corresponds to :

$f(r,N-r,\frac{k}{m})=\binom{N-1}{r}{\Big{(}\frac{k}{m}\Big{)}}^{r}\Big{(}1-\frac{k}{m}\Big{)}^{N-r-1}$

As the number of observations is the focus of this theorem, we fix parameters
$k,m,r$ and investigate the behaviour of the function while $N$ being
variable. Intuitively, we use the following notation:

$\tau_{k,m,r}(N)=f(r,N-r,\frac{k}{m})$

In lemma C.9 and C.11 we investigate properties of this function to have
better understanding of failure probability of $\mathbf{ERR}$:

######  Lemma C.9.

$\tau_{k,m,r}(N)$ is a decreasing function after N being larger than
$(\frac{2m}{k}+1)r$. Specifically, we can give the following bound for the
decreasing rate:

$1-\frac{k}{m}<\frac{\tau_{k,m,r}(N+1)}{\tau_{k,m,r}(N)}<1-\frac{k}{2m}$

######  Proof C.10.

To show the decreasing we analyse the fraction :

$\displaystyle\frac{\tau_{k,m,r}(N+1)}{\tau_{k,m,r}(N)}=\frac{\binom{N}{r}{\Big{(}\frac{k}{m}\Big{)}}^{r}\Big{(}1-\frac{k}{m}\Big{)}^{N-r}}{\binom{N-1}{r}{\Big{(}\frac{k}{m}\Big{)}}^{r}\Big{(}1-\frac{k}{m}\Big{)}^{N-r-1}}$
$\displaystyle=\frac{\frac{N!}{r!(N-r)!}{\Big{(}\frac{k}{m}\Big{)}}^{r}\Big{(}1-\frac{k}{m}\Big{)}^{N-r}}{\frac{(N-1)!}{r!(N-1-r)!}{\Big{(}\frac{k}{m}\Big{)}}^{r}\Big{(}1-\frac{k}{m}\Big{)}^{N-r-1}}$
$\displaystyle=\frac{N}{N-r}(1-\frac{k}{m})$

So, we get following recursive formula:

$\displaystyle\tau_{k,m,r}(N+1)=\frac{N}{N-r}\Big{(}1-\frac{k}{m}\Big{)}{\tau_{k,m,r}(N)}.$

Left side of the the target inequality is easy to prove as $\frac{N}{N-r}>1$
implies

$\frac{\tau_{k,m,r}(N+1)}{\tau_{k,m,r}(N)}>1-\frac{k}{m}.$

Then, we only need to prove the right side of the inequality. Lets make the
following observations

$\frac{N}{N-r}=1+\frac{r}{N-r}$

and from the hypothesis of the lemma we have

$N>\Big{(}\frac{2m}{k}+1\Big{)}r\implies
N-r>\frac{2m}{k}r\implies\frac{r}{N-r}<\frac{k}{2m}.$

Now, we are ready to prove rigth side:

$\displaystyle\frac{\tau_{k,m,r}(N+1)}{\tau_{k,m,r}(N)}=\frac{N}{N-r}\Big{(}1-\frac{k}{m}\Big{)}$
$\displaystyle=\Big{(}1+\frac{r}{N-r}\Big{)}\Big{(}1-\frac{k}{m}\Big{)}$
$\displaystyle<\Big{(}1+\frac{k}{2m}\Big{)}\Big{(}1-\frac{k}{m}\Big{)}$
$\displaystyle=1-\frac{k}{2m}-\frac{k^{2}}{2m^{2}}$
$\displaystyle<1-\frac{k}{2m}.$

Therefore:

$\displaystyle
1-\frac{k}{m}<\frac{\tau_{k,m,r}(N+1)}{\tau_{k,m,r}(N)}<1-\frac{k}{2m}.$

Note that we can claim decreasing of $\tau_{k,m,r}$ just follows from the
right side of the inequality.

To explore more properties of the function $\tau_{k,m,r}$ we prove the
following lemma.

######  Lemma C.11.

Lets assume $n$ is a positive integer. Then $\tau_{k,m,r}$ satisfies the
following inequality

$\displaystyle\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+n\Big{)}\leq\frac{1}{n}.$

######  Proof C.12.

It is clear that $\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)\Big{)}<1$ as it is
value of a probability mass function. In lemma 3 we proved that the functions
$\tau_{k,m,r}$ is decreasing after $\frac{2m}{k}(r+1)$. Therefore, for any
positive integer $n$ the following inequalities satisfied:

$\displaystyle\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+n\Big{)}$
$\displaystyle<\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+n-1\Big{)}$
$\displaystyle\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+n\Big{)}$
$\displaystyle<\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+n-2\Big{)}$
$\displaystyle\vdots$
$\displaystyle\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+n\Big{)}$
$\displaystyle<\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)\Big{)}$

By summing all these inequalities we conclude:

$\displaystyle
n\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+n\Big{)}<\sum_{i=1}^{n}\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+i\Big{)}$

To bound the second term, we can use:

$\sum_{i=1}^{n}\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+i\Big{)}\leq\sum_{i=r}^{\infty}\tau_{k,m,r}(i)=1$

and dividing left and rigth side of the inequality above concludes:

$\displaystyle n\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+n\Big{)}<1.$

To apply the lemma above for $n=\frac{2m}{k}$ we get,

$\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}\Big{)}<\frac{k}{2m}$

Using right side of the lemma C.9 we notice :

$\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+i\Big{)}<\frac{k}{2m}\Big{(}1-\frac{k}{2m}\Big{)}^{i}$

for any positive integer $i$. Picking $i=\frac{2m}{k}\log{\frac{1}{\epsilon}}$
follows as :

$\displaystyle\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+\frac{2m}{k}\log{\frac{1}{\epsilon}}\Big{)}$
$\displaystyle<\frac{k}{2m}\Big{(}1-\frac{k}{2m}\Big{)}^{\frac{2m}{k}\log{\frac{1}{\epsilon}}}$
$\displaystyle<\frac{k}{2m}e^{-\log{\frac{1}{\epsilon}}}=\frac{k}{2m}\epsilon$

second inequality here is application of the
$(1-\frac{1}{\alpha})^{\alpha}<\frac{1}{e}$ for $\alpha>0$. Therefore we
currently have :

$\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+\frac{2m}{k}\log{\frac{1}{\epsilon}}\Big{)}<\frac{k}{2m}\epsilon$

and we target to bound :

$\sum_{i=0}^{\infty}\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+\frac{2m}{k}\log{\frac{1}{\epsilon}}+i\Big{)}.$

To apply right side of lemma C.9, $i$ times we conclude :

$\displaystyle\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+\frac{2m}{k}\log{\frac{1}{\epsilon}}+i\Big{)}$
$\displaystyle<$
$\displaystyle\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+\frac{2m}{k}\log{\frac{1}{\epsilon}}\Big{)}\Big{(}1-\frac{k}{2m}\Big{)}^{i}$

Therefore the summation above can be upper bounded as:

$\displaystyle\sum_{i=0}^{\infty}\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+$
$\displaystyle\frac{2m}{k}\log{\frac{1}{\epsilon}}+i\Big{)}<$
$\displaystyle<\sum_{i=0}^{\infty}\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+\frac{2m}{k}\log{\frac{1}{\epsilon}}\Big{)}\Big{(}1-\frac{k}{2m}\Big{)}^{i}$
$\displaystyle=\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+\frac{2m}{k}\log{\frac{1}{\epsilon}}\Big{)}\sum_{i=0}^{\infty}\Big{(}1-\frac{k}{2m}\Big{)}^{i}$
$\displaystyle=\tau_{k,m,r}\Big{(}\frac{2m}{k}(r+1)+\frac{2m}{k}+\frac{2m}{k}\log{\frac{1}{\epsilon}}\Big{)}\frac{2m}{k}$
$\displaystyle<\epsilon\frac{k}{2m}\frac{2m}{k}=\epsilon.$

Therefore, we conclude that the probability of $\mathbf{ERR}$ terminating
after $\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}$ is smaller than
$\epsilon$.

At this point we have number upper bound for number of active observations in
order to have $1-\epsilon$ probability of termination. However, we need to
give the bound with respect to number of overall observations. Following lemma
will help us for that purpose

######  Lemma C.13.

At every phase of the algorith-$\mathbf{ERR}$, if there is at least one active
observation, then there is at least $t$ many active observations.

######  Proof C.14.

The first step is to observe that, any column in $C$ is already inactive as
they are already in temporary column space. The second observation is any
column that is linear combination of columns in C also already inactive. We
prove the lemma by assuming the hypothesis of the lemma is not correct and we
will deduce contradiction from that. Therefore, we assume that there is a step
that the number of active columns is less than $t$, under the condition not
all columns are inactive.

Number of active columns being smaller than $t$ implies that the number of
inactive columns is larger than $n-t$. Which implies there is a subset of
columns- $\Omega^{\prime}$ that satisfies $|\Omega^{\prime}|>n-t$ and
$\mathbf{M}_{:\Omega^{\prime}}$ has rank of at most $r-1$ (as there are still
some active columns).

We know that the rank of $\mathbf{M}$ being $r$ implies there is at least one
set of $r$ many linearly independent rows. Lets denote one of these sets by
$R=\\{j_{1},j_{2},...,j_{r}\\}$ and naturally, the set of row vectors
$\mathbf{M}_{j_{1}:},\mathbf{M}_{j_{2}:},...,\mathbf{M}_{j_{r}:}$ are linearly
dependent.

Returning back to the argument $M_{:\Omega^{\prime}}$ having a rank of at most
$r-1$, implies the rank of $M_{R:\Omega^{\prime}}$ is also at most $r-1$.
Therefore, there is a linear dependence relation among the vectors
$\mathbf{M}_{j_{1}:\Omega^{\prime}}$, $\mathbf{M}_{j_{2}:\Omega^{\prime}}$, .
. . ,$\mathbf{M}_{j_{r}:\Omega^{\prime}}$. As we already have
$\Omega^{\prime}>n-t$ then using lemma 1 we conclude that there is linear
dependence relation among
$\mathbf{M}_{j_{1}:},\mathbf{M}_{j_{2}:},...,\mathbf{M}_{j_{r}:}$ which is a
contradiction. Therefore, if there is one active column we can conclude there
is at least $t$ many active columns.

Rest of the proof is simple counting argument. We know that if we have
$\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}$ many observations
then with probability larger than $1-\epsilon$ our algorithm succeeds.
Moreover, from the lemma above, as at each phase we have at least
$\psi(\mathbb{V})$ many observations,

$\frac{\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}}{t}$

many phase is enough to have desired number of active observations. Note that,
at each step we have at most n many observation, which concludes the statement

$\frac{\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}}{t}n$

many observation is enough to guarantee with probability $1-\epsilon$

###  C.4 Proof of corollary 3.3

We start by rephrasing the corollary 5 and prove the statement for each case
later on.

######  Corollary.

Observation complexity of $\mathbf{ERR}$ studied for three different case
below:

  * •

if $\psi(\mathbb{V})=\mathcal{O}(1)$ then observation complexity is upper
bounded by $(m+n-r)r+2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})}\\\
=(m+n-r)r+\mathcal{O}\big{(}nr\mu_{0}\log{(\frac{r}{\epsilon})}\big{)}$. (
this bound matches with Balcan and Zhang (2016) but many times it is much
smaller quantity as we discussed in previous section)

  * •

if $\psi(\mathbb{V})=\Theta(r)$ then observation count is upper bounded by
$(m+n-r)r+\mathcal{O}\Big{(}\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{r}n\Big{)}\\\
=(m+n-r)r+\mathcal{O}\big{(}n\mu_{0}(r+\log{\frac{1}{\epsilon}})\big{)}$.
Selecting $\epsilon=\frac{1}{2^{\mathcal{O}(r)}}$ gives bound of
$mr+\mathcal{O}(n\mu_{0}r)$

  * •

if $\psi(\mathbb{V})=\Theta(n)$ then observation count is upper bounded by
$(m+n-r)r+\mathcal{O}\Big{(}\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{n}n\Big{)}\\\
=(m+n-r)r+\mathcal{O}\big{(}\mu_{0}r(r+\log{\frac{1}{\epsilon}})\big{)}$
Selecting $\epsilon=\frac{1}{2^{\mathcal{O}(r)}}$ gives bound:
$\mathcal{O}((m+n-r)r)$

######  Proof C.15.

Case : $\psi(\mathbb{V})=\mathcal{O}(1)$. From the theorem 3.2 the observation
complexity is upper bounded by

$(m+n-r)r+\mathrm{min}\Big{(}2\frac{mn}{{\psi}(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n\Big{)}$

therefore it is upper bounded by
$(m+n-r)r+2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})}$. Moreoover,
in lemma C.6 we show

$\mu(\mathbb{U})\geq\frac{m}{r}\frac{1}{\psi(\mathbb{U})}$

which upper bounds the last quantity by
$(m+n-r)r+\mathcal{O}\big{(}nr\mu_{0}\log{(\frac{r}{\epsilon})}\big{)}$.

Case $\psi(\mathbb{V})=\Theta(r)$: This time we choose the second term in
$\mathrm{min}$ operator of theorem 3.2. We note that
$\frac{m}{\psi(\mathbb{U})}$ can be upper bounded by $\mu(\mathbb{U})r$ and
plugging it together with $\psi(\mathbb{V})=\Theta(r)$ gives us upper bound of
$(m+n-r)r+\mathcal{O}\big{(}n\mu_{0}(r+\log{\frac{1}{\epsilon}})\big{)}$.
Moreover, if $\epsilon=\frac{1}{2^{\mathcal{O}(r)}}$ then
$\log{\frac{1}{\epsilon}}$ is $\mathcal{O}(r)$, therefore right summand is
bounded by $\mathcal{O}(n\mu_{0}r)$. Considering the fact $\mu_{0}\geq 1$
always, then overall expression is upper bounded by
$mr+\mathcal{O}(n\mu_{0}r)$

Case $\psi(\mathbb{V})=\Theta(n)$: This case is just similar too previous case
with the difference of plugging $\psi(\mathbb{V})=\Theta(n)$ gives us the
bound of
$(m+n-r)r+\mathcal{O}\big{(}\mu_{0}r(r+\log{\frac{1}{\epsilon}})\big{)}$.
Using the similar bound to $\epsilon$ makes the right summand to be
$\mathcal{O}(\mu_{0}r^{2})$. Moreover from the definition of coherence we have
$\mu_{0}\leq\frac{m}{r}$ which upper bounds this term by $\mathcal{O}(mr)$
therefore overall sum is upper bounded by $\mathcal{O}((m+n-r)r)$.

##  Appendix D Proof of Theorem 3.4. Exact Recovery While Rank Estimation

We start with rephrasing the theorem 4. Then we prove the theorem statement
and its corollary.

######  Theorem.

(Exact Recovery while Rank Estimation) Let $r$ be the rank of underlying
$m\times n$ sized matrix $\mathbf{M}$ with column space $\mathbb{U}$ and row
space $\mathbb{V}$. Then, $\mathbf{ERRE}$ exactly recovers the underlying
matrix $\mathbf{M}$ while estimating rank with probability at least
$1-(\epsilon+e^{-T\frac{\psi(\mathbb{U})\psi(\mathbb{V})}{m}})$ using at most

$\displaystyle(m+n-r)r+Tn+\mathrm{min}\Big{(}2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n)\Big{)}$

observations.

######  Proof D.1.

We again use $k$ and $t$ for $\psi(\mathbb{U})$ and $\psi(\mathbb{V})$
correspondingly and use all the terminology from the previous proofs. Then, we
start by proving that under the scenario there is still active column, then
with probability $1-e^{-T\frac{kt}{m}}$, it will be detected in $T$ phases. We
prove the following key lemma in order to accomplish the proof of the theorem.

######  Lemma D.2.

Lets assume the underlying matrix $\mathbf{M}$ has row space non-sparsity
number $k$ and column space non-sparsity number $t$. Then, if at an
intermediate step of $\mathbf{ERRE}$ still column space not recovered
completely, then with probability $1-e^{-T\frac{kt}{m}}$ new independent
column will be detected within $T$ phases.

######  Proof D.3.

For every active column observation, the probability of detecting independence
is at least $1-\frac{k}{m}$ from the lemma C.2. From the lemma C.13 , if there
is one active column, then there is at least $t$ many active column in that
phase. Therefore, the probability of detection of an active column is at least

$\Big{(}1-\frac{k}{m}\Big{)}^{t}.$

Then, we conclude that after $T$ many phase, detection probability is at least

$\Big{(}1-\frac{k}{m}\Big{)}^{tT}.$

Using the inequality $1+x\leq e^{x}$ for $\forall x\in\mathbb{R}$ the quantity
above can be bounded by:

$\Big{(}1-\frac{k}{m}\Big{)}^{tT}<e^{-T\frac{kt}{m}}.$

In the rest of the proof we show that with probability at least
$1-e^{-T\frac{kt}{m}}$, estimated rank $\widehat{r}$ is equal to $r$.

$P(r=\widehat{r})=1-\big{(}P(r<\widehat{r})+P(r>\widehat{r})\big{)}$

$P(r<\widehat{r})=0$ trivially satisfied, $\widehat{r}$ represents number of
detected linearly independent columns of $\mathbf{M}$ which is always bounded
by $r$. Now, all we need to do is to bound $P(r<\widehat{r})$. We denote the
event of existence of active column by $ACE$. Then, trivially:

$P(\widehat{r}<r)=P\big{(}\widehat{r}<r\hskip 2.84526pt\text{and}\hskip
2.84526ptACE\big{)}$

Moreover, we can write

$P\big{(}\widehat{r}<r\hskip 2.84526pt\text{and}\hskip
2.84526ptACE\big{)}=\sum_{i=0}^{r-1}P\big{(}\widehat{r}=i\hskip
2.84526pt\text{and}\hskip 2.84526ptACE\big{)}=P\big{(}ACE\hskip
2.84526pt|\hskip 2.84526pt\widehat{r}=i\big{)}P(\widehat{r}=i)$

To finish the proof we just need to observe following equality / inequality :

$\displaystyle P(\widehat{r}<r)=\sum_{i=0}^{r-1}P\big{(}\widehat{r}=i\wedge
ACE\big{)}=\sum_{i=0}^{r-1}P\big{(}ACE|\widehat{r}=i\big{)}P(\widehat{r}=i)$

From the lemma above, we can imply that

$P\big{(}ACE|\widehat{r}=i\big{)}\leq e^{-T\frac{kt}{m}}$

and as probability of $P(\widehat{r}=r)\neq 0$, we conclude
$P(\widehat{r}<r)<1$. Equivalently,

$\sum_{i=0}^{r-1}P\big{(}\widehat{r}=i\big{)}<1$

which all together these two inequalities concludes

$\displaystyle
P(\widehat{r}<r)=\sum_{i=0}^{r-1}P\big{(}ACE|\widehat{r}=i\big{)}P(\widehat{r}=i)\leq
e^{-T\frac{kt}{m}}\sum_{i=0}^{r-1}P(\widehat{r}=i)\leq e^{-T\frac{kt}{m}}$

To finalize the proof, we divide the algorithm $\mathbf{ERRE}$ into two parts.
First part, is the detection point of the last independent column by
algorithm, and second part is waiting T many rounds to check if there is any
independent column left. Moreover, $\mathbf{ERRE}$ would fail generating
correct matrix only if failure in the second part happens (there is still
independent column not detected, but checking tells us that there is no left)
i.e. $\widehat{r}<r$ which we just show $P(\widehat{r}<r)<e^{-T\frac{kt}{m}}$.
This concludes that with probability at least $1-e^{-T\frac{kt}{m}}$ recovered
matrix is correct.
Therefore, with probability $1-e^{-T\frac{kt}{m}}$ the first part of the
algorithm is just equivalent to the algorithm $\mathbf{ERR}$, which with
probability more than $1-\epsilon$ observation complexity is bounded by

$\displaystyle(m+n-r)r+\mathrm{min}\Big{(}2\frac{mn}{k}\log{(\frac{4r}{\epsilon})},\frac{\frac{2m}{k}(r+2+\log{\frac{1}{\epsilon}})}{t}n\Big{)}$

using the union bound we conclude that with probability at least
$1-\epsilon+e^{-T\frac{kt}{m}}$, the algorithm recovers underlying matrix
correctly and observation complexity is bounded by

$\displaystyle(m+n-r)r+Tn+\mathrm{min}\Big{(}2\frac{mn}{k}\log{(\frac{4r}{\epsilon})},\frac{\frac{2m}{k}(r+2+\log{\frac{1}{\epsilon}})}{t}n\Big{)}$

######  Corollary.

Lets assume that either $\psi(\mathbb{U})$ or $\psi(\mathbb{V})$ is big enough
i.e. $\psi(\mathbb{U})\psi(\mathbb{V})\geq m$. For a given $\epsilon$ lets set
$T=\log{\frac{1}{\epsilon}}$, then $\mathbf{ERRE}$ recovers underlying matrix
with probability $1-2\epsilon$ using just

$\displaystyle(m+n-r)r+n\log{\frac{1}{\epsilon}}+\mathrm{min}\Big{(}2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n\Big{)}$

######  Proof D.4.

We first observe following inequality as implication of given conditions:

$\displaystyle kt\geq m\implies\frac{kt}{m}\geq 1\implies e^{\frac{kt}{m}}\geq
e\implies e^{-\frac{kt}{m}}\leq\frac{1}{e}$

The rest of the proof is just straightforward application of the theorem.
Setting $T=\log{\frac{1}{\epsilon}}$ to the statement of theorem tells with
probability at least $1-(\epsilon+e^{-\frac{kt}{m}\log{\frac{1}{\epsilon}}})$
using

$\displaystyle(m+n-r)r+n\log{\frac{1}{\epsilon}}+\mathrm{min}\Big{(}2\frac{mn}{k}\log{(\frac{4r}{\epsilon})},\frac{\frac{2m}{k}(r+2+\log{\frac{1}{\epsilon}})}{t}n\Big{)}$

observations. Considering the fact that $e^{-\frac{kt}{m}}\leq\frac{1}{e}$ we
conclude that

$\displaystyle
e^{-\frac{kt}{m}\log{\frac{1}{\epsilon}}}\leq\Big{(}\frac{1}{e}\Big{)}^{\log{\frac{1}{\epsilon}}}=e^{-\log{\frac{1}{\epsilon}}}=e^{\log{\epsilon}}=\epsilon$

Which concludes that with probability at least $1-2\epsilon$ the observation
complexity is bounded by

$\displaystyle(m+n-r)r+n\log{\frac{1}{\epsilon}}+\mathrm{min}\Big{(}2\frac{mn}{k}\log{(\frac{4r}{\epsilon})},\frac{\frac{2m}{k}(r+2+\log{\frac{1}{\epsilon}})}{t}n\Big{)}$

##  Appendix E Proof of Theorem 3.6. Exact Recovery with Two Phases

Lets remind that in the algorithm $\mathbf{EREI}$ we define
$\mathrm{min}\Big{(}2\frac{m}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}\Big{)}$.
Basically there is two case to show algorithm recovers the underlying matrix
correctly with probability $1-\epsilon$.

###  E.1  $d=2\frac{m}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})}$

We first start with the case that if minimum of these two quantities is
$2\frac{m}{k}\log{(\frac{r}{\epsilon})}$. As the matrix has rank $r$, there
exists at least one set of linearly independent columns with $r$ columns. We
select the set of linear independent columns$-C$ that has lexicographically
smallest indices. We show sampling $2\frac{m}{k}\log{(\frac{1}{\epsilon})}$
entries from each column will give us the probability of at least
$1-r\epsilon$ correctly recovery.
From the Step 5 of proof of the theorem 3.4 we can see sampling
$2\frac{m}{k}\log{(\frac{1}{\epsilon})}$ entries from an active column, would
give guarantee of probability of at least $1-\epsilon$ detection of
independence. As $C$ is lexicographically smallest, each column is active on
the time entries sampled from it, and each of $r$ columns will succeed with
probability at least $1-\epsilon$. Therefore, using union bound, with
probability $1-r\epsilon$ all of the columns in C will succeed, which
guarantees the exact recovery.
Replacing $\epsilon$ by $\frac{\epsilon}{r}$ will conclude the result that
sampling $2\frac{m}{k}\log{(\frac{r}{\epsilon})}$ from each column will
guarantees the correctness of the algorithm with probability at least
$1-\epsilon$.

###  E.2
$d=\frac{\frac{2m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}$

From the follow up of lemma C.2, we conclude that in a process of
$\frac{k}{m}$ probability success and $1-\frac{k}{m}$ probability of failure,
having $\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}$ trial is
enough to guarantee getting $r$ many success with at least probability
$1-\epsilon$.
Failure probability of the algorithm $\mathbf{EREI}$ is equal to failing
finding $r$ linearly independent columns. Consider following equation:

$\displaystyle P\big{(}\mathbf{EREI}fails\big{)}$
$\displaystyle=P\Big{(}\mathbf{EREI}fails\text{ and
TNAO}\geq\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}\Big{)}$
$\displaystyle+P\Big{(}\mathbf{EREI}fails\text{ and
TNAO}<\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}\Big{)}$

where we denote TNAO as total number of active observations. Recall that we
call an observation active, if it is active in the execution time (the column
is still not contained in the current column space). Intuitively we represent
NAO by number of active observations executed by the algorithm $\mathbf{EREI}$
in the given specific time.
From lemma C.13, if there exists an active column, then there exists at least
$t$ many active columns. Therefore, failure of the algorithm is equivalent to
existence of an active column when algorithm terminates. Moreover each of our
observations in those columns were active observations and considering the
fact that we observed
$\frac{\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}}{t}$ many
entries in each of them, total number of active observations is at least

$\displaystyle
t\frac{\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}}{t}=\frac{2m}{k}\Big{(}r+2+\log{\frac{1}{\epsilon}}\Big{)}$

Therefore
$P\Big{(}\text{NAO}<\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}|\mathbf{EREI}fails\Big{)}=0$
and using Bayesian rule we conclude

$\displaystyle P\Big{(}\mathbf{EREI}fails\text{ and
TNAO}\leq\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}\Big{)}=0$

Then, following equation simplly satisfied:

$\displaystyle
P\big{(}\mathbf{EREI}fails\big{)}=P\Big{(}\mathbf{EREI}fails\text{ and
TNAO}\geq\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}\Big{)}$

We can observe the following inequality as $\mathbf{EREI}$ may tamporarily
fail at the point that the number of active observations is
$\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}$ but it can succeed
finding remaining independent columns later during the execution:

$\displaystyle P\Big{(}\mathbf{EREI}\text{ currently fail when NAO =}$
$\displaystyle\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}\Big{)}\geq$
$\displaystyle P\Big{(}\mathbf{EREI}fails\text{ and
TNAO}\geq\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}\Big{)}$

Therefore we conclude that:

$\displaystyle P\big{(}\mathbf{EREI}fails\big{)}\leq
P\Big{(}\mathbf{EREI}\text{ currently fail when NAO =}$
$\displaystyle\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}\Big{)}$

Remember the fact that at each active observation probability of
$\mathbf{EREI}$ detecting linear independence of is larger or equal than
$\frac{k}{m}$. From the previous discussion if the probability is exactly
equal to $\frac{k}{m}$ then still not finding $r$ linearly independent column
at $\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}$ observations is
less than $\epsilon$. Therefore, $\mathbf{EREI}$ not detecting r linearly
independent column after
$\frac{2m}{k}\big{(}r+2+\log{\frac{1}{\epsilon}}\big{)}$ observations is
smaller than $\epsilon$, which is equivalent to

$\displaystyle P\big{(}\mathbf{EREI}fails\big{)}\leq\epsilon$

as desired.

##  Appendix F Sparse Random Noise

We first start with the discussion regarding the sparsity-number of row space
of induced matrix:

######  Lemma F.1.

Lets assume that for a given $m\times n$ sized rank$-r$ matrix
$\widetilde{\mathbf{M}}$, the nonsparsity-number of it row space
$\widetilde{\mathbb{V}}$ is equal to one: $\psi(\widetilde{\mathbb{V}})=1$.
Then there is a column$-c$, that deletion of it decrements the rank:
$\mathrm{rank}(\widetilde{\mathbf{M}}_{:[n]\setminus\\{c\\}})=r-1$.

######  Proof F.2.

From the definition of nonsparsity-number, we notice that, it is always
positive and moreover, only case that it is equal to $1$ is if some of the
standard basis vector $e_{i}$ is contained in the space. Then lets assume that
the row space contains $e_{i_{0}}$, then we claim that the deletion of the
column $i_{0}$ decrements the rank.
Lets assume that
$\mathrm{rank}(\widetilde{\mathbf{M}}_{:[n]\setminus\\{i_{0}\\}})=r$.
Moreover, lets denote the $\widetilde{\mathbf{M}}^{0}$ by the matrix that is
$i_{0}$-th column replaced by zero vector. It is trivial to see that that
$\mathrm{rank}(\widetilde{\mathbf{M}}_{:[n]\setminus\\{i_{0}\\}})=\mathrm{rank}(\widetilde{\mathbf{M}}^{0})$.
Therefore $\mathrm{rank}(\widetilde{\mathbf{M}}^{0})=r$ satisfies. Moreover,
row space of $\widetilde{\mathbf{M}}^{0}$ is subset of row space of
$\widetilde{\mathbf{M}}$, however, as both of them has the same rank $r$,
these space are the same. But, this is a contradiction to the fact that,
$e_{i_{0}}$ is contained in the row space of $\widetilde{\mathbf{M}}$ but not
in the row space of $\widetilde{\mathbf{M}}^{0}$ (due to the fact that, entire
row space has $0$ in its $i_{0}$-th coordinate). Then, our assumption is
wrong, $\mathrm{rank}(\widetilde{\mathbf{M}}_{:[n]\setminus\\{i_{0}\\}})$
cannot be $r$ and only other possible option is $r-1$. Therefore
$\mathrm{rank}(\widetilde{\mathbf{M}}_{:[n]\setminus\\{c\\}})=r-1$ satisfies.

######  Lemma F.3.

Lets assume that for a given $m\times n$ sized rank$-r$ matrix
$\widetilde{\mathbf{M}}$ with row space $\widetilde{\mathbb{V}}$, several
columns are deleted. Then, rank of the matrix is preserved, and its non-
sparsity number is decreased by at most $a-$where $a$ stands for the number of
columns those are deleted.

######  Proof F.4.

The proof is just inductively application of following claims:

  * 1

Deletion of single column, can reduce nonsparsity-number by at most 1.

  * 2

if $\psi(\widetilde{\mathbb{V}})>1$, deletion of a column cannot decrement the
rank.

Lets prove the first claim: Lets assume for contradiction that, there is a
column $c$ that its deletion causes drop of row space nonsparsity-number by 2,
i.e. $\psi(\widetilde{\mathbb{V}})-\psi(\mathbb{V}^{\prime})\geq 2$, where
$\mathbb{V}^{\prime}$ is the row space of
$\widetilde{\mathbf{M}}_{:[n]\setminus\\{c\\}}$. Let remind that the
definition of nonsparsity-number:
$\psi(\mathbb{V}^{\prime})=\mathrm{min}\\{\psi(x)|x\in\mathbb{V}^{\prime}\text{
and }x\neq 0\\}$. Lets pick the nonzero vector $x_{0}\in\mathbb{V}^{\prime}$
which satisfies the minimality in this definition. As $\mathbb{V}^{\prime}$ is
restriction of $\widetilde{\mathbb{V}}$ to the index set
$[n]\setminus\\{c\\}$, there is a vector $y\in\mathbb{V}$ such that
$y_{[n]\setminus\\{c\\}}=x_{0}$. Therefore
$\|y\|_{0}\leq\|x_{0}\|_{0}+1=\psi(\mathbb{V}^{\prime})+1$. Considering,
$\psi(\widetilde{\mathbb{V}})\leq\|y\|_{0}\leq\|x_{0}\|_{0}+1=\psi(\mathbb{V}^{\prime})+1$
which implies $\psi(\widetilde{\mathbb{V}})-\psi(\mathbb{V}^{\prime})\leq 1$
and this contradicts to the assumption. Therefore, first claim indeed always
satisfied.
Now, we prove the second claim: This is a simple statement, once we notice
that if deletion of the column $c$ results decrement in the rank of the
matrix, then $e_{c}$ (i.e. $c-$th standard vector) is contained in the row
space of $\widetilde{\mathbf{M}}$. The proof is simple as following:
Lets assume without lost of generality columns with the index set
$\mathcal{B}=\\{c_{1},c_{2},\ldots,c_{r-1},c\\}$ is a basis for column space.
Note that, $c$ should be part of any basis, because without column$-c$ the
column space has dimension $r-1$. Moreover, we know that for any
$i\notin\mathcal{B}$, the column $\widetilde{\mathbf{M}}_{:i}$ can be written
as linear combination of columns $\\{c_{1},c_{2},\ldots,c_{r-1}\\}$ i.e.
$\widetilde{\mathbf{M}}_{:i}=\sum_{j=1}^{r-1}\alpha_{j}\widetilde{\mathbf{M}}_{:c_{j}}$
for scalar $\alpha_{j}$’s. Moreover, considering the fact that,
$\widetilde{\mathbf{M}}_{:\mathcal{B}}$ has rank equal to $r$, we can find the
set of rows $R=\\{R_{1},R_{2},\ldots,R_{r}\\}$, that
$\mathbf{M}_{R:\mathcal{B}}$ also has rank $r$. Considering the fact that,
$\widetilde{\mathbf{M}}_{R:\mathcal{B}}$ is $r\times r$ sized matrix, then its
row space contains the standard basis vector: $(0,0,\ldots,0,1)$. This follows
that there is a linear combination of rows $R=\\{R_{1},R_{2},\ldots,R_{r}\\}$
with some scalars $\beta_{1},\beta_{2},\ldots,\beta_{r}$ that

$\displaystyle\beta_{1}\widetilde{\mathbf{M}}_{R_{1}:\mathcal{B}}+\beta_{2}\widetilde{\mathbf{M}}_{R_{2}:\mathcal{B}}+\ldots+\beta_{r}\widetilde{\mathbf{M}}_{R_{r}:\mathcal{B}}=(0,0,\ldots,0,1).$

For a given $i\notin\mathcal{B}$ lets check the $i-$th coordinate of the
vector

$\displaystyle\beta_{1}\widetilde{\mathbf{M}}_{R_{1}:i}+\beta_{2}\widetilde{\mathbf{M}}_{R_{2}:i}+\ldots+\beta_{r}\widetilde{\mathbf{M}}_{R_{r}:i}.$

Remember that
$\widetilde{\mathbf{M}}_{:i}=\sum_{j=1}^{r-1}\alpha_{j}\widetilde{\mathbf{M}}_{:c_{j}}$
as $i\notin\mathcal{B}$, therefore the sum above can be written as:

$\displaystyle\beta_{1}\widetilde{\mathbf{M}}_{R_{1}:i}+\beta_{2}\widetilde{\mathbf{M}}_{R_{2}:i}+\ldots+\beta_{r}\widetilde{\mathbf{M}}_{R_{r}:i}$
$\displaystyle=\beta_{1}\sum_{j=1}^{r-1}\alpha_{j}\widetilde{\mathbf{M}}_{:c_{j}}+\beta_{2}\sum_{j=1}^{r-1}\alpha_{j}\widetilde{\mathbf{M}}_{:c_{j}}+\ldots+\beta_{r}\sum_{j=1}^{r-1}\alpha_{j}\widetilde{\mathbf{M}}_{:c_{j}}$
$\displaystyle=\alpha_{1}\sum_{i=1}^{r}\beta_{i}\widetilde{\mathbf{M}}_{:c_{1}}+\alpha_{2}\sum_{i=1}^{r}\beta_{i}\widetilde{\mathbf{M}}_{:c_{2}}+\ldots+\alpha_{r-1}\sum_{i=1}^{r}\beta_{i}\widetilde{\mathbf{M}}_{:c_{r-1}}$
$\displaystyle=\alpha_{1}\times 0+\alpha_{2}\times 0+\ldots+\alpha_{r-1}\times
0=0$

and this concludes that

$\displaystyle\beta_{1}\widetilde{\mathbf{M}}_{R_{1}:}+\beta_{2}\widetilde{\mathbf{M}}_{R_{2}:}+\ldots+\beta_{r}\widetilde{\mathbf{M}}_{R_{r}:}=(0,0,\ldots,0,1,0,\ldots,0)$

Therefore $e_{c}$ is in the row space, and this implies that
$\psi(\widetilde{\mathbb{V}})=1$. Therefore,if
$\psi(\widetilde{\mathbb{V}})>1$ then deletion of a column cannot decrement
rank.

EEREI: Extended Exact recovery with estimated information

Input: $r,\psi(\mathbb{U}),\psi(\mathbb{V})$
Initialize:
$k=0,\widehat{\mathbf{U}}^{0}=\emptyset,d=2\frac{m}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},R=\emptyset$

1: if $\xi\leq\frac{\psi(\mathbb{V})}{2}$

2:
$d=\mathrm{min}\Big{(}2\frac{m}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{4m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}\Big{)}$

3: Draw uniformly random entries $\Omega\subset[m]$ of size $d$

4: for $i$ from $1$ to $n$ do

5: if
$\|\mathbf{M}_{\Omega:i}-{\mathcal{P}_{\mathbf{\widehat{U}_{\Omega}^{k}}}}\mathbf{M}_{\Omega:i}\|>0$

6: Fully observe $\mathbf{M}_{:i}$

7:
$\widehat{\mathbf{U}}^{k+1}\leftarrow\widehat{\mathbf{U}}^{k}\cup\mathbf{M_{:i}}$,
Orthogonalize $\widehat{\mathbf{U}}^{k+1}$, $k=k+1$

8: Select a row $a\in\Omega\setminus R$ that,
$\mathbf{\widehat{U}_{R\cup\\{a\\}}^{k+1}}$ is rank $k+1$ then $R\leftarrow
R\cup\\{a\\}$

9: Draw uniformly random entries $\Delta\subset[m]\setminus R$ of size $d$ and
$\Omega=\Delta\cup R$

10: Observe unobserved entries in $\mathbf{M}_{R:}$

11: for $i$ from $1$ to $n$ do

12: if $\mathbf{M}_{:i}$ not fully observed :
$\widehat{\mathbf{M}}_{:i}=\widehat{\mathbf{U}}^{k}{\widehat{\mathbf{U}}^{k^{+}}_{R:}}\widehat{\mathbf{M}}_{R:i}$

13: Detect all the columns that their deletion decrements rank and collect
them in $\Sigma$

Output: Noisy Columns - $\Sigma$, recovered underlying matrix
$\widehat{\mathbf{M}}_{:[n]\setminus\Sigma}$

The proof of the algorithm $\mathbf{EEREI}$ correctly detects noisy columns is
the same as the proof provided in Balcan and Zhang (2016), therefore we don’t
see necessity to provide it here. Moreover, the correct recovery of the
remaining entries is the same as the proof of $\mathbf{EREI}$ with only
difference, if $\xi\leq\frac{\psi(\mathbb{V})}{2}$ happens and
$2\frac{m}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})}>\frac{\frac{4m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}$.
However, the crucial step here will be to notice number of active columns will
be at least $\frac{\psi(\mathbb{V})}{2}$ and at each active column we are
doing
$\frac{\frac{4m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}$
many observations which gives overall

$\displaystyle\frac{\frac{4m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}\times\frac{\psi(\mathbb{V})}{2}=2\frac{m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})$

active observations, which is the required number of active observations in
order to detect $r$ complete column space with probability $1-\epsilon$.

##### Number of Observations:

The number of observations is simply $\xi$ many additional observed columns
and rows, compared to the algorithm $\mathbf{EREI}$ with the slight difference
if $\xi<\frac{\psi(\mathbb{V})}{2}$ then

$\displaystyle(m+n-r)r+\mathrm{min}\Big{(}2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})},\frac{\frac{4m}{\psi(\mathbb{U})}(r+2+\log{\frac{1}{\epsilon}})}{\psi(\mathbb{V})}n\Big{)}+\xi(m+n)$

and if $\xi>\frac{\psi(\mathbb{V})}{2}$

$\displaystyle(m+n-r)r+2\frac{mn}{\psi(\mathbb{U})}\log{(\frac{r}{\epsilon})}+\xi(m+n)$

###  F.1 Recall for properties of non-degenerate subspace

Lets remind the characteristics of non-degenerate random vectors provided in
Balcan and Zhang (2016):
Let $\mathbf{E}^{s}\in\mathbb{R}^{m\times s}$ be matrix consisting of
corrupted vectors drawn from any non-degenerate distribution. Let
$\mathbb{U}^{k}∈\mathbb{R}^{m\times k}$ be any fixed matrix with rank $k$.
Then with probability 1, we have

  * •

$\mathrm{rank}(\mathbf{E}^{s})=s$ for any $s\leq m$

  * •

$\mathrm{rank}(\mathbf{E}^{s},x)=s+1$ holds for
$x\in\mathbf{U}^{k}\subset\mathbb{R^{m}}$ uniformly and $s\leq m-k$, where $x$
can be depend or independent on $\mathbf{E}^{s}$

  * •

$\mathrm{rank}(\mathbf{E}^{s},\mathbb{U}^{k})=s+k$ given that $s+k\leq m$

  * •

The marginal of non-degenerate distribution is non-degenerate

##  Appendix G Bounded Deterministic Noise

Proofs here are inspired by the work of Balcan and Zhang (2016), with the
given difference that here we use different$-$ smaller observation complexity.
For sake of completeness of the proof, we prove all details here as well.
We first show that, estimated subspace by algorithm does not have higher