\section{Introduction}
Data intrinsic dimensionality is a central object of study in compressed sensing, sketching, numerical linear algebra, machine learning, and many other domains~\cite{lin2017low,krauthgamer2003property,zhang2013counterexample,woodruff2014sketching,clarkson2013low,zhang2015relations,zhang2014robust}. In compressed sensing and sketching, the study of intrinsic dimensionality has led to significant advances in compressing the data to a size that is far smaller than the ambient dimension while still preserving useful properties of the signal~\cite{nakos2018improved,awasthi2016learning}. In numerical linear algebra and machine learning, understanding intrinsic dimensionality serves as a necessary condition for the success of various subspace recovery problems~\cite{hardt2013algorithms}, e.g., matrix completion~\cite{zhang2016completing,hardt2014understanding,jain2013low,sun2015guaranteed} and robust PCA~\cite{balcan2018matrix,zhang2015exact,bouwmans2018applications}. The focus of this work is on the intrinsic dimensionality of matrices, such as the rank, stable rank, Schatten-$p$ norms, and SVD entropy. The stable rank is defined to be the squared ratio of the Frobenius norm and the largest singular value, and the Schatten-$p$ norm is the $\ell_p$ norm of the singular values (see Appendix \ref{section: Entropy} for our definition of SVD entropy). We study these quantities in the framework of non-adaptive property testing~\cite{parnas2003testing,chan2014optimal,daskalakis2013testing}: given non-adaptive query access to the unknown matrix $\mathbf{A}\in\mathbb{F}^{n\times n}$ over a field $\mathbb{F}$, our goal is to determine whether $\mathbf{A}$ is of dimension $d$ (where dimension depends on the specific problem), or is $\epsilon$-far from having this property. The latter means that at least an $\epsilon$-fraction of entries of $\mathbf{A}$ should be modified in order to have dimension $d$. Query access typically comes in the form of reading a single entry of the matrix, though we will also discuss sensing models where a query returns the value $\langle\mathbf{X}_i,\mathbf{A}\rangle:= \tr(\mathbf{X}_i^\top\mathbf{A})$ for a given $\mathbf{X}_i$. Without making assumptions on $\mathbf{A}$, we would like to choose our sample pattern or set $\{\mathbf{X}_i\}$ of query matrices so that the query complexity is as small as possible.

Despite a large amount of work on testing matrix rank, many fundamental questions remain open. In the rank testing problem in the sampling model, one such question is to design an efficient algorithm that can distinguish rank-$d$ vs. $\epsilon$-far from rank-$d$ with optimal sample complexity.
The best-known sampling upper bound for non-adaptive rank testing for general $d$ is $\mathcal{O}(d^2/\epsilon^2)$, which is achieved simply by sampling an $\mathcal{O}(d/\epsilon)\times \mathcal{O}(d/\epsilon)$ submatrix uniformly at random~\cite{krauthgamer2003property}. For arbitrary fields $\mathbb{F}$, only an $\Omega((1/\epsilon)\log(1/\epsilon))$ lower bound for constant $d$ is known~\cite{li2014improved}. 

Besides the rank problem above, testing many numerical properties of real matrices has yet to be explored. For example, it is unknown what the query complexity is for the stable rank, which is a natural relaxation of rank in applications. Other examples for which previously we had no bounds are the Schatten-$p$ norms and SVD entropy. We discuss these problems in a new property testing framework that we call the \emph{bounded entry model}. This model has many realistic applications in the Netflix challenge~\cite{koren2009matrix}, where each entry of the matrix corresponds to the rating from a customer to a movie, ranging from 1 to 5. Understanding the query complexity of testing numerical properties in the bounded entry model is an important problem in recommendation systems and applications of matrix completion, where often entries are bounded. 


\comment{ 
There are some lower bounds that come from the sketching literature: for stable rank $d$ matrices, with fewer than $\mathcal{O}(d^2/\epsilon^2)$ non-adaptive samples, a $(1\pm\epsilon)$-approximation to the largest singular value is not possible \cite{li2016tight}. When no assumptions are made on the stable rank, there is an $\mathcal{O}(n^2/\alpha^4)$ upper bound for an $\alpha$-approximation to the largest singular value. Another line of research~\cite{kong2017spectrum,khetan2017spectrum} considers estimating  the Schatten-$p$ norm up to a constant factor, and when $p$ is as large as $\Theta(\log n/\epsilon)$, this estimator approximates the largest singular value to the desired $(1\pm\epsilon)$-factor accuracy. However, the sample complexity in those works is exponential in $p$.
}

\comment{
\medskip
\noindent{\textbf{Connections to Machine Learning.}}
We provide both positive and negative answers to the questions above. Our study is motivated by connections between property testing and machine learning~\cite{goldreich1998property,ron2008property}: property testing can determine inexpensively whether learning with a low-rank hypothesis class is worthwhile~\cite{balcan2012active}. Problems related to our model include matrix completion~\cite{balcan2016noise,zhang2016completing,balcan2018matrix,ge2016matrix,hardt2014computational} and robust PCA~\cite{zhang2015exact}, which have applications in recommendation system, video surveillance, etc~\cite{lin2017low}. In these problems, the data points are the column vectors of a matrix $\mathbf{A}=\L+\S$, where $\L$ is a low-rank matrix and $\S$ is only guaranteed to be a sparse matrix; note the entries in $\S$ may be arbitrarily large. Our result gives a near-optimal decision version of the robust PCA problem with a sample size independent of $n$: either $\mathbf{A}=\L$ for a rank-$d$ matrix $\L$, or if $\mathbf{A}=\L+\S$, then necessarily more than an $\epsilon$-fraction of entries of $\S$ are non-zero. Distinguishing the two cases helps detect, inexpensively, whether there is a rank-$d$ matrix that agrees with the observed entries which are corrupted with sparse noise~\cite{recht2011simpler,candes2011robust,pimentel2016converse,ashraphijuo2018deterministic}. In comparison, learning algorithms require $\Omega(nd\log n)$ samples for complete recovery of an underlying rank-$d$ matrix~\cite{candes2010power}. 

Our study of various numerical properties of matrices has applications to approximate matrix multiplication~\cite{cohen2015optimal}, random sparsification~\cite{tropp2015introduction}, column subset selection, matrix factorization, and eigenvalue optimization~\cite{tropp2009column,rudelson2007sampling}, since these measure the intrinsic dimensionality of matrices~\cite{tropp2015introduction}. A byproduct of our algorithms is a non-adaptive algorithm for estimating the largest singular value of an $n\times n$ matrix.
It is well-known that the power method is an efficient \emph{adaptive} algorithm for this problem. However, it typically requires an eigengap and needs to read all the entries of a matrix in order to compute a matrix-vector product. Other work has applied cycle-like estimators with sample complexity of $\mathsf{poly}(n)$~\cite{kong2017spectrum,khetan2017spectrum,li2014sketching}. In contrast, we provide the first \emph{non-adaptive} algorithm to estimate the largest singular value up to $(1\pm\epsilon)$ relative error with $\mathsf{poly}(d\log (n)/\epsilon)$ samples.}

\subsection{Problem Setup, Related Work, and Our Results}
\label{section: Problem Setup and Our Results}
Our work has two parts: (1)
we resolve the query complexity of non-adaptive matrix rank testing, a well-studied problem in this model, and (2) we develop a new framework for testing 
numerical properties of real matrices, including the stable rank, the Schatten-$p$ norms and the SVD entropy.
Our results are summarized in Table~\ref{table: result}. We use $\widetilde\mathcal{O}$ and $\widetilde\Omega$ notation to hide polylogarithmic factors in the arguments inside. For the rank testing results, the hidden polylogarithmic factors depend only on $d$ and $1/\epsilon$ and do not depend on $n$; for the other problems, they may depend on $n$.

\medskip
\noindent{\textbf{Rank Testing.}}
We first study the rank testing problem when we can only non-adaptively query entries. The goal is to design a sampling scheme on the entries of the unknown matrix $\mathbf{A}$ and an algorithm so that we can distinguish whether $\mathbf{A}$ is of rank $d$, or at least an $\epsilon$-fraction of entries of $\mathbf{A}$ should be modified in order to reduce the rank to $d$. This problem was first proposed by Krauthgamer and Sasson in~\cite{krauthgamer2003property} with a sample complexity upper bound of $\mathcal{O}(d^2/\epsilon^2)$. In this work, 
we improve this to $\widetilde{\mathcal{O}}(d^2/\epsilon)$ for every $d$ and $\epsilon$, and complement this with a matching lower bound, showing that any algorithm with constant success probability requires at least $\widetilde{\Omega}(d^2/\epsilon)$ samples:

\medskip
\noindent{\textbf{Theorems \ref{theorem: correctness of algorithm for general d}, \ref{theorem: lower bound of rank testing over finite fields under sampling model}, and \ref{theorem: lower bound of rank testing over reals}} (Informal)\textbf{.}}
\emph{For any matrix $\mathbf{A}\in\mathbb{F}^{n\times n}$ over any field, there is a randomized non-adaptive sampling algorithm which reads $\widetilde{\mathcal{O}}(d^2/\epsilon)$ entries and runs in $\mathsf{poly}(d/\epsilon)$ time, and with high probability correctly solves the rank testing problem. Further, any non-adaptive algorithm with constant success probability requires $\widetilde{\Omega}(d^2/\epsilon)$ samples over $\mathbb{R}$ or any finite field.}

\medskip
Our non-adaptive sample complexity bound of $\widetilde\mathcal{O}(d^2/\epsilon)$ matches what is known with adaptive queries~\cite{li2014improved}, and thus we show the best known upper bound might as well be non-adaptive.

\begin{table}[t]
\caption{Query complexity results in this paper for non-adaptive testing of the rank, stable rank, Schatten-$p$ norms, and SVD entropy. The testing of the stable rank, Schatten $p$-norm and SVD entropy are considered in the bounded entry model.}
\centering
\label{table: result}
{
\centering
\begin{tabular}{c||c|c|c|c}
\hline
Testing Problems & Rank & Stable Rank & Schatten-$p$ Norm & Entropy\\
 \hline\hline
\multirow{2}{1.5cm}{Sampling} & $\widetilde\mathcal{O}(d^2/\epsilon)$ (all fields) & $\widetilde\mathcal{O}(d^3/\epsilon^4)$ & & \multirow{4}{0.8cm}{$\Omega(n)$\textsuperscript{\textdagger}}\\
& $\widetilde\Omega(d^2/\epsilon)$ (finite fields and $\mathbb{R}$) & $\widetilde\Omega(d^2/\epsilon^2)$\textsuperscript{\textdagger} & $\widetilde\mathcal{O}(1/\epsilon^{4p/(p-2)})$ ($p>2$) & \\
\cline{1-3}
\multirow{2}{1.4cm}{Sensing} & $\mathcal{O}(d^2)$ (all fields) & $\widetilde{\mathcal{O}}(d^{2.5}/\epsilon^2)$ & $\Omega(n)$ ($p\in[1,2)$) & \\
& $\widetilde\Omega(d^2)$ (finite fields) & $\widetilde\Omega(d^2/\epsilon^2)$\textsuperscript{\textdagger} &  & \\
\hline
\end{tabular}
}

\rule{0in}{1.2em}{\footnotesize \textsuperscript{\textdagger} The lower bound involves a reparameterization of the testing problem. Please see the respective theorem for details.}
\end{table}

\medskip
\noindent{\textbf{New Framework for Testing Matrix Properties.}} Testing rank is only one of many tasks in determining if a matrix
has low intrinsic dimensionality. In several applications, we require a less fragile measure of the collinearity of rows and columns, which is known as the stable rank~\cite{tropp2015introduction}. We introduce what we call the \emph{bounded entry model} as a new framework for studying such problems through the lens of property testing. In this model, we require all entries of a matrix to be bounded by $1$ in absolute value. Boundedness has many natural applications in recommendation systems, e.g., the user-item matrix of preferences for products by customers has bounded entries in the Netflix challenge~\cite{koren2009matrix}. Indeed, there are many user rating matrices, etc., which naturally have a small
number of discrete values, and therefore fit into a bounded entry model. 
The boundedness of entries also avoids trivialities in which one can modify
a matrix to have 
a property by setting a single entry to be 
arbitrarily large, which, e.g., could make 
the stable rank arbitrarily close to $1$. 

Our model is a generalization of previous work in which stable rank testing
was done in a model for which all rows had to have bounded norm
\cite{li2014improved}, and the algorithm is only allowed to change entire
rows at a time. As our non-adaptive rank testing algorithm will illustrate,
one can sometimes do better by only reading certain carefully selected
entries in rows and columns. Indeed, this is precisely the source of our
improvement over prior work. Thus, the restriction of having to read an entire
row is often unnatural, and further motivates our bounded entry model.  
We first informally state our main theorems on stable rank testing in this model. 

\medskip
\noindent{\textbf{Theorem \ref{theorem: stable rank testing upper bound}} (Informal)\textbf{.}}
\emph{There is a randomized algorithm for the stable rank testing problem to decide whether a matrix is of stable rank at most $d$ or is $\epsilon$-far from stable rank at most $d$, with failure probability at most $1/3$, and which reads $\widetilde\mathcal{O}(d^3/\epsilon^4)$ entries.}

\medskip
Theorem \ref{theorem: stable rank testing upper bound} relies on a new $(1\pm\tau)$-approximate non-adaptive estimator of the largest singular value of a matrix, which may be of independent interest. 

\medskip
\noindent{\textbf{Theorem \ref{theorem: operator norm estimator by Ismail}} (Informal)\textbf{.}}
\emph{Suppose that $\mathbf{A}\in\mathbb{R}^{n\times n}$ has stable rank $\mathcal{O}(d)$ and $\|\mathbf{A}\|_F^2=\Omega(\tau n^2)$. Then in the bounded entry model, there is a randomized non-adaptive sampling algorithm which reads $\widetilde\mathcal{O}(d^2/\tau^4)$ entries and with probability at least $0.9$, outputs a $(1\pm\tau)$-approximation to the largest singular value of $\mathbf{A}$.}

\medskip
We remark that when the stable rank is constant and the singular value gap $\sigma_1(\mathbf{A})/\sigma_2(\mathbf{A}) = (1/\tau)^{\gamma}$ for an arbitrary constant $\gamma >0$, the operator norm can be estimated up to a $(1\pm\tau)$-factor by querying $\mathcal{O}(1/\tau^2)$ entries non-adaptively. We defer these and related results to Appendix \ref{section: Estimation with Eigengap}.

Other measures of intrinsic dimensionality include matrix norms, such as the Schatten-$p$ norm $\|\cdot\|_{\mathcal{S}_p}$, which measures the central tendency of the singular values. Familiar special cases are $p=1$, $2$ and $\infty$, which have applications in differential privacy~\cite{hardt2012simple} and non-convex optimization~\cite{balcan2018matrix,deshpande2011algorithms} for $p=1$, and in numerical linear algebra~\cite{mahoney2011randomized} for $p\in\{2,\infty\}$. Matrix norms have been studied extensively in the streaming literature \cite{li2014sketching,li2016approximating,li2016tight,LW17}, though their study in property testing models is lacking. 

We study non-adaptive algorithms for these problems in the bounded entry model. We consider distinguishing whether $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ is at least $cn^p$ for $p>2$ (at least $cn^{1+1/p}$ for $p<2$), or at least an $\epsilon$-fraction of entries of $\mathbf{A}$ should be modified in order to have this property, where $c$ is a constant (depending only on $p$). We choose the threshold $n^p$ for $p>2$ and $n^{1+1/p}$ for $p<2$ because they are the largest possible value of $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ for $\mathbf{A}$ under the bounded entry model. When $p>2$, $\|\mathbf{A}\|_{\mathcal{S}_p}$ is maximized when $\mathbf{A}$ is of rank $1$, and so this gives us an alternative ``measure'' of how close we are to a rank-$1$ matrix. Testing whether $\|\mathbf{A}\|_{\mathcal{S}_p}$ is large in sublinear time allows us to quickly determine whether $\mathbf{A}$ can be well approximated by a low-rank matrix, which could save us from running more expensive low-rank approximation algorithms. In contrast, when $p<2$, $\|\mathbf{A}\|_{\mathcal{S}_p}$ is maximized when $\mathbf{A}$ has a flat spectrum, and so is a measure of how well-conditioned $\mathbf{A}$ is. A fast tester could save us from running expensive pre-conditioning algorithms. We state our main theorems informally below.

\medskip
\noindent{\textbf{Theorem \ref{theorem: Schatten-p norm upper bound}} (Informal)\textbf{.}}
\emph{For constant $p>2$, there is a randomized algorithm for the Schatten-$p$ norm testing problem with failure probability at most $1/3$ which reads $\widetilde\mathcal{O}(1/\epsilon^{4p/(p-2)})$ entries.}



\medskip
\noindent{\textbf{Results for Sensing Algorithms.}}
We also consider a more powerful query oracle known as the \emph{sensing model}, where query access comes in the form of $\langle\mathbf{X}_i,\mathbf{A}\rangle := \tr(\mathbf{X}_i^\top\mathbf{A})$ for some sensing matrices $\mathbf{X}_i$ of our choice. 
These matrices are chosen non-adaptively.
We show differences in the complexity of the above problems in this and the above sampling model.  For the testing and the estimation problems above, we have the following results in the sensing model:

\medskip
\noindent{\textbf{Theorem \ref{theorem: lower bound over finite fields in general basis}} (Informal)\textbf{.}}
\emph{Over an arbitrary finite field, any non-adaptive algorithm with constant success probability for the rank testing problem in the sensing model requires $\widetilde\Omega(d^2)$ queries.}

\medskip
\noindent{\textbf{Theorems \ref{theorem: stable rank testing upper bound} and \ref{theorem: stable rank lower bound}} (Informal)\textbf{.}}
\emph{There is a randomized algorithm for the stable rank testing problem with failure probability at most $1/3$ in the sensing model with $\widetilde\mathcal{O}(d^{2.5}/\epsilon^2)$ queries. Further, any algorithm with constant success probability requires $\widetilde{\Omega}(d^2/\epsilon^2)$ queries.}

\medskip
\noindent{\textbf{Theorem \ref{thm:schatten_p_lb}} (Informal)\textbf{.}}
\emph{For $p\in[1,2)$, any algorithm for the Schatten-$p$ norm testing problem with failure probability at most $1/3$ requires $\Omega(n)$ queries.}

\medskip
\noindent{\textbf{Theorem \ref{theorem: operator norm estimator under sensing model}} (Informal)\textbf{.}}
\emph{Suppose that $\mathbf{A}\in\mathbb{R}^{n\times n}$ has stable rank $\mathcal{O}(d)$ and $\|\mathbf{A}\|_F^2=\Omega(\tau n^2)$. In the bounded entry model, there is a randomized sensing algorithm with sensing complexity $\widetilde\mathcal{O}(d^2/\tau^2)$ which outputs a $(1\pm\tau)$-approximation to the largest singular value with probability at least $0.9$. This sensing complexity is optimal up to polylogarithmic factors.}

\medskip
We also provide an $\Omega(n)$ query lower bound for the SVD entropy testing in the sensing model. We defer the definition of the problem and related results to Section~\ref{section: Entropy}.

\subsection{Our Techniques}
\label{section: Our Techniques}
We now discuss the techniques in more detail, starting with the rank testing problem. 

Prior to the work of \cite{li2014improved}, the only known algorithm for $d = 1$ was to sample an $\mathcal{O}(1/\epsilon)\times \mathcal{O}(1/\epsilon)$ submatrix. In contrast, for rank $1$ an algorithm in \cite{li2014improved} samples $\mathcal{O}(\log(1/\epsilon))$ blocks of varying shapes ``within a random $\mathcal{O}(1/\epsilon)\times \mathcal{O}(1/\epsilon)$ submatrix'' and argues that these shapes are sufficient to expose a rank-$2$ submatrix. For $d=1$ the goal is to augment a $1\times 1$ matrix to a full-rank $2\times 2$ matrix. One can show that with good probability, one of the shapes ``catches'' an entry that enlarges the $1\times 1$ matrix to a full-rank $2\times 2$ matrix. For instance, in Figure~\ref{figure: our sampling scheme}, $(r,c)$ is our $1\times 1$ matrix and the leftmost vertical block catches an ``augmentation element'' $(r',c')$ which makes $\left[\begin{smallmatrix} (r,c') & (r,c)\\ (r',c') & (r',c)\end{smallmatrix}\right]$ a full-rank $2\times 2$ matrix. Hereby, the ``augmentation element'' means the entry by adding which we augment a $r\times r$ matrix to a $(r+1)\times(r+1)$ matrix. In \cite{li2014improved}, an argument was claimed for $d = 1$, though we note an omission in their analysis. Namely, the ``augmentation entry'' $(r',c')$ can be the $1\times 1$ matrix we begin with (meaning that $\mathbf{A}_{r',c'}\neq 0$, which might not be true), and since one can show that both $(r,c)$ and $(r',c')$ fall inside the same sampling block with good probability, the $2\times 2$ matrix would be fully observed and the algorithm would thus be able to determine that it has rank $2$. However, it is possible that $\mathbf{A}_{r',c'} = 0$ and $(r',c')$ would not be a starting point (i.e., a $1\times 1$ rank-$1$ matrix), and in this case, $(r',c)$ may not be observed, as illustrated in Figure~\ref{figure: our sampling scheme}. In this case the algorithm will not be able to determine whether the augmented $2\times 2$ matrix is of full rank. For $d > 1$, nothing was known. One issue is that the probability of fully observing a $d\times d$ submatrix within these shapes is very small. To overcome this, we propose what we call \emph{rebasing} and \emph{transformation to a canonical structure}. These arguments allow us to tolerate unobserved entries and conveniently obtain an algorithm for every $d$, completing the analysis of \cite{li2014improved} for $d = 1$ in the process. 

\begin{figure}
\centering
\includegraphics[width=4.5cm]{caseii.pdf}
\caption{\small{Our sampling scheme (the region enclosed by the dotted lines modulo permutation of rows and columns) and our path of augmenting a $1\times 1$ submatrix. The whole region is the $\mathcal{O}(d/\epsilon)\times \mathcal{O}(d/\epsilon)$ submatrix sampled from the $n\times n$ matrix.}}
\label{figure: our sampling scheme}
\end{figure}

\medskip
\noindent{\textbf{Rebasing Argument + Canonical Structure.}} The best previous result for the rank testing problem uniformly samples an $\mathcal{O}(d/\epsilon)\times \mathcal{O}(d/\epsilon)$ submatrix and argues that one can find a $(d+1)\times (d+1)$ full-rank submatrix within it when $\mathbf{A}$ is $\epsilon$-far from rank-$d$~\cite{krauthgamer2003property}. In contrast, our algorithm follows from subsampling an $\mathcal{O}(\epsilon)$-fraction of entries in this $\mathcal{O}(d/\epsilon)\times \mathcal{O}(d/\epsilon)$ submatrix. Let $\mathcal{R}_1\subseteq \cdots \subseteq \mathcal{R}_m$ and $\mathcal{C}_1\supseteq \cdots \supseteq \mathcal{C}_m$ be the indices of subsampled rows and columns, respectively, with $m=\mathcal{O}(\log(1/\epsilon))$. We choose these indices uniformly at random such that $|\mathcal{R}_i|=\widetilde\mathcal{O}(d2^i)$ and $|\mathcal{C}_i|=\widetilde\mathcal{O}(d/(2^i\epsilon))$, and sample the entries in all $m$ blocks determined by the $\{\mathcal{R}_i,\mathcal{C}_i\}$ (see Figure~\ref{figure: our sampling scheme}, where our sampled regions are enclosed by the dotted lines). Since there are $\widetilde\mathcal{O}(\log(1/\epsilon))$ blocks and in each block we sample $\widetilde\mathcal{O}(d^2/\epsilon)$ entries, the sample complexity of our algorithm is as small as $\widetilde\mathcal{O}(d^2/\epsilon)$.

The correctness of our algorithm for $d=1$ follows from what we call a rebasing argument. Starting from an empty matrix, our goal is to maintain and augment the matrix to a $2\times 2$ full-rank matrix when $\mathbf{A}$ is $\epsilon$-far from rank-$d$. By a level-set argument, we show an oracle lemma which states that \emph{we can augment any $r\times r$ full-rank matrix to an $(r+1)\times (r+1)$ full-rank matrix by an augmentation entry in the sampled region}, as long as $r\le d$ and $\mathbf{A}$ is $\epsilon$-far from rank-$d$. Therefore, as a first step we successfully find a $1\times 1$ full-rank matrix, say with index $(r,c)$, in the sampled region. We then argue that we can either (a) find a $2\times 2$ fully-observed full-rank submatrix or a $2\times 2$ submatrix which is not fully observed but we know must be of full rank, or (b) move our maintained $1\times 1$ full-rank submatrix upwards or leftwards to a new $1\times 1$ \emph{full-rank} submatrix and repeat checking whether case (a) happens or not; if not, we implement case (b) again and repeat the procedure. To see case (a), by the oracle lemma, if the augmented entry is $(r'',c')$ (see Figure \ref{figure: our sampling scheme}), then we fully observe the submatrix determined by $(r'',c')$ and $(r,c)$ and so the algorithm is correct in this case. On the other hand, if the augmented entry is $(r',c')$, then we fail to see the entry at $(r',c)$. In this case, when $\mathbf{A}_{r,c'}= 0$, then we must have $\mathbf{A}_{r',c'}\neq 0$; otherwise, $(r',c')$ is not an augment of $(r,c)$, which leads to a contradiction with the oracle lemma. Thus we find a $2\times 2$ matrix with structure
\begin{equation}
\label{equ: structure for d=1}
\begin{bmatrix}
\mathbf{A}_{r,c'} & \mathbf{A}_{r,c}\\
\mathbf{A}_{r',c'} & \mathbf{A}_{r',c}
\end{bmatrix}
=
\begin{bmatrix}
0 & \neq 0\\
\neq 0 & ?
\end{bmatrix},
\end{equation}
which must be of rank $2$ despite an unobserved entry, and the algorithm therefore is correct in this case. The remaining case of the analysis above is when $\mathbf{A}_{r,c'}\neq 0$. Instead of trying to augment $\mathbf{A}_{r,c}$, we augment $\mathbf{A}_{r,c'}$ in the next step. Note that the index $(r,c')$ is to the left of $(r,c)$. This leads to case (b). In the worst case, we move the $1\times 1$ non-zero matrix to the uppermost left corner,\footnote{The upper-left corner refers to the intersection of all sampled blocks, namely, $\mathcal{R}_1\times \mathcal{C}_m$; it does not mean the top-left entry.} e.g., $(r'',c')$. Fortunately, since $(r'',c')$ is in the uppermost left corner, we can, as guaranteed by the oracle lemma, augment it to a $2\times 2$ \emph{fully-observed} full-rank matrix. Again the algorithm outputs correctly in this case.

The analysis becomes more challenging for general $d$, since the number of unobserved/unimportant entries (i.e., those entries marked as ``$?$'') may propagate as we augment an $r\times r$ submatrix ($r=1,2,...,d$) in each round. To resolve the issue, we maintain a structure (modulo elementary transformations) similar to structure \eqref{equ: structure for d=1} for the $r\times r$ submatrix, that is,
\begin{equation}
\label{equ: structure for general d}
\begin{bmatrix}
0 & 0 & \cdots & 0 & \cdots & 0 & \ne 0\\
0 & 0 & \cdots & 0 & \cdots & \ne 0 & ?\\
\vdots & \vdots &  & \vdots &  & \vdots & \vdots\\
0 & \ne 0 & \cdots & ? & \cdots & ? & ?\\
\ne 0 & ? & \cdots & ? & \cdots & ? & ?\\
\end{bmatrix}.
\end{equation}
Since the proposed structure has non-zero determinant, the submatrix is always of full rank. Similar to the case for $d=1$, we show that we can either (a) augment the $r\times r$ submatrix to an $(r+1)\times (r+1)$ submatrix with the same structure \eqref{equ: structure for general d} (modulo elementary transformations); or (b) find another $r\times r$ submatrix of structure \eqref{equ: structure for general d} that is closer to the upper-left corner than the original $r\times r$ matrix. Hence the algorithm is correct for general $d$. More details are provided in the proof of Theorem \ref{theorem: correctness of algorithm for general d}.

\medskip
\noindent{\textbf{Pivot-Node Assignment.}} Our rank testing lower bound under the sampling model over a finite field $\mathbb{F}$ follows from distinguishing two hard instances $\mathbf{U}\mathbf{V}^\top$ vs. $\mathbf{W}$, where $\mathbf{U},\mathbf{V}\in\mathbb{F}^{t\times d}$ and $\mathbf{W}\in\mathbb{F}^{t\times t}$ have i.i.d.\ entries that are uniform over $\mathbb{F}$. For an observed subset $\mathcal{S}$ of entries with $|\mathcal{S}|=\mathcal{O}(d^2)$, we bound the total variation distance between the distributions of the observed entries in the two cases by a small constant. In particular, we show that the probability $\Pr[(\mathbf{U}\mathbf{V}^\top)|_{\mathcal{S}}=\mathbf{x}]$ is large for any observation $\mathbf{x}\in\mathbb{F}^{|\mathcal{S}|}$, by a \emph{pivot-node assignment} argument, as follows. We reformulate our problem as a bipartite graph assignment problem $G=(L\cup R,E)$, where $L$ corresponds to the rows of $\mathbf{U}$, $R$ the rows of $\mathbf{V}$ and each edge of $E$ one entry in $\mathcal{S}$. We want to assign each node a vector/affine subspace, meaning that the corresponding row in $\mathbf{U}$ or $\mathbf{V}$ will be that vector or in that affine subspace, such that they agree with our observation, i.e., $(\mathbf{U}\mathbf{V}^\top)|_{\mathcal{S}}=\mathbf{x}$. Since $\mathbf{U},\mathbf{V}$ are random matrices, we assign random vectors to nodes adaptively, one at a time, and try to maintain consistency with the fact that $(\mathbf{U}\mathbf{V}^\top)|_{\mathcal{S}} = \mathbf{x}$. Note that the order of the assignment is important, as a bad choice for an earlier node may invalidate any assignment to a later node. To overcome this issue, we choose nodes of large degrees as \emph{pivot nodes} and assign each non-pivot node adaptively in a careful manner so as to guarantee that the incident pivot nodes will always have valid assignments (which in fact form an affine subspace). In the end we assign the pivot node vectors from their respective affine subspaces. We employ a counting argument for each step in this assignment procedure to lower bound the number of valid assignments, and thus lower bound the probability $\Pr[(\mathbf{U}\mathbf{V}^\top)|_{\mathcal{S}}=\mathbf{x}]$.

The above analysis gives us an $\Omega(d^2)$ lower bound for constant $\epsilon$ since $\mathbf{W}$ is constant-far from being of rank $d$. The desired $\Omega(d^2/\epsilon)$ lower bound follows from planting $\mathbf{U}\mathbf{V}^\top$ vs. $\mathbf{W}$ with $t=\sqrt{\epsilon}n$ into an $n\times n$ matrix at uniformly random positions, and padding zeros everywhere else.


\medskip
\noindent{\textbf{New Analytical Framework for Stable Rank, Schatten-$p$ Norm, and Entropy Testing.}} We propose a new analytical framework by reducing the testing problem to a sequence of estimation problems \emph{without involving $\mathsf{poly}(n)$ in the sample complexity}. There is a two-stage estimation in our framework: (1) a constant-approximation to some statistic $X$ of interest (e.g., stable rank) which enables us to distinguish $X\le d$ vs. $X\ge 10d$ for the threshold parameter $d$ of interest. If $X\ge 10d$, we can safely output ``$\mathbf{A}$ is far from $X\le d$''; otherwise, the statistic is at most $10d$, and (2) we show that $X$ has a $(1\pm\epsilon)$-factor difference between ``$X\leq d$'' and ``far from $X\leq d$'', and so we implement a more accurate $(1\pm\epsilon)$-approximation to distinguish the two cases. The sample complexity does not depend on $n$ polynomially because (1) the first estimator is ``rough'' and gives only a constant-factor approximation and (2) the second estimator operates under the condition that $X\leq 10d$ and thus $\mathbf{A}$ has a low intrinsic dimension. We apply the proposed framework to the testing problems of the stable rank and the Schatten-$p$ norm by plugging in our estimators in Theorem~\ref{theorem: operator norm estimator by Ismail} and Theorem~\ref{theorem: operator norm estimator under sensing model}. This analytical framework may be of independent interest to other property testing problems more broadly.

In a number of these problems, a key difficulty is arguing about spectral
properties 
of a matrix $\mathbf{A}$
when it is $\epsilon$-far from having a property, such as having
stable rank at most $d$. 
Because of the fact that
the entries must always be bounded by $1$ in absolute value, it becomes non-trivial
to argue, for example, that if $\mathbf{A}$ is $\epsilon$-far from having stable
rank at most $d$, that its stable rank is even slightly larger than $d$. A natural
approach is to argue that you could change an $\epsilon$-fraction of rows 
of $\mathbf{A}$ to agree with a multiple of the
top left or right singular vector of $\mathbf{A}$, and since we are
still guaranteed to have stable rank at least $d$ after changing such entries, 
it means that the operator
norm of $\mathbf{A}$ must have been small to begin with (which says something about the
original stable rank of $\mathbf{A}$, since its Frobenius norm can also be estimated).
The trouble is, if the top singular vector has some entries that are very large,
and others that are small, one cannot scale the singular vector by a large
amount since then we would violate the boundedness criterion of our model. We
get around this by arguing there either needs to exist a left or a right singular
vector of large $\ell_1$-norm (in some cases such vectors may only be right
singular vectors, and in other cases only left singular vectors). The $\ell_1$-norm
is a natural norm to study in this context, since it is dual to the $\ell_{\infty}$-norm, which we use to capture the boundedness property of the matrix. 

Our lower bounds for the above problems follow from the corresponding sketching lower bounds for the estimation problem in \cite{li2016tight,LNW:schatten_unpublished}, together with rigidity-type results \cite{valiant1977graph} for the hard instances regarding the respective statistic of interest.



\section{Preliminaries}
We shall use bold capital letters $\mathbf{A}$, $\mathbf{B}$, ... to indicate matrices, bold lower-case letters $\u$, $\v$, ... to indicate vectors, and lower-case letters $a$, $b$, ... to indicate scalars. We adopt the convention of abbreviating the set $\{1,2,...,n\}$ as $[n]$. We write $f\gtrsim g$ (resp. $f\lesssim g$) if there exists a constant $C>0$ such that $f\ge Cg$ (resp. $f\le Cg$).

For matrix functions, denote by $\mathsf{rank}(\mathbf{A})$ and $\mathsf{srank}(\mathbf{A})$ the rank and the stable rank of $\mathbf{A}\neq\mathbf{0}$, respectively. It always holds that $1\le \mathsf{srank}(\mathbf{A})\le \mathsf{rank}(\mathbf{A})$. For matrix norms, let $\|\mathbf{A}\|_{\mathcal{S}_p}$ denote the Schatten-$p$ norm of $\mathbf{A}$, defined as $\|\mathbf{A}\|_{\mathcal{S}_p}=\left(\sum_{i=1}^n \sigma_i^p(\mathbf{A})\right)^{1/p}$. The Frobenius norm $\|\mathbf{A}\|_F$ is a special case of the Schatten-$p$ norm when $p=2$, the operator norm or the spectral norm (the largest singular value) of $\|\mathbf{A}\|$ equals to the limit as $p\rightarrow +\infty$. When $0 <p<1$, $\|\mathbf{A}\|_{\mathcal{S}_p}$ is not a norm but is still a well-defined quantity, and it tends to $\mathsf{rank}(\mathbf{A})$ as $p\to 0^+$.  Let $\|\mathbf{A}\|_0$ denote the number of non-zero entries in $\mathbf{A}$, and $\|\mathbf{A}\|_\infty$ denote the entrywise $\ell_\infty$ norm of $\mathbf{A}$, i.e., $\|\mathbf{A}\|_\infty = \max_{i,j} |\mathbf{A}_{i,j}|$.
The \emph{rigidity} of a matrix $\mathbf{A}$ over a field $\mathbb{F}$, denoted by $\mathcal{R}_{\mathbf{A}}^{\mathbb{F}}(r)$, is the least number of entries of $\mathbf{A}$ that must be changed in order to reduce the rank of $\mathbf{A}$ to a value at most $r$:
\begin{equation*}
\mathcal{R}_{\mathbf{A}}^{\mathbb{F}}(r):=\min\{\|\mathbf{C}\|_0:\mathsf{rank}_{\mathbb{F}}(\mathbf{A}+\mathbf{C})\le r\}.
\end{equation*}
Sometimes we may omit the subscript $\mathbf{A}$ in $\mathcal{R}_{\mathbf{A}}^{\mathbb{F}}(r)$ when the matrix of interest is clear from the context.


We define the entropy of an unnormalized distribution $(p_1,\dots,p_n)$ ($ 0 <p_1+\cdots+p_n\leq 1$ with $p_i \geq 0$ for all $i$) to be
\[
H(p_1,\dots,p_n) = -\sum_i p_i\log p_i.
\]
Let $\mathbf{A}\in \mathbb{R}^{n\times n}$, we define its entropy as
\begin{equation}\label{eqn:entropy_defn}
H(\mathbf{A}) = H\left(\frac{\sigma_1^2(\mathbf{A})}{n^2},\dots,\frac{\sigma_n^2(\mathbf{A})}{n^2}\right) = \frac{-\sum_i \frac{\sigma_i^2(\mathbf{A})}{n^2}\log\frac{\sigma_i^2(\mathbf{A})}{n^2}}{\sum_i \frac{\sigma_i^2(\mathbf{A})}{n^2}}.
\end{equation}
with the convention that $0\cdot\infty = 0$. For matrices $\mathbf{A}$ satisfying $\|\mathbf{A}\|_\infty\leq 1$, it holds that $\sigma_i(\mathbf{A})\leq n$ for all $i$ and the entropy above coincides with the usual Shannon entropy. Note that scaling only changes the entropy additively; that is, $H(\beta\mathbf{A}) = H(\mathbf{A}) - \log\beta^2$.

Let $\mathcal{G}(m,n)$ denote the distribution of $m\times n$ i.i.d. standard Gaussian matrix over $\mathbb{R}$ and $\mathcal{U}_{\mathbb{F}}(m,n)$ (or $\mathcal{U}(\mathcal{S})$) represent $m\times n$ i.i.d. uniform matrix over a finite field $\mathbb{F}$ (or a finite set $\mathcal{S}$). We use $d_{TV}(\mathcal{L}_1,\mathcal{L}_2)$ to denote the total variation distance between two distributions $\mathcal{L}_1$ and $\mathcal{L}_2$.

We shall also frequently use $c$, $c'$, $c_0$, $C$, $C'$, $C_0$, etc., to represent constants, which are understood to be absolute constants unless the dependency is otherwise specified.







\section{Non-Adaptive Rank Testing}
In this section, we study the following problem of testing low-rank matrices.
\begin{problem}[Rank Testing with Parameter $(n,d,\epsilon)$ in the Sampling Model]
\label{problem: problem of property testing of rank}
Given a field $\mathbb{F}$ and a matrix $\mathbf{A}\in\mathbb{F}^{n\times n}$ which has one of promised properties:
\begin{itemize}
\item[$\mathsf{H0.}$]
$\mathbf{A}$ has rank at most $d$;
\item[$\mathsf{H1.}$]
$\mathbf{A}$ is $\epsilon$-far from having rank at most $d$, meaning that $\mathbf{A}$ requires changing at least an $\epsilon$-fraction of its entries to have rank at most $d$.
\end{itemize}
The problem is to design a property testing algorithm that outputs $\mathsf{H0}$ with probability $1$ if $\mathbf{A}\in \mathsf{H0}$, and output $\mathsf{H1}$ with probability at least 0.99 if $\mathbf{A}\in\mathsf{H1}$, with the least number of queried entries.
\end{problem}

\subsection{Positive Results}
\label{section: positive results}
Below we provide a non-adaptive algorithm for the rank testing problem under the sampling model with $\widetilde\mathcal{O}(\frac{d^2}{\epsilon})$ queries when $\epsilon\le\frac{1}{e}$. Let $\eta\in(0,\frac12)$ be such that $\eta\log(\frac{1}{\eta})=\epsilon$ and let $m = \lceil\log (\frac{1}{\eta})\rceil$.
\begin{algorithm}[ht]
\caption{Robust non-adaptive testing of matrix rank}
\label{algorithm: non-adaptive robust testing of rank}
\begin{algorithmic}[1]
\State Choose $\mathcal{R}_1,\dots,\mathcal{R}_m$ and $\mathcal{C}_1,\dots,\mathcal{C}_m$ from $[n]$ uniformly at random such that
\begin{equation*}
\mathcal{R}_1\subseteq \cdots \subseteq \mathcal{R}_m,\qquad \mathcal{C}_1\supseteq \cdots \supseteq \mathcal{C}_m,
\end{equation*}
and
\begin{equation*}
|\mathcal{R}_i|=c[\log d+\log\log(1/\eta)]d\log(1/\eta)2^i,\qquad |\mathcal{C}_i|=c[\log d+\log\log(1/\eta)]d\log (1/\eta)/(2^i\eta),
\end{equation*}
where $c>0$ is an absolute constant. To impose containment for $\mathcal{R}_i$'s, $\mathcal{R}_i$ can be formed by appending to $\mathcal{R}_{i-1}$ uniformly random $|\mathcal{R}_i|-|\mathcal{R}_{i-1}|$ rows. The containment for $\mathcal{C}_i$'s can be imposed similarly.

\State  Query the entries in $\mathcal{Q}=\bigcup_{i=1}^m (\mathcal{R}_i\times \mathcal{C}_i)$. Note that the entries in $(\mathcal{R}_m\times \mathcal{C}_1)\setminus \mathcal{Q}$ are unobserved. The algorithm solves the following minimization problem by filling in those entries of $\mathbf{A}_{(\mathcal{R}_m\times \mathcal{C}_1)\setminus\mathcal{Q}}$ given input $\mathbf{A}_{\mathcal{Q}}$.
\begin{equation}
\label{equ: upper bound}
r:=\min_{\mathbf{A}_{(\mathcal{R}_m\times \mathcal{C}_1)\setminus \mathcal{Q}}} \mathsf{rank}(\mathbf{A}_{\mathcal{R}_m,\mathcal{C}_1}).
\end{equation}
\State Output ``$\mathbf{A}$ is $\epsilon$-far from having rank $d$'' if $r>d$; otherwise, output ``$\mathbf{A}$ is of rank at most $d$''.
\end{algorithmic}
\end{algorithm}

We note that the number of entries that Algorithm \ref{algorithm: non-adaptive robust testing of rank} queries is
$$\mathcal{O}(k\cdot [\log d+\log\log(1/\eta)]^2d^2\log^2(1/\eta)/\eta)=\widetilde\mathcal{O}(d^2/\epsilon).$$
We now prove the correctness of Algorithm \ref{algorithm: non-adaptive robust testing of rank}. Before proceeding, we reproduce the definitions \emph{augment set} and \emph{augment pattern $i$} and relevant lemmata from~\cite{li2014improved} as follows.

\begin{definition}[Augment]
For $n\times n$ fixed matrix $\mathbf{A}$, we call $(r,c)$ an augment for $\mathcal{R}\times \mathcal{C}\subseteq [n]\times [n]$ if $r\in[n]\backslash \mathcal{R}$, $c\in[n]\backslash \mathcal{C}$ and $\mathsf{rank}(\mathbf{A}_{\mathcal{R}\cup\{r\},\mathcal{C}\cup\{c\}})>\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})$. We denote by $\mathsf{aug}(\mathcal{R},\mathcal{C})$ the set of all the augments for $\mathcal{R}\times \mathcal{C}$, namely,
\begin{equation*}
\mathsf{aug}(\mathcal{R},\mathcal{C})=\{(r,c)\in([n]\backslash \mathcal{R})\times ([n]\backslash \mathcal{C})\mid \mathsf{rank}(\mathbf{A}_{\mathcal{R}\cup\{r\},\mathcal{C}\cup\{c\}})>\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})\}.
\end{equation*}
\end{definition}

\begin{definition}[Augment Pattern]
For fixed $\mathcal{R}$, $\mathcal{C}$ and $\mathbf{A}$, define $\mathsf{count}_r$ (where $r\in[n]\backslash \mathcal{R}$) to be the number of $c$'s such that $(r,c)\in \mathsf{aug}(\mathcal{R},\mathcal{C})$. Let $\{\mathsf{count}^\ast_i\}_{i\in [n-|\mathcal{R}|]}$ the non-increasing reordering of the sequence $\{\mathsf{count}_i\}_{i\in [n]\backslash \mathcal{R}}$, and $\mathsf{count}_{i}^\ast=0$ for $i>n-|\mathcal{R}|$. We say that $(\mathcal{R},\mathcal{C})$ has augment pattern $i$ on $\mathbf{A}$ if and only if $\mathsf{count}_{n/2^i}^\ast\ge 2^{i-1}\eta n$.
\end{definition}


\begin{lemma
\label{lemma: augment}
Let $\mathbf{A}_{\mathcal{R},\mathcal{C}}$ be a $t\times t$ full-rank matrix. If $\mathbf{A}$ is $\epsilon$-far from having rank $d$ and $\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})=t\le d$, then
\begin{equation*}
|\mathsf{aug}(\mathcal{R},\mathcal{C})|=\sum_{r\in[n]\backslash \mathcal{R}} \mathsf{count}_r=\sum_{i=1}^{n-|\mathcal{R}|}\mathsf{count}_i^*\ge \frac{\epsilon n^2}{3}.
\end{equation*}
\end{lemma}

\begin{proof}
Let $\mathcal{S}$ be the set of entries $(r,c)$ in $\mathcal{R}^c\times \mathcal{C}^c$ such that $\mathsf{rank}(\mathbf{A}_{\mathcal{R}\cup \{r\},\mathcal{C}\cup \{c\}})>\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})$, i.e., $\mathcal{S}=\mathsf{aug}(\mathcal{R},\mathcal{C})$. We will show that $|\mathcal{S}|\ge \epsilon n^2/3$.

Let $\mathcal{T}$ be the complement of $\mathcal{S}$ inside the set $\mathcal{R}^c\times \mathcal{C}^c$. For any $(r,c)\in\mathcal{S}$, we discuss the following two cases.

\medskip
\noindent{\textbf{Case (i). There is $c'\in \mathcal{C}^c$ such that $(r,c')\in \mathcal{T}$ or $r'\in \mathcal{R}^c$ such that $(r',c)\in \mathcal{T}$}}

In the former case, the row vector $\mathbf{A}_{r,\mathcal{C}\cup\{c'\}}$ is a linear combination of the rows of $\mathbf{A}_{\mathcal{R},\mathcal{C}\cup\{c'\}}$. So we can change the value of $\mathbf{A}_{r,c}$ so that $\mathbf{A}_{r,\mathcal{C}\cup\{c\}}$ is a linear combination of $\mathbf{A}_{\mathcal{R},\mathcal{C}\cup\{c\}}$ with the same representation coefficients as that of $\mathbf{A}_{\mathcal{R},\mathcal{C}\cup\{c'\}}$. Therefore, augmenting $\mathbf{A}_{R,C}$ by the pair $(r,c)$ would not increase $\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})$. Similarly, if there is $r'\in \mathcal{R}^c$ such that $(r',c)\in T$, we can change the value of $\mathbf{A}_{r,c}$ so that augmenting $\mathbf{A}_{\mathcal{R},\mathcal{C}}$ by the pair $(r,c)$ would not increase $\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})$. We change at most $|\mathcal{S}|$ entries for both cases combined.

\medskip
\noindent{\textbf{Case (ii). $(r,c')\in \mathcal{S}$ for all $c'\in \mathcal{C}^c$ and $(r',c)\in \mathcal{S}$ for all $r'\in \mathcal{R}^c$}}

In this case, we can change the entire $r$-th row and $c$-th column of $\mathbf{A}$ so that $\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})$ does not increase by augmenting it with any pair in $(\mathcal{R}^c\times \{c\})\cup(\{r\}\times \mathcal{C}^c)$. Recall that $n\ge 2d$ and $t\le d$. It follows that $n\le 2(n-t)$. Therefore, this specific pair $(r,c)$ would lead to the change of at most $2n\le 2(n-t)+2(n-t)\le 2(|\mathcal{R}^c|+|\mathcal{C}^c|)$ entries. For all such $(r,c)$'s, we change at most $2|\mathcal{S}|$ entries in this case.

In summary, we can change at most $3|\mathcal{S}|$ entries of $\mathbf{A}$ so that $\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})$ cannot increase by augmenting $\mathbf{A}_{\mathcal{R},\mathcal{C}}$ with any pair $(r,c)\in \mathcal{R}^c\times \mathcal{C}^c$. Since $\mathbf{A}$ is $\epsilon$-far from being rank $d$, we must have $3|\mathcal{S}|\ge \epsilon n^2$. Namely, $|\mathsf{aug}(\mathcal{R},\mathcal{C})|=|\mathcal{S}|\ge \epsilon n^2/3$.
\end{proof}


\begin{lemma
\label{lemma: existence of augment pattern}
Let $\mathbf{A}_{\mathcal{R},\mathcal{C}}$ be a $t\times t$ full-rank matrix. If $\mathbf{A}$ is $\epsilon$-far from being rank $d$ and $\mathsf{rank}(\mathbf{A}_{\mathcal{R},\mathcal{C}})=t\le d$, then there exists $i$ such that $(\mathcal{R},\mathcal{C})$ has augment pattern $i$.
\end{lemma}

\begin{proof}
Suppose that $(\mathcal{R},\mathcal{C})$ does not have any augment pattern in $[\log(1/\eta)]$. That is
\begin{equation*}
\mathsf{count}_{n/2^i}^\ast<2^{i-1}\eta n,\quad i=1,2,...,\log(1/\eta).
\end{equation*}
Therefore,
\begin{equation*}
\begin{split}
\sum_i \mathsf{count}_i^*&=\sum_{i=\frac{n}{2}+1}^n \mathsf{count}_i^*+\sum_{i=\frac{n}{4}+1}^{\frac{n}{2}} \mathsf{count}_i^*+...+\sum_{i=\frac{n}{2^{\log(1/\eta)}}+1}^{\frac{n}{2^{\log(1/\eta)-1}}}\mathsf{count}_i^*+\sum_{i=1}^{\eta n}\mathsf{count}_i^*\\
&\le \frac{n}{2}\mathsf{count}_{\frac{n}{2}+1}^\ast+\frac{n}{4}\mathsf{count}_{\frac{n}{4}+1}^\ast+\cdots+\frac{n}{2^{\log(1/\eta)}}\mathsf{count}_{\frac{n}{2^{\log(1/\eta)}}+1}^\ast+\eta n\mathsf{count}_{1}^\ast\\
&< \frac{n}{2}\eta n+\frac{n}{4}2\eta n+...+\eta n2^{\log(1/\eta)-1}\eta n+\eta n^2\\
&=\frac{\eta n^2}{2}(\log(1/\eta)+2)\\
&\le \frac{\epsilon n^2}{3},
\end{split}
\end{equation*}
which leads to a contradiction with Lemma \ref{lemma: augment}.
\end{proof}

\begin{lemma
\label{lemma: uniform sampling captures augment pattern}
For fixed $(\mathcal{R},\mathcal{C})$, suppose that $(\mathcal{R},\mathcal{C})$ has augment pattern $i$ on $\mathbf{A}$. Let $\mathcal{R}',\mathcal{C}'\subseteq [n]$ be uniformly random such that $|\mathcal{R}'|=c2^i$, $|\mathcal{C}'|=c/(2^i\eta)$. Then the probability that $(\mathcal{R}',\mathcal{C}')$ contains at least one augment of $(\mathcal{R},\mathcal{C})$ on $\mathbf{A}$ is at least $1-2e^{-c/2}$.
\end{lemma}

\begin{proof}
Since $(\mathcal{R},\mathcal{C})$ has augment pattern $i$ on matrix $\mathbf{A}$, the probability that $\mathcal{R}'$ (and $\mathcal{C}'$) does not hit row (and column) of any augment is $(1-2^{-i})^{c2^i}$ (and $(1-2^{i-1}\eta)^{c/(2^i\eta)}$). Therefore, the probability that $(\mathcal{R}',\mathcal{C}')$ hits at least one augment is given by
\[
\left(1-(1-2^{-i})^{c2^i}\right)\left(1-(1-2^{i-1}\eta)^{c/(2^i\eta)}\right)\ge 1-\frac{2}{e^{c/2}}.\qedhere
\]
\end{proof}


\subsubsection{Warm-Up: The Case of $d=1$}

Without loss of generality, we may permute the rows and columns of $\mathbf{A}$ and assume that $\mathcal{R}_i = \{1,\dots,|\mathcal{R}_i|\}$ and $\mathcal{C}_i = \{1,\dots,|\mathcal{C}_i|\}$ for all $i\leq \lceil\log\frac{1}{\eta}\rceil$.

\begin{theorem}
\label{theorem: correctness of algorithm for d=1}
Let $\epsilon\le 1/e$ and $d=1$. For any matrix $\mathbf{A}$, the probability that Algorithm \ref{algorithm: non-adaptive robust testing of rank} fails is at most $1/3$.
\end{theorem}

\begin{proof}
If $\mathbf{A}$ is of rank at most $d$, then the algorithm will never make mistake; so we assume that $\mathbf{A}$ is $\epsilon$-far from being rank $d$ in the proof below.

Lemma~\ref{lemma: existence of augment pattern} shows that $(\emptyset,\emptyset)$ has some augment pattern $s$ and by Lemma~\ref{lemma: uniform sampling captures augment pattern}, with probability at least $1-2e^{-c/2}$ there exists $(r,c)\in (\mathcal{R}_s,\mathcal{C}_s)$ such that $(r,c)\in \textsf{aug}(\emptyset,\emptyset)$, i.e., $\mathbf{A}_{(r,c)}\ne 0$. We now argue that the rank-$1$ submatrix $\mathbf{A}_{(r,c)}$ can be augmented to a rank-$2$ submatrix.

Again by Lemma~\ref{lemma: existence of augment pattern}, $(\{r\},\{c\})$ has an augment pattern $j$; otherwise, $\mathbf{A}$ is not $\epsilon$-far from being rank-$d$, and with probability at least $1-2e^{-c/2}$ there exists $(r',c')\in (\mathcal{R}_j,\mathcal{C}_j)$ such that $(r',c')\in \textsf{aug}(\{r\},\{c\})$. We now discuss three cases based on the position of $(r',c')$ in relation to $(r,c)$.

\medskip
\noindent{\textbf{Case (i). $(r',c')\in R_s\times C_s$.}}

By Lemma \ref{lemma: uniform sampling captures augment pattern}, with probability at least $1-2e^{-c/2}$, $\mathcal{R}_j\times \mathcal{C}_j$ contains an argument for $({r},{c})$, denoted by $(r',c')$. By construction of $\{\mathcal{R}_j\}$ and $\{\mathcal{C}_j\}$, $(r,c')$ and $(r',c)$ are also queried (See Figure \ref{figure: case i}). Thus we find a $2\times 2$ non-singular matrix. The algorithm answers correctly with probability at least $1-4e^{-c_0/4}>2/3$ in this case.


\medskip
\noindent{\textbf{Case (ii). $r'\not\in \mathcal{R}_s$ or $c'\not\in \mathcal{C}_s$.}}

In this case, we show that starting from $\mathbf{A}_{r,c}$, we can always find a path for the non-singular $1\times 1$ submatrix $\mathbf{A}_{*,*}$ such that the index $(*,*)$ always moves to the left or above, so we make progress towards case (i): we note that the non-zero element in the most upper left corner can always be augmented with three queried elements in the same augment pattern (i.e., Case (i)), because the uppermost left corner belongs to all $(\mathcal{R}_i,\mathcal{C}_i)$'s by construction. We now show how to find the path (Please refer to Figure \ref{figure: case ii} for the following proofs).
\begin{figure}
\centering
\subfigure[Case (i).]{
\includegraphics{casei.pdf}
\label{figure: case i}
}
\subfigure[Case (ii).]{
\includegraphics{caseii.pdf}
\label{figure: case ii}
}
\caption{Finding an augmentation path $(d=1)$, where the whole region is the $\mathcal{O}(d/\epsilon)\times \mathcal{O}(d/\epsilon)$ submatrix uniformly sampled from the original $n\times n$ matrix.}
\end{figure}

For index $(r,c)$ such that $\mathbf{A}_{r,c}\ne 0$, if $r'\not\in \mathcal{R}_s$ or $c'\not\in \mathcal{C}_s$ (say $r'\not\in\mathcal{R}_s$ at the moment), then by Lemma \ref{lemma: uniform sampling captures augment pattern}, there exists an index $(r',c')\in (\mathcal{R}_j,\mathcal{C}_j)$ such that $(r,c)$ can be augmented by $(r',c')$. However, we cannot observe $\mathbf{A}_{r',c}$ so we do not find a $2\times 2$ submatrix at the moment. To make progress, we further discuss two cases.

\medskip
\noindent{\textbf{Case (ii.1). $\mathbf{A}_{r,c'}=0$ and $\mathbf{A}_{r',c'}=0$.}}

This case is impossible; otherwise, $(r',c')$ cannot be an augment of $(r,c)$.

\medskip
\noindent{\textbf{Case (ii.2). $\mathbf{A}_{r,c'}=0$ and $\mathbf{A}_{r',c'}\neq 0$.}}

Since $\mathbf{A}_{r,c}\ne 0$, $\mathbf{A}_{r',c'}\ne 0$ and $\mathbf{A}_{r,c'}=0$, no matter what $\mathbf{A}_{r,c'}$ is, the $2\times 2$ submatrix
\begin{equation*}
\begin{bmatrix}
\mathbf{A}_{r,c'} & \mathbf{A}_{r,c}\\
\mathbf{A}_{r',c'} & \mathbf{A}_{r',c}
\end{bmatrix}
=
\begin{bmatrix}
0 & \ne 0\\
\ne 0 & ?
\end{bmatrix}
\end{equation*}
is always non-singular (Denote by $?$ the entry which can be observed or unobserved, meaning that the specific value of the entry is unimportant for our purpose). So the algorithm answers correctly with probability at least $1-4e^{-c_0/4}>2/3$.


\medskip
\noindent{\textbf{Case (ii.3). $\mathbf{A}_{r,c'}\neq 0$.}}
Instead of augmenting $(r,c)$, we shall pick $(r, c')$ to be our new base entry ($1\times 1$ matrix) and try to augment it to a $2\times 2$ matrix. In this way, we have moved our base $1\times 1$ matrix towards the upper-left corner. We can repeat the preceding arguments of different cases.

If Case (i) happens for $(r,c')$, we immediately have a $2\times 2$ rank-$2$ submatrix and the algorithm answers correctly with a good probability. If Case (i) does not happen, we shall demonstrate that we can make further progress. Suppose that $(r'',c'')$ is an augment of $(\{r\},\{c'\})$ and $c''\not\in \mathcal{C}_s\cup \mathcal{C}_j$. We intend to look at the submatrix
\[
\begin{bmatrix}
\mathbf{A}_{r'',c'} & \mathbf{A}_{r'',c''}\\
\mathbf{A}_{r,c'} & \mathbf{A}_{r,c''}
\end{bmatrix}
\]
Here we cannot observe $\mathbf{A}_{r,c''}$. We know that $\mathbf{A}_{r'',c'}$ and $\mathbf{A}_{r'',c''}$ cannot be both $0$, otherwise $(r'',c'')$ would not be an augment for $(r,c')$. If $\mathbf{A}_{r'',c'} = 0$ and $\mathbf{A}_{r'',c''}\neq 0$, this $2\times 2$ matrix is nonsingular regardless of the value of $\mathbf{A}_{r,c''}$ and the algorithm will answer correctly. If $\mathbf{A}_{r'',c'} \neq 0$, we can rebase our $1\times 1$ base matrix to be $(r'',c')$ and try to augment it. Since $(r'',c')$ is above $(r',c)$, we have again moved towards the upper-left corner.

Note that there are at most $\log(1/\eta)$ different augment patterns and each time we rebase, $\mathbf{A}_{*,*}$ moves from one $(\mathcal{R}_t,\mathcal{C}_t)$ to another for some $t$. Hence, after repeating the argument above at most $2\log (1/\eta)$ times, the algorithm is guaranteed to observe a $2\times 2$ non-singular submatrix. Since the failure probability in each round is at most $4e^{-c_0/4}$, by union bound over $2\log (1/\eta)$ rounds, the overall failure probability is at most $8\log(1/\eta)e^{-c_0/4} \leq 1/3$, provided that $c_0=\mathcal{O}(\log\log(\frac{1}{\eta}))$.

In summary, the overall probability is at least $2/3$ that the algorithm answers correctly in all cases by finding a submatrix of rank $2$, when $\mathbf{A}$ is $\epsilon$-far from being rank-$1$.
\end{proof}



\subsubsection{Extension to General Rank $d$}

\begin{theorem}
\label{theorem: correctness of algorithm for general d}
Let $\epsilon\le 1/e$ and $d\ge 1$. For any matrix $\mathbf{A}$, the probability that Algorithm \ref{algorithm: non-adaptive robust testing of rank} fails is at most $1/\mathsf{poly}(d\log (\frac{1}{\epsilon}))$.
\end{theorem}

\begin{proof}
If $\mathbf{A}$ is of rank at most $d$, then the algorithm will never make mistake, so we assume that $\mathbf{A}$ is $\epsilon$-far from being rank $d$ in the proof below.

The idea is that, we start with the base case of an empty matrix, and augment it to a full-rank $r\times r$ matrix in $r$ rounds, where in each round we increase the dimension of the matrix by exactly one. Each round may contain several steps in which we move the intermediate $j\times j$ matrix ($j\le r$) towards the upper-left corner without augmenting it; here, moving the matrix towards the upper-left corner means changing $\mathbf{A}_{\mathcal{R},\mathcal{C}}$ to $\mathbf{A}_{\mathcal{R}',\mathcal{C}'}$, of the same rank, with $|\mathcal{R}'|=|\mathcal{R}|=|\mathcal{C}'|=|\mathcal{C}|=j$ and $\mathcal{R}'\preceq \mathcal{R}$ and $\mathcal{C}'\preceq \mathcal{C}$, where $\mathcal{R}'\preceq \mathcal{R}$ means that, suppose that $r_1' < r_2' < \cdots < r_j'$ are the (sorted) elements in $\mathcal{R}'$ and $r_1 < r_2 < \cdots < r_j$ are the (sorted) elements in $\mathcal{R}$, it holds that $r_i'\leq r_i$ for all $1\leq i\leq j$, and $\mathcal{C}'\preceq \mathcal{C}$ has a similar meaning.

The challenge is that those unobserved entries $?$'s may propagate as we augment the submatrix in each round. Our goal is to prove that starting from a \emph{structural} $(r-1)\times (r-1)$ full-rank submatrix which might have $?$'s as its entries, no matter what values of \emph{all} $?$'s are, with the augment operator we either (1) make progress for $(r-1)\times (r-1)$ submatrix, or (2) obtain an $r\times r$ full-rank submatrix \emph{with the same structure}. Let us first condition on the event that Lemma~\ref{lemma: uniform sampling captures augment pattern} holds true. Regarding the structure, we have the following claim.

\begin{claim}
\label{claim: structure for question mark}
There exists a searching path for $r\times r$ full-rank submatrices with non-decreasing $r$ which has the following lower triangular form modulo an elementary transformation
\begin{equation}
\label{equ: form}
\begin{bmatrix}
0 & 0 & \cdots & 0 & \cdots & 0 & \ne 0\\
0 & 0 & \cdots & 0 & \cdots & \ne 0 & ?\\
\vdots & \vdots &  & \vdots &  & \vdots & \vdots\\
0 & 0 & \cdots & \ne 0 & \cdots & ? & ?\\
\vdots & \vdots &  & \vdots &  & \vdots & \vdots\\
0 & \ne 0 & \cdots & ? & \cdots & ? & ?\\
\ne 0 & ? & \cdots & ? & \cdots & ? & ?\\
\end{bmatrix},
\end{equation}
where $\ne 0$ denotes the known entry which is non-zero, and $?$ denotes an entry which can be either observed or unobserved.
\end{claim}

\begin{proof}[Proof of Claim \ref{claim: structure for question mark}]
Without loss of generality, we assume that all $?$'s are unobserved, which is the most challenging case; otherwise, the proof degenerates to the discussion of \emph{central submatrix} in Case (iii) which we shall specify later.
We prove the claim by induction. The base case $r=1$ is true by Theorem \ref{theorem: correctness of algorithm for d=1}. Suppose the claims holds for $r-1$. We now argue the correctness for $r$.

Let $(p,q)$ be the augment. Denote the augment row by
\begin{equation*}
\begin{bmatrix}
y_1 & \cdots & y_b & \mathbf{A}_{p,q} & y_{b+2} & \cdots & y_{r}
\end{bmatrix},
\end{equation*}
and the augment column by
\begin{equation*}
\begin{bmatrix}
x_1 & \cdots & x_a & \mathbf{A}_{p,q} & x_{a+2} & \cdots & x_{r}
\end{bmatrix}^\top.
\end{equation*}
We now discuss three cases based on the relation between $a+b$ and $r$.



\medskip
\noindent{\textbf{Case (i). $a+b=r-1$ ($\mathbf{A}_{p,q}$ is on the antidiagonal of $r\times r$ submatrix)}.}


In this case, $y_{b+2},\dots,y_r$ and $x_{a+2},\dots,x_r$ are all $?$'s. We argue that $x_1=x_2=\cdots=x_a=0$ and $y_1=y_2=\cdots=y_b=0$; otherwise, we can make progress. First consider $y_i$ for $1\leq i\leq b$. If some $y_i\ne 0$, we can delete the $(r-i)$-th row in the $(r-1)\times (r-1)$ submatrix and insert the augment row (without the augment entry $\mathbf{A}_{p,q}$), which is above the deleted row.
Thus we obtain a new $(r-1)\times (r-1)$ submatrix towards the upper-left corner, and furthermore, the new submatrix exhibits the structure in \eqref{equ: form}. The same argument applies for $x_1,x_2,...,x_a$. Therefore, if no progress is made, it must hold that $x_1=x_2=...=x_a=0$ and $y_1=y_2=...=y_b=0$. In this case, $\mathbf{A}_{p,q}\ne 0$; otherwise, $(p,q)$ is not an augment. Therefore we obtain an $r\times r$ full-rank matrix of the form \eqref{equ: form}.

\medskip
\noindent{\textbf{Case (ii). $a+b< r-1$ ($\mathbf{A}_{p,q}$ is above the antidiagonal of $r\times r$ submatrix)}.}

In this case, $y_{r-a+1},\dots,y_r$ and $x_{r-b+1},\dots,x_r$ are all $?$'s. Similarly to Case (i), we shall argue that $x_1= \cdots =x_a=x_{a+2}= \cdots =x_{r-b}=0$ and $y_1=\cdots =y_b=y_{b+2}=\cdots=y_{r-a}=0$; otherwise, we can make progress. To see this, consider first $y_i$ for $1\leq i\leq b$ and then for $b+2\leq i\leq r-a$. If $y_i\ne 0$ for some $i\leq b$, we can delete the $(r-i)$-th row in the $(r-1)\times (r-1)$ submatrix  and insert the augment row (without the augment entry $\mathbf{A}_{p,q}$), which is above the deleted row, and so we make progress. Now assume that $y_1=\cdots=y_b=0$. If $y_i\ne 0$ for some $i$ such that $b+2\leq i\leq r-a$, we can delete the $(r-i+1)$-st row in the $(r-1)\times (r-1)$ submatrix of the last step and insert the augment row (without the augment entry $\mathbf{A}_{p,q}$), which is above the deleted row. So we make progress towards the most upper left corner. The same argument applies to $x_1,\dots,x_a,x_{a+2},\dots,x_{r-b}$. Therefore, $x_1=\cdots=x_a=x_{a+2}=...=x_{r-b}=0$ and $y_1=\cdots=y_b=y_{b+2}=\cdots=y_{r-a}=0$. In this case, $\mathbf{A}_{p,q}\ne 0$; otherwise, $(p,q)$ is not an augment since all possible choices of $?$'s cannot make the $r\times r$ submatrix non-singular. By exchanging the $(a+1)$-st row and the $(r-b)$-th row of the $r\times r$ submatrix or exchanging the $(b+1)$-st column and the $(r-a)$-th column, we obtain an $r\times r$ submatrix of the form \eqref{equ: form}.

\medskip
\noindent{\textbf{Case (iii). $a+b> r-1$ ($\mathbf{A}_{p,q}$ is below the antidiagonal of $r\times r$ submatrix)}.}

In this case, we argue that $x_i=y_j=0$ for all $i\leq r-b-1$ and $j\leq r-a-1$; otherwise we can make progress as Cases (i) and (ii) for $y_j$. To see this, let us discuss from $j=1$ to $r-a-1$. If $y_j\ne 0$ ($j=1,2,\dots,r-a-1$), we can delete the $(r-j)$-th row in the $(r-1)\times (r-1)$ submatrix and insert the augment row (without the augment entry $\mathbf{A}_{p,q}$), which is above the deleted row. So we make progress. The same argument applies to $x_1,\dots,x_{r-b-1}$. So $x_i=y_j=0$ for all $i\leq r-b-1$ and $j\leq r-a-1$.

Given that there is only one non-zero entry in the first $r-b-1$ rows and the first $r-a-1$ columns of the $r\times r$ submatrix (i.e., the Laplace expansion of the determinant), we only need to focus on a minor corresponding to a $\min\{a,b\}\times \min\{a,b\}$ \emph{central submatrix}, which decides whether the determinant of the $r\times r$ submatrix is zero and is fully-observed because the augment $(p,q)$ is at the lower right corner of the central submatrix (see the red part in Eqn.~\eqref{equ: central matrix}). Since it is fully-observed, the minor must be non-zero; otherwise, $(p,q)$ cannot be an augment for all choices of $?$'s. Therefore, we can do an elementary transformation to make the central submatrix a lower triangular matrix with non-zero antidiagonal entries. More importantly, such an elementary transformation also transforms the $r\times r$ matrix to a lower triangular matrix with non-zero antidiagonal entries, because all the entries to the left and above of the central matrix are $0$'s, and all the entries to the right and below of the central matrix are $?$'s. Hence any elementary transformation keeps $0$'s and $?$'s unchanged, and we obtain therefore an $r\times r$ submatrix of the form \eqref{equ: form}.

\begin{equation}
\label{equ: central matrix}
\begin{bmatrix}
0 & 0 & \cdots & \cdots & 0 & \cdots & 0 & \cdots & 0 & \ne 0\\
0 & 0 & \cdots & \cdots & 0 & \cdots & 0 & \cdots & \ne 0 & ?\\
\vdots & \vdots & & & \vdots & & \vdots & & \vdots & \vdots\\
\vdots & \vdots & & & \vdots & & \vdots & & \vdots & \vdots\\
0 & 0 & \cdots & \cdots & \red{\ne 0} & \red{\cdots} & \red{\textsf{known}} & \cdots & ? & ?\\
\vdots & \vdots & & & \red{\vdots} & & \red{\vdots} & & \vdots & \vdots\\
0 & 0 & \cdots & \cdots & \red{\textsf{known}} & \red{\cdots} & \red{\textsf{augment } \mathbf{A}_{p,q}} & \cdots & ? & ?\\
\vdots & \vdots & & & \vdots & & \vdots & & \vdots & \vdots\\
0 & \ne 0 & \cdots & \cdots & ? & \cdots & ? & \cdots & ? & ?\\
\ne 0 & ? & \cdots & \cdots & ? & \cdots & ? & \cdots & ? & ?
\end{bmatrix}.
\end{equation}
\end{proof}

Now we are ready to prove Theorem \ref{theorem: correctness of algorithm for general d}. Note that Lemma \ref{lemma: uniform sampling captures augment pattern} works only for \emph{fixed} $(\mathcal{R},\mathcal{C})$. To make the lemma applicable ``for all'' $(\mathcal{R},\mathcal{C})$ throughout the augmentation process, we shall take a union bound by choosing $|\mathcal{R}|$ and $|\mathcal{C}|$ large enough. Specifically, for each $i$, we divide $\mathcal{R}_i=\bigcup_{k=1}^\ell \mathcal{R}_i^{(k)}$ uniformly at random into $\ell = d+d\log(\frac{1}{\eta})$\footnote{In the number of parts $d+d\log(\frac{1}{\eta})$, the first term follows from the operation of augmenting $1\times 1$ submatrix to $d\times d$. The second term follows from moving the submatrix towards the upper left corner (from the lower-right corner in the worst case).} even parts $\mathcal{R}_i^{(1)}, \mathcal{R}_i^{(2)}, \dots, \mathcal{R}_i^{(d)}$, where each $|\mathcal{R}_i^{(k)}|=c[\log(d)+\log\log(\frac{1}{\eta})]2^i$, and divide $\mathcal{C}_i=\bigcup_{k=1}^d \mathcal{C}_i^{(k)}$ uniformly at random into $\ell$ even parts $\mathcal{C}_i^{(1)}, \mathcal{C}_i^{(2)}, \dots, \mathcal{C}_i^{(\ell)}$, where each $|\mathcal{C}_i^{(k)}|=c[\log(d)+\log\log(\frac{1}{\eta})]/(2^i\eta)$ for every $k$. We note that $\{\mathcal{R}_i^{(k)}\}_k$ (and $\{\mathcal{C}_i^{(k)}\}_k$) are independent of each other. It follows that
the event in Lemma \ref{lemma: uniform sampling captures augment pattern} holds
with probability at least $1-\frac{1}{\operatorname{poly}(d\log(1/\eta))}$. By a union bound over all $\ell^2 = \Theta(d^2\log^2(\frac{1}{\eta}))$ possible choices of $\{\mathcal{R}_i^{(k)}\}\times \{\mathcal{C}_i^{(k)}\}$ and Claim \ref{claim: structure for question mark}, with probability at least $1-1/\mathsf{poly}(d\log(\frac{1}{\epsilon}))$, Algorithm \ref{algorithm: non-adaptive robust testing of rank} answers correctly, when $\mathbf{A}$ is $\epsilon$-far from having rank $d$.
\end{proof}

\subsubsection{A Computationally Efficient Algorithm}

We now show how to implement Algorithm \ref{algorithm: non-adaptive robust testing of rank} efficiently, for which we only need to give a polynomial-time algorithm to solve the minimization problem \eqref{equ: upper bound} in Algorithm \ref{algorithm: a computationally efficient algorithm}. We have the following theorem.

\begin{algorithm}[ht]
\caption{Solving problem \eqref{equ: upper bound} in the polynomial time}
\label{algorithm: a computationally efficient algorithm}
\begin{algorithmic}[1]
\INPUT $\mathcal{R}_1,\dots,\mathcal{R}_k$ and $\mathcal{C}_1,\dots,\mathcal{C}_k$. Denote by $\mathcal{R}^{(i)}$ the set of sampled indices in the $i$-th column of $\mathbf{A}$, and let $\mathcal{R}^{(i)}_\perp = \mathcal{R}_k \setminus \mathcal{R}^{(i)}$.
\OUTPUT the solution $r$ to the minimization problem \eqref{equ: upper bound}.
\State $\S\leftarrow [\ ]$ is an empty matrix.
\State $r\leftarrow 0$.
\For{$i=1,\dots,|\mathcal{C}_1|$}
	\If {there exists $\mathbf{x}$ such that $\S_{\mathcal{R}^{(i)},:}\mathbf{x} = \mathbf{A}_{\mathcal{R}^{(i)},i}$}
		\State $\mathbf{A}_{\mathcal{R}_\perp^{(i)},i}\leftarrow \S_{\mathcal{R}_\perp^{(i)},:}\mathbf{x}$.
	\Else
		\State $\mathbf{A}_{\mathcal{R}_\perp^{(i)},i}\leftarrow \mathbf{1}$.
		\State $\S\leftarrow [\S,\mathbf{A}_{\mathcal{R}_k,i}]$.
		\State $r\leftarrow r+1$.
	\EndIf
\EndFor
\State \Return $r$.
\end{algorithmic}
\end{algorithm}

\begin{theorem}
\label{theorem: time complexity of rank testing}
Algorithm \ref{algorithm: a computationally efficient algorithm} correctly solves the minimization problem \eqref{equ: upper bound} in $\mathsf{poly}(\frac{d}{\epsilon})$ time.
\end{theorem}

\begin{proof}
Without loss of generality, we may permute the rows and columns of $\mathbf{A}$ and assume that $\mathcal{R}_i = \{1,\dots,|\mathcal{R}_i|\}$ and $\mathcal{C}_i = \{1,\dots,|\mathcal{C}_i|\}$ for all $i\leq \lceil\log\frac{1}{\eta}\rceil$. Our goal is to complete the submatrix $\mathbf{A}_{(\mathcal{R}_m\times \mathcal{C}_1)}$ such that its rank is minimal. Denote by $\mathcal{R}^{(i)}$ the set of sampled indices in the $i$-th column of $\mathbf{A}$. We start from an empty matrix $\S=[\ ]$. We will extend $\S$ as we process the columns of $\mathbf{A}$ that are not in the block $(\mathcal{R}_k,\mathcal{C}_k)$ from left to right. We will maintain the following two invariants:

\begin{itemize}
\item
The minimal rank of matrix completion is always equal to the number of columns of $\S$.
\item
After processing the $i$-th column of $\mathbf{A}$, the restricted column $\mathbf{A}_{\mathcal{R}^{(i)},i}$ is in the column space of $\S_{\mathcal{R}^{(i)},:}$.
\end{itemize}

Note that both invariants hold in the base case. For the $i$-th column $\mathbf{A}_{:,i}$ that we encounter, if $\mathbf{A}_{\mathcal{R}^{(i)},i}$ is in the column space of $\S_{\mathcal{R}^{(i)},:}$, then we use a linear combination on the first $|\mathcal{R}^{(i)}|$ coordinates of vectors given by the columns of $\S_{\mathcal{R}^{(i)},:}$ to extend $\mathbf{A}_{\mathcal{R}^{(i)},i}$ from a vector in $|\mathcal{R}^{(i)}|$ dimensions to a vector in $|\mathcal{R}_m|$ dimensions, and we do not change $\S$. Notice that the two invariants are preserved in this case.

Otherwise, $\mathbf{A}_{\mathcal{R}^{(i)},i}$ is not in the column space of $\S_{\mathcal{R}^{(i)},:}$. If $\mathbf{A}_{\mathcal{R}^{(i)},i}$ were in the column space of $\mathbf{A}_{\mathcal{R}^{(i)},1:{(i-1)}}$, we would, by the second invariant above, have that $\mathbf{A}_{\mathcal{R}^{(i)},i}$ is in the column space of $\S_{\mathcal{R}^{(i)},:}$, a contradiction. Therefore, $\mathbf{A}_{\mathcal{R}^{(i)},i}$ is not in the column space of $\mathbf{A}_{\mathcal{R}^{(i)},[i-1]}$. In this case, $\mathbf{A}_{:,i}$ must be linearly independent of all previous columns $\mathbf{A}_{:,[i-1]}$. We can thus append to $\S$ on the right the vector $[\mathbf{A}_{\mathcal{R}^{(i)},i};\mathbf{1}]$ (The vector $\mathbf{1}$ can be replaced with any $(|\mathcal{R}_k|-|\mathcal{R}^{(i)}|)$-dimensional vector), which increases the size and rank of $\S$ by $1$, and we maintain our two invariants.

The time complexity of Algorithm \ref{algorithm: a computationally efficient algorithm} is $\mathsf{poly}(\frac{d}{\epsilon})$.
\end{proof}







\subsection{Lower Bounds over Finite Fields in the Sampling Model}

According to Yao's minimax principle, it suffices to provide a distribution on $n\times n$ input matrices $\mathbf{A}$ for which any deterministic testing algorithm fails with significant probability over the choice of $\mathbf{A}$. Before proceeding, we first state a hardness result that we want to reduce from.

\begin{algorithm}[ht]
\caption{Decomposing edges $E$}
\label{algorithm: decompose E}
\begin{algorithmic}[1]
\INPUT A bipartite graph $G=(L\cup R,E)$.
\OUTPUT Partition of $E=E_1\cup \cdots \cup E_t$ and the set of pivot nodes $\{w_t\}$.
\State $t\leftarrow 0$.
\While {$E\ne\emptyset$}
	\State Find $v$ such that $1\le \mathsf{deg}(v)\le\gamma d$.
	\State $t\rightarrow t+1$.
	\State $E_t\leftarrow$ edges between $v$ and all its neighbours.
	\State $w_t\leftarrow v$.
	\State $E\leftarrow E \setminus E_t$.
\EndWhile
\State \Return $E=E_1\cup\cdots\cup E_t$ and $\{w_t\}$.
\end{algorithmic}
\end{algorithm}

\begin{lemma}
\label{lemma: partition of graph}
Let $G=(L\cup R,E)$ be a bipartite graph such that $|L|=|R|=n$ and $|E|<\gamma^2 d^2$ for $d\leq n/\gamma$. Then Algorithm \ref{algorithm: decompose E} returns a partition $E=E_1\cup E_2\cup\cdots\cup E_t$, where $t\le \gamma^2 d^2$ and $|E_i|\le \gamma d$ for all $i$.
\end{lemma}

\begin{proof}
We first show that Algorithm \ref{algorithm: decompose E} can be executed correctly, that is, whenever $E\ne \emptyset$ there always exists $v$ such that $1\le \mathsf{deg}(v)\le\gamma d$. We note that $1\le \mathsf{deg}(v)$ is obvious because $E\ne \emptyset$. If all vertices with non-zero degree have degree at least $\gamma d$, the total number of edges would be at least $\gamma d n\geq d^2 \gamma^2$, contradicting our assumption on the size of $E$. When the algorithm terminates, it is clear that each $E_i$ generates at most $\gamma d$ edges and the $E_i$'s are disjoint and so $t\le \gamma^2 d^2$.
\end{proof}

\begin{lemma}
\label{Lemma: independence}
Suppose that there are $t$ groups of (fixed) vectors $\{\v_1^{(k)},\dots,\v_{s_k}^{(k)}\}_{k\in [t]}\subset\mathbb{F}^d$ such that the vectors in each group are linearly independent (denoted by $\perp$). Let $\mathbf{w}_1,\dots,\mathbf{w}_r$ be random vectors in $\mathbb{F}^d$ such that each $\mathbf{w}_i$ is chosen uniformly at random from some set $\mathcal{S}_i\subseteq \mathbb{F}^d$ with $|\mathcal{S}_i|\geq |\mathbb{F}|^{(1-\gamma)d}$. Let $s = \max_k {s_k}$. When $s+r\le \gamma d$ for all $k$ and $t\le \gamma^2 d^2$, it holds that
\begin{equation*}
\Pr_{\mathbf{w}_1,\dots,\mathbf{w}_r} \left\{\v_1^{(k)}\perp \dots \perp\v_{s_k}^{(k)}\perp\mathbf{w}_1\perp \cdots \perp\mathbf{w}_r \text{ for all } k\in [t]\right \}\ge 1-\frac{\gamma^3 d^3}{|\mathbb{F}|^{(1-2\gamma)d}}.
\end{equation*}
\end{lemma}

\begin{proof}
For fixed $\mathbf{w}_1,\dots,\mathbf{w}_{i-1}$ such that $\v_1^{(k)},\dots,\v_{s_k}^{(k)},\mathbf{w}_1,\dots,\mathbf{w}_{i-1}$ are linearly independent for all $k\in[t]$, the probability that $\mathbf{w}_i\in \mathcal{S}_i$ is linearly independent of $\v_1^{(k)},\dots,\v_{s_k}^{(k)},\mathbf{w}_1,\dots,\mathbf{w}_{i-1}$ for all $k\in[t]$ is at least
$
1-\frac{t|\mathbb{F}|^{s_k+i-1}}{|\mathcal{S}_i|} \geq 1-\frac{t|\mathbb{F}|^{s_k+i-1}}{|\mathbb{F}|^{(1-\gamma)d}} = 1-\frac{t}{|\mathbb{F}|^{(1-\gamma)d-(s_k+i-1)}} \geq 1 - \frac{t}{|\mathbb{F}|^{(1-\gamma)d-(s+i-1)}}.
$
Therefore, for all $k\in[t]$ with $t\le\gamma^2 d^2$, we have
\begin{align*}
& \quad\ \Pr_{\mathbf{w}_1,\dots,\mathbf{w}_r}\{\v_1^{(k)}\perp\cdots\perp\v_{s_k}^{(k)}\perp\mathbf{w}_1\perp\cdots\perp\mathbf{w}_r\text{ for all }k\}\\
&=  \prod_{i=2}^{r} \Pr_{\mathbf{w}_i}\{\v_1^{(k)}\perp\cdots\perp\v_{s_k}^{(k)}\perp \mathbf{w}_1 \perp \cdots \perp \mathbf{w}_i \ \text{ for all }k \mid \v_1^{(k)}\perp\cdots\perp\v_{s_k}^{(k)}\perp \mathbf{w}_1 \perp \cdots \perp \mathbf{w}_{i-1}\text{ for all }k\}
\\
&\qquad \times \Pr_{\mathbf{w}_1}\{\v_1^{(k)}\perp \cdots \perp\v_{s_k}^{(k)}\perp\mathbf{w}_1\text{ for all }k\}\\
&\ge \prod_{i=1}^r \left(1-\frac{t}{|\mathbb{F}|^{(1-\gamma)d-(s+i-1)}}\right)\\
&\ge \prod_{i=1}^r \left(1-\frac{\gamma^2 d^2}{|\mathbb{F}|^{(1-2\gamma)d}}\right)\quad\text{(by $s+i-1\le\gamma d$ and $t\le \gamma^2 d^2$)}\\
&\ge 1- \frac{r\gamma^2 d^2}{|\mathbb{F}|^{(1-2\gamma)d}}\quad\text{(by $(1-x)^t\ge 1-tx$ for $x\in(0,1)$)}\\
&\ge 1-\frac{\gamma^3 d^3}{|\mathbb{F}|^{(1-2\gamma)d}}.\quad\text{(since $r\le\gamma d$)}. \qedhere
\end{align*}
\end{proof}

When $|\mathcal{S}_i| = |\mathbb{F}|^{d-d_i}$ for $d_i\leq \gamma d$, it follows from Lemma \ref{Lemma: independence} that the number of choices of the event
\begin{equation}
\label{equ: fraction}
\begin{split}
&\left|\left\{(\mathbf{w}_1,\dots,\mathbf{w}_r)\in \mathcal{S}_1\times\cdots\times \mathcal{S}_r: \v_1^{(k)}\perp \cdots \perp\v_{s_k}^{(k)}\perp\mathbf{w}_1 \perp \cdots \perp \mathbf{w}_r \text{ for all } k\right\}\right|\\
=&\Pr_{\mathbf{w}_1,\dots,\mathbf{w}_r}\left\{\v_1^{(k)}\perp \cdots \perp\v_{s_k}^{(k)}\perp\mathbf{w}_1 \perp \cdots \perp \mathbf{w}_r \text{ for all } k\right\}\cdot \prod_{i=1}^r|\mathcal{S}_i|\\
\ge & \left(1-\frac{\gamma^3 d^3}{|\mathbb{F}|^{(1-2\gamma)d}}\right)\cdot \prod_{i=1}^r |\mathcal{S}_i|\quad\text{(by Lemma \ref{Lemma: independence})}\\
= & \left(1-\frac{\gamma^3 d^3}{|\mathbb{F}|^{(1-2\gamma)d}}\right)|\mathbb{F}|^{rd-\sum_{i=1}^r d_i}.\quad\text{(recall that $|\mathcal{S}_i|=|\mathbb{F}|^{d-d_i}$)}
\end{split}
\end{equation}

Based on this result, we have the following lemma.
\begin{algorithm}[ht]
\caption{Path for assigning subspace $H_v$ and random vector $\mathbf{x}_v$ to each node $v$}
\label{algorithm: path for assigning subspace and random vector for each node}
\begin{algorithmic}[1]
\INPUT Bipartite graph $G=(L\cup R,E)$, partition $E=E_1\cup\cdots \cup E_t$ and pivot nodes $\{w_t\}$ by Algorithm \ref{algorithm: decompose E}, observed entries $\mathbf{x}|_{E}$.
\OUTPUT An affine space $H_v$ of vectors for every node $v$ and a vector $\mathbf{x}_v\in H_v$ for every node $v$.
\State $H_v\gets \mathbb{F}^d$ for all $v$.
\State Set all nodes $v$ unassigned.
\For {$i\leftarrow t$ \textbf{down to} $1$}
	\State Let $v_1^{(i)},\dots,v_{|E_i|}^{(i)}$ be the non-pivot nodes in $E_i$ (i.e., the edges in $E_i$ are $(w_i, v_j^{(i)})$).
	\For {$j\leftarrow 1$\textbf{ to }$|E_i|$}
		\If{$v_j^{(i)}$ is unassigned} \label{alg:line:v_unassigned}
			\State $W_{v_j^{(i)}}\hspace{-0.1cm} \gets\hspace{-0.1cm} H_{v_j^{(i)}}\setminus\bigcup_{k\leq i: v_{j}^{(i)}\neq w_k} \hspace{-0.2cm} \operatorname{span}\{\mathbf{x}_{v_1}^{(i)}, \dots, \mathbf{x}_{v_{j-1}}^{(i)}, \text{previously assigned non-pivot nodes in }E_k\}$.
			\State Choose $w_{v_j^{(i)}}$ uniformly at random from $H_{v_j^{(i)}}$. \label{alg:line:nonpivot_vector_assignment}
			\If {$w_{v_j^{(i)}}\not\in W_{v_j^{(i)}}$}
				\State \textbf{abort}.
			\EndIf
			\State Set $v_j^{(i)}$ to be assigned.
		\EndIf
	\EndFor
	\State Let $H_{w_i}$ be the solution set to the linear system (w.r.t. $\mathbf{x}_{w_i}$): $\mathbf{x}_{w_i}^\top [\mathbf{x}_{v_1}^{(i)},\cdots ,\mathbf{x}_{v_{|E_i|}}^{(i)}]=(\mathbf{x}|_{E_i})^\top$.
\EndFor
\State Choose $\mathbf{x}_{w_s}$ uniformly from $H_{w_s}$ of dimension $d-|E_s|$ for all $s\in\mathcal{S}_0=\{p\in[t]\mid w_p\text{ is
 unassigned}\}$\label{alg:line:pivot_vector_assignment}.
\State \Return $\{H_v\}$ and $\{\mathbf{x}_v\}$.
\end{algorithmic}
\end{algorithm}


\begin{lemma}
Let $\mathbf{U},\mathbf{V}\sim \mathcal{U}_\mathbb{F}(n,d)$, where $\mathcal{U}_{\mathbb{F}}(m,n)$ represents $m\times n$ i.i.d. uniform matrix over a finite field $\mathbb{F}$. Denote by $\mathcal{S}$ any subset of $[n]\times [n]$ such that $|\mathcal{S}|<\gamma^2 d^2$ for $\gamma\in (0,1/4)$ and $d\leq n/\gamma$. It holds that for any $\mathbf{x}\in\mathbb{F}^{|\mathcal{S}|}$,
\begin{equation*}
\Pr[(\mathbf{U}\mathbf{V}^T)|_\mathcal{S}=\mathbf{x}]-\frac{1}{|\mathbb{F}|^{|\mathcal{S}|}}\ge -\frac{\gamma^5 d^5}{|\mathbb{F}|^{(1-2\gamma)d+|\mathcal{S}|}}.
\end{equation*}
\end{lemma}

\begin{proof}
Consider a bipartite graph $G=(L\cup R,E)$ where $|L|=|R|=n$ and $(i,j)\in E$ if and only if $(i,j)\in\mathcal{S}$. We run Algorithm \ref{algorithm: decompose E} on graph $G$. By Lemma \ref{lemma: partition of graph}, we obtain a sequence of edge sets $E_1\dots,E_t$ with $w_1,\dots,w_t$ (called \emph{pivot nodes}), such that
\begin{itemize}
\item[1.]
$\{E_i,\dots,E_t\}$ forms a partition of $E$;
\item[2.]
$|E_i|\le \gamma d$ for all $i$.
\end{itemize}
Since there is a one-by-one correspondence between the edges and the entries in $\mathcal{S}$, we will not distinguish edges and entries in the rest of the proof.

We associate each node $v$ of $G$ with an affine space $H_v\subseteq \mathbb{F}^d$ and a random vector $\mathbf{x}_v\in H_v$ as in Algorithm \ref{algorithm: path for assigning subspace and random vector for each node}. Basically, Algorithm \ref{algorithm: path for assigning subspace and random vector for each node} first assigns the non-pivot nodes (to determine the affine subspace $H_{w_i}$) from the $E_t$ down to the $E_1$), and in the end assigns all unassigned pivot nodes.

In the following argument, we number the for-loop iterations in Algorithm \ref{algorithm: path for assigning subspace and random vector for each node} backwards, i.e., the for-loop starts with the $t$-th iteration and goes down to the first iteration. In the $i$-th iteration, let $r_i$ denote the number of nodes $v_j^{(i)}$ that are unassigned at the runtime of Line~\ref{alg:line:v_unassigned} and let $\#\mathcal{E}_i$ denote the number of good choices (which do not trigger abortion) of Step~\ref{alg:line:nonpivot_vector_assignment}  over all $r_i$ nodes to be assigned.
Let $\#\mathcal{G}$ be the number of possible choices of Step~\ref{alg:line:pivot_vector_assignment} of Algorithm \ref{algorithm: path for assigning subspace and random vector for each node} and $s_0=|\mathcal{S}_0|$ be the number of assigned pivot nodes by Step~\ref{alg:line:pivot_vector_assignment}. Note that by the construction of Algorithm \ref{algorithm: decompose E}, the non-pivot nodes of $E_i$ cannot be the pivot nodes of $E_j$ for $j<i$. So Algorithm \ref{algorithm: path for assigning subspace and random vector for each node}, if terminated successfully, can find an assignment such that $(\mathbf{U}\mathbf{V}^\top)|_\mathcal{S}=\mathbf{x}$. We now lower bound the success probability.

Let $d_j^{(i)}=d-\mathsf{dim}(H_{v_j^{(i)}})$, which is either $0$ or $|E_k|$ for some $k>i$. For any given realization $\mathbf{x}$, we have the following:

\begin{align*}
&\quad\ \Pr\{(\mathbf{U} \mathbf{V}^\top)|_\mathcal{S}=\mathbf{x}\}\\
&\ge \frac{\#\mathcal{E}_t\cdot \#\mathcal{E}_{t-1} \cdots \#\mathcal{E}_1}{|\mathbb{F}|^{d (r_t + \cdots + r_1)}}\frac{\#\mathcal{G}}{|\mathbb{F}|^{d s_0}}\quad\mbox{(by rule of product and definition of $\#\mathcal{E}_i$)}\\
&\ge \prod_{i=1}^{t} \frac{1}{|\mathbb{F}|^{d_1^{(i)}+ \cdots +d_{r_i}^{(i)}}}\left(1-\frac{\gamma^3 d^3}{|\mathbb{F}|^{(1-2\gamma)d}}\right)^t\cdot \frac{\#\mathcal{G}}{|\mathbb{F}|^{d s_0}}\quad \mbox{(by Eqn. \eqref{equ: fraction})}\\
&\ge \frac{1}{|\mathbb{F}|^{\sum_{i=1}^t\sum_{j=1}^{r_i} d_j^{(i)}}}\left(1-\frac{\gamma^5 d^5}{|\mathbb{F}|^{(1-2\gamma)d}}\right)\cdot \frac{\#\mathcal{G}}{|\mathbb{F}|^{d\times s_0}}\quad\mbox{(by $(1-x)^t\ge 1-tx$ for $x\in(0,1)$ and $t\le \gamma^2 d^2$)}\\
&=\frac{1}{|\mathbb{F}|^{\sum_{i=1}^t\sum_{j=1}^{r_i} d_j^{(i)}}}\left(1-\frac{\gamma^5 d^5}{|\mathbb{F}|^{(1-2\gamma)d}}\right)\cdot \frac{1}{|\mathbb{F}|^{\sum_{s\in\mathcal{S}_0} |E_s|}}\quad\text{(by definition of $\#\mathcal{G}$)}\\
&\ge \frac{1}{|\mathbb{F}|^{|E_1|+\cdots+|E_t|}}\left(1-\frac{\gamma^5 d^5}{|\mathbb{F}|^{(1-2\gamma)d}}\right),
\end{align*}
where the last inequality holds because $|E_1|+\dots+|E_t|=\sum_{j=1}^t\sum_{i=1}^{r_j} d_i^{(j)}+\sum_{s\in\mathcal{S}_0}|E_s|$ as every pivot and non-pivot node must be assigned exactly once by Algorithm \ref{algorithm: path for assigning subspace and random vector for each node} upon successful termination. (Recall that $d_i^{(j)}$ is either equal to $0$ when $v_j^{(i)}$ is non-pivotal, or equal to $|E_k|$ when $v_j^{(i)}=w_k$.)
\end{proof}

Denote by $\mathcal{S}\subset[n]\times [n]$ a set of indices of an $n\times n$ matrix. For any distribution $\mathcal{L}$ over $\mathbb{F}^{n\times n}$, define $\mathcal{L}(\mathcal{S})$ on $\mathbb{F}^{|\mathcal{S}|}$ as the marginal distribution of $\mathcal{L}$ on the entries of $\mathcal{S}$, namely,
\begin{equation*}
(\mathbf{X}_{p_1,q_1},\mathbf{X}_{p_2,q_2},\dots,\mathbf{X}_{p_{|\mathcal{S}|},q_{|\mathcal{S}|}})\sim\mathcal{L}(\mathcal{S}),\qquad \mathbf{X}\sim\mathcal{L}.
\end{equation*}
Now we are ready to show a lower bound of robust testing problem over any finite field.
\begin{theorem}
\label{theorem: total variation distance of sampled matrices for rank testing lower bound over finite field}
Suppose that $\mathbb{F}$ is a finite field and $\gamma\in(0,1/4)$ is an absolute constant. Let $\mathbf{U},\mathbf{V}\sim\mathcal{U}_{\mathbb{F}}(n,d)$ and $\mathbf{W}\sim\mathcal{U}_{\mathbb{F}}(n,n)$, where $\mathcal{U}_{\mathbb{F}}(m,n)$ represents $m\times n$ i.i.d. uniform matrix over a finite field $\mathbb{F}$. Consider two distributions $\mathcal{L}_1$ and $\mathcal{L}_2$ over $\mathbb{F}^{n\times n}$ defined by $\mathbf{U}\mathbf{V}^\top$ and $\mathbf{W}$, respectively. Let $\mathcal{S}\subset [n]\times [n]$. When $|\mathcal{S}|<\gamma^2 d^2$, it holds that
\begin{equation*}
d_{TV}(\mathcal{L}_1(\mathcal{S}),\mathcal{L}_2(\mathcal{S}))\le Cd^5|\mathbb{F}|^{-cd},
\end{equation*}
where $C,c>0$ are constants depending on $\gamma$, and $d_{TV}(\cdot,\cdot)$ represents the total variation distance between two distributions.
\end{theorem}

\begin{proof}
Let
\begin{equation*}
\mathcal{X}=\left\{\mathbf{x}\in\mathbb{F}^{|\mathcal{S}|} \left|\ \Pr\left[(\mathbf{U}\mathbf{V}^\top)|_{\mathcal{S}}=\mathbf{x}\right]<\frac{1}{|\mathbb{F}|^{|\mathcal{S}|}}\right.\right\}.
\end{equation*}
It follows from the definition of total variation distance that
\begin{equation*}
d_{TV}(\mathcal{L}_1(\mathcal{S}),\mathcal{L}_2(\mathcal{S}))=\sum_{\mathbf{x}\in\mathcal{X}}\left[\frac{1}{|\mathbb{F}|^{|\mathcal{S}|}}-\Pr[(\mathbf{U}\mathbf{V}^\top)|_{\mathcal{S}}=\mathbf{x}]\right]\le \sum_{\mathbf{x}\in\mathcal{X}}\frac{\gamma^5 d^5}{|\mathbb{F}|^{(1-2\gamma)d}}\frac{1}{|\mathbb{F}|^{|\mathcal{S}|}}\le \frac{\gamma^5 d^5}{|\mathbb{F}|^{(1-2\gamma)d}},
\end{equation*}
where the last inequality holds since $|\mathcal{X}|\le |\mathbb{F}|^{|\mathcal{S}|}$.
\end{proof}

Based on the above theorem, we have the following lower bound for the rank testing problem over finite field.
\begin{theorem}
\label{theorem: lower bound of rank testing over finite fields under sampling model}
Let $d\le \sqrt{\epsilon}n$. Any non-adaptive algorithm for Problem \ref{problem: problem of property testing of rank} over any finite field $\mathbb{F}$ requires $\Omega(d^2/\epsilon)$ queries.
\end{theorem}
\begin{proof}
We first show that for constant $\epsilon$, any non-adaptive algorithm for Problem \ref{problem: problem of property testing of rank} over finite field $\mathbb{F}$ requires $\Omega(d^2)$ queries. Note that $\mathbf{W}\sim\mathcal{U}_{\mathbb{F}}(n,n)$ is $\epsilon$-far from having rank less than $d$. It follows immediately from the preceding theorem that any algorithm which solves the matrix rank testing problem over a finite field must read $\Omega(d^2)$ entries; otherwise when $d$ is large enough, it will hold that $d_{TV}(\mathcal{L}_1(\mathcal{S}),\mathcal{L}_2(\mathcal{S}))<1/4$, contradicting the correctness of the algorithm on distinguishing $\mathcal{L}_1$ from $\mathcal{L}_2$.

We now prove the case for arbitrary $\epsilon$. Denote by $\mathbf{A}$ and $\mathbf{B}$ the two hard instances in Theorem \ref{theorem: total variation distance of sampled matrices for rank testing lower bound over finite field}. We construct two hard instances $\mathbf{C}$ and $\mathbf{D}$ by uniformly at random planting the above-mentioned hard instances $\mathbf{A}$ and $\mathbf{B}$ of dimension $\sqrt{\epsilon}n\times \sqrt{\epsilon}n$, respectively, and padding zeros everywhere else. Note that $\mathbf{D}$ being $\epsilon$-far from rank $d$ is equivalent to $\mathbf{B}$ being constant-far from rank $d$. Suppose that we can request $cd^2/\epsilon$ queries with a small absolute constant $c$ to distinguish the ranks of the hard instances $\mathbf{C}$ and $\mathbf{D}$, then in expectation (and with high probability by a Markov bound) we can request $cd^2$ queries of the hard instances $\mathbf{A}$ and $\mathbf{B}$ to distinguish their ranks, which leads to a contradiction.
\end{proof}






\subsection{Lower Bounds over Real Field under the Sampling Model}
The \emph{rigidity} of a matrix $\mathbf{A}$ over a field $\mathbb{F}$, denoted by $\mathcal{R}_{\mathbf{A}}^{\mathbb{F}}(r)$, is the least number of entries of $\mathbf{A}$ that must be changed in order to reduce the rank of $\mathbf{A}$ to a value at most $r$:
$
\mathcal{R}_{\mathbf{A}}^{\mathbb{F}}(r):=\min\{\|\mathbf{C}\|_0\mid\mathsf{rank}_{\mathbb{F}}(\mathbf{A}+\mathbf{C})\le r\}.
$
We first cite the following lemma and theorem.

\begin{lemma}[Matrix Rigidity, Theorem 6.4, \cite{valiant1977graph}]
\label{lemma: matrix rigidity over reals}
The real $n\times n$ i.i.d. Gaussian matrix $\mathbf{G}$ is of rigidity $\mathcal{R}_{\mathbf{G}}^{\mathbb{R}}(r)=\Omega((n-r)^2)$ with probability $1$.
\end{lemma}


\begin{theorem}[Theorem 3.5, \cite{li2014sketching}]
\label{theorem: hardness of distinguishing Gaussian noise}
Let $\mathbf{U},\mathbf{V}\sim \mathcal{G}(n,d)$ and $\mathbf{G}\sim \mathcal{G}(n,n)$. Consider two distributions $\mathcal{L}_1$ and $\mathcal{L}_2$ over $\mathbb{R}^{n\times n}$ defined by $\mathbf{U}\mathbf{V}^\top$ and $\mathbf{U}\mathbf{V}^\top+n^{-14}\mathbf{G}$, respectively. Let $\mathcal{S}\subset [n]\times [n]$. Whenever $|\mathcal{S}|\le d^2$, it holds that
\begin{equation*}
d_{TV}(\mathcal{L}_1(\mathcal{S}),\mathcal{L}_2(\mathcal{S}))\le C|S|(n^{-2}+dc^d),
\end{equation*}
where $C>0$ and $0<c<1$ are absolute constants.
\end{theorem}

Now we are ready to prove the sample complexity lower bound of rank testing over the reals in the sampling model.
\begin{theorem}
\label{theorem: lower bound of rank testing over reals}
Let $d\le \sqrt{\epsilon}n$. Any non-adaptive algorithm for Problem \ref{problem: problem of property testing of rank} over $\mathbb{R}$ requires $\Omega(d^2/\epsilon)$ queries.
\end{theorem}

\begin{proof}
We first show that for constant $\epsilon$, any non-adaptive algorithm for Problem \ref{problem: problem of property testing of rank} over $\mathbb{R}$ requires $\Omega(d^2)$ queries. Note that Theorem \ref{theorem: hardness of distinguishing Gaussian noise} provides two hard instances for distinguishing a rank-$d$ matrix (of the form $\mathbf{A}=\mathbf{U}\mathbf{V}^\top$) from a rank-$n$ matrix (of the form $\mathbf{B}=\mathbf{U}\mathbf{V}^\top+n^{-14}\mathbf{G}$), where $\mathbf{U},\mathbf{V}\sim\mathcal{G}(n,d)$ and $\mathbf{G}\sim\mathcal{G}(n,n)$. For our purpose, we only need to show that the rank-$n$ matrix $\mathbf{B}=\mathbf{U}\mathbf{V}^\top+n^{-14}\mathbf{G}$ has rigidity $\mathcal{R}_{\mathbf{B}}^{\mathbb{R}}(d)=\Omega(n^2)$.
Denote by $\mathsf{rank}_{\ell}(\mathbf{B})=\min_{\|\S\|_0=\ell} \mathsf{rank}(\mathbf{B}+\S)$. We note that
\begin{equation*}
\begin{split}
d&\ge \mathsf{rank}_{\mathcal{R}_{\mathbf{B}}^{\mathbb{R}}(d)}(\mathbf{B})\\
&=\min_{\|\S\|_0=\mathcal{R}_{\mathbf{B}}^{\mathbb{R}}(d)}\mathsf{rank}(\mathbf{U}\mathbf{V}^\top+n^{-14}\mathbf{G}+\S)\\
&\ge \min_{\|\S\|_0=\mathcal{R}_{\mathbf{B}}^{\mathbb{R}}(d)}\mathsf{rank}(n^{-14}\mathbf{G}+\S)-\mathsf{rank}(\mathbf{U}\mathbf{V}^\top)\\
&\ge \min_{\|\S\|_0=\mathcal{R}_{\mathbf{B}}^{\mathbb{R}}(d)}\mathsf{rank}(n^{-14}\mathbf{G}+\S)-d.
\end{split}
\end{equation*}
Therefore, $\min_{\|\S\|_0=\mathcal{R}_{\mathbf{B}}^{\mathbb{R}}(d)}\mathsf{rank}(n^{-14}\mathbf{G}+\S)\le 2d$, i.e., $\mathcal{R}_{\mathbf{B}}^{\mathbb{R}}(d)\ge \mathcal{R}_{n^{-14}\mathbf{G}}^{\mathbb{R}}(2d)$. By Lemma \ref{lemma: matrix rigidity over reals}, we have $\mathcal{R}_{n^{-14}\mathbf{G}}^{\mathbb{R}}(2d)=\Omega(n-2d)^2=\Omega(n^2)$. So $\mathcal{R}_{\mathbf{B}}^{\mathbb{R}}(d)=\Omega(n^2)$.

We now prove the case for arbitrary $\epsilon$. We construct two hard instances $\mathbf{C}$ and $\mathbf{D}$ by uniformly at random planting the above-mentioned hard instances $\mathbf{A}$ and $\mathbf{B}$ of dimension $\sqrt{\epsilon}n\times \sqrt{\epsilon}n$, respectively, and padding zeros everywhere else. Note that $\mathbf{D}$ being $\epsilon$-far from rank $d$ is equivalent to $\mathbf{B}$ being constant-far from rank $d$. Suppose that we can request $cd^2/\epsilon$ queries with a small absolute constant $c$ to distinguish the ranks of the hard instances $\mathbf{C}$ and $\mathbf{D}$, then in expectation (and with high probability by a Markov bound) we can request $cd^2$ queries of the hard instances $\mathbf{A}$ and $\mathbf{B}$ to distinguish their ranks, which leads to a contradiction.
\end{proof}




\subsection{Lower Bounds over Finite Fields in the Sensing Model}
\label{section: Lower Bounds over Finite Fields under the Sensing Model}

In this section, we provide a lower bound for the rank testing problem in the sensing model over any finite field $\mathbb{F}$. The sensing problem can query the underlying matrix $\mathbf{A}$ in the form of $\langle \mathbf{A},\mathbf{X}_{i} \rangle$ for any sequence of (randomized or deterministic) sensing matrices $\{\mathbf{X}_i\}$. The algorithms for querying entries of $\mathbf{A}$ are a special case of matrix sensing problem if we set $\mathbf{X}_i=\mathbf{e}_p\mathbf{e}_q^\top$ for some $(p,q)$. The problem can be stated more formally as follows:
\begin{problem}[Rank Testing with Parameter $(n,d,\epsilon)$ in the Sensing Model]
\label{problem: problem of property testing of rank in the sensing model}
Given a field $\mathbb{F}$ and a matrix $\mathbf{A}\in\mathbb{F}^{n\times n}$ which has one of promised properties:
\begin{itemize}
\item[$\mathsf{H0.}$]
$\mathbf{A}$ has rank at most $d$;
\item[$\mathsf{H1.}$]
$\mathbf{A}$ is $\epsilon$-far from having rank at most $d$, meaning that $\mathbf{A}$ requires changing at least an $\epsilon$-fraction of its entries to have rank at most $d$.
\end{itemize}
The problem is to design a property testing algorithm that outputs $\mathsf{H0}$ with probability $1$ if $\mathbf{A}\in \mathsf{H0}$, and output $\mathsf{H1}$ with probability at least 0.99 if $\mathbf{A}\in\mathsf{H1}$, with the least number of queries of the form $\langle\mathbf{A},\mathbf{X}_i\rangle$, where $\{\mathbf{X}_i\}$ is a sequence of sensing matrices.
\end{problem}


\begin{definition}[Ruzsa-Szemer$\acute{\text{e}}$di Graph]
A graph $G$ is an $(r,t)$-\emph{Ruzsa-Szemer$\acute{\text{e}}$di graph (RS graph for short)}, if and only if the set of edges of $G$ consists of $t$ pairwise disjoint induced matchings $M_1,\dots,M_t$, each of which is of size $r$.
\end{definition}

\begin{definition}[Boolean Hidden Hypermatching, $\mathsf{BHH}_{n,p}$]
The \emph{Boolean Hidden Hypermatching} problem is a one-way communication problem where Alice is given a boolean vector $\mathbf{x}\in\{0,1\}^n$ such that $n=2kp$ for some integer $k\ge 1$, and Bob is given a boolean vector $\mathbf{w}$ of length $n/p$ and a perfect $p$-hypermatching $\mathcal{M}$ on $n$ vertices such that each hyperedge contains $p$ vertices. Denote by $\mathcal{M}\mathbf{x}$ the length $n/p$ boolean vector $(\bigoplus_{1\le i\le p}\mathbf{x}_{\mathcal{M}_{1,i}},\bigoplus_{1\le i\le p}\mathbf{x}_{\mathcal{M}_{2,i}},\dots,\bigoplus_{1\le i\le p}\mathbf{x}_{\mathcal{M}_{n/p,i}})$ where $\{\mathcal{M}_{1,1},\dots,\mathcal{M}_{1,p}\},\dots,\{\mathcal{M}_{n/p,1},\dots,\mathcal{M}_{n/p,p}\}$ are the hyperedges of $\mathcal{M}$. It is promised that either $\mathcal{M}\mathbf{x}=\mathbf{w}$ or $\mathcal{M}\mathbf{x}=\overline\mathbf{w}$. The goal of the problem is for Bob to output \textup{\textbf{YES}} when $\mathcal{M}\mathbf{x}=\mathbf{w}$ and \textup{\textbf{NO}} when $\mathcal{M}\mathbf{x}=\overline\mathbf{w}$ ($\oplus$ stands for addition modulo 2).
\end{definition}

For our purpose, it is more convenient to focus on a special case of Boolean Hidden Hypermatching problem, namely, $\mathsf{BHH}_{n,p}^0$ where the vector $\mathbf{w}=\mathbf{0}^{n/p}$ ($p$ is an even integer) and Bob's task is to output \textbf{YES} if $\mathcal{M}\mathbf{x}=\mathbf{0}^{n/p}$ and output \textbf{NO} if $\mathcal{M}\mathbf{x}=\mathbf{1}^{n/p}$. It is known that we can reduce any instance of $\mathsf{BHH}_{n,p}$ to an instance of $\mathsf{BHH}_{2n,p}^0$ deterministically without any communication between Alice and Bob~\cite{bury2015sublinear,li2016approximating,verbin2011streaming}, by the following reduction.

\medskip
\noindent{\textbf{Reduction from $\mathsf{BHH}_{n,p}$ to $\mathsf{BHH}_{2n,p}^0$.}}
We reduce any instance of $\mathsf{BHH}_{n,p}$ to an instance of $\mathsf{BHH}_{2n,p}^0$ ($n=2kp$ for some integer $k$). Let $\mathcal{M}$ be a perfect $p$-hypermatching and $\mathbf{x}\in\{0,1\}^n$ in $\mathsf{BHH}_{n,p}$. Denote by $\mathbf{x}'=[\mathbf{x};\overline{\mathbf{x}}]$ the concatenation of $\mathbf{x}$ and $\overline\mathbf{x}$, where $\overline\mathbf{x}$ is the bitwise negation of $\mathbf{x}$. Let $\mathcal{M}'$ be the $p$-hypermatching in $\mathsf{BHH}_{2n,p}^0$.
Denote by $\{\mathbf{x}_1,\dots,\mathbf{x}_p\}\in\mathcal{M}$ the $l$-th hyperedge of $\mathcal{M}$ ($l\in[n/p]$). We add two hyperedges to $\mathcal{M}'$ as follows. If $\mathbf{w}_l=0$, we add $\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_p\}$ and $\{\overline{\mathbf{x}_1},\overline{\mathbf{x}_2},\dots,\overline{\mathbf{x}_p}\}$ to $\mathcal{M}'$; Otherwise, we add $\{\overline{\mathbf{x}_1},\mathbf{x}_2,\dots,\mathbf{x}_p\}$ and $\{\mathbf{x}_1,\overline{\mathbf{x}_2},\dots,\overline{\mathbf{x}_p}\}$ to $\mathcal{M}'$. Note that we flip an even number of bits when $\mathbf{w}_l=0$ and an odd number of bits when $\mathbf{w}_l=1$. This does not change the parity of each set as $p$ is even. Thus $\mathcal{M}\mathbf{x}=\mathbf{w}$ implies $\mathcal{M}'\mathbf{x}'=\mathbf{0}^{2n/p}$, and $\mathcal{M}\mathbf{x}=\overline{\mathbf{w}}$ implies $\mathcal{M}'\mathbf{x}'=\mathbf{1}^{2n/p}$.

\medskip
Previous papers
\cite{assadi2017estimating,bury2015sublinear,esfandiari2014streaming} used the $\mathsf{BHH}_{n,p}^0$ problem to prove lower bounds for estimating matching size in the data stream: given an instance $(\mathbf{x},\mathcal{M})$ in $\mathsf{BHH}_{n,p}^0$ (Denote by $\mathcal{D}_{\mathsf{BHH}}$ the hard distribution of $\mathsf{BHH}_{n,p}^0$), we create a graph $G(V\cup W,E)$ with $|V|=|W|=n$ via the following algorithm.


\begin{algorithm}[ht]
\caption{Reduction from $\mathsf{BHH}_{n,p}^0$ to the problem of estimating matching size in the data stream}
\label{algorithm: reduction from BHH to matching size}
\begin{algorithmic}[1]
\INPUT An instance from $\mathsf{BHH}_{n,p}^0$.
\OUTPUT A graph $G=(V\cup W,E)$.
\State For any $\mathbf{x}_i=1$, Alice adds an edge between $v_i$ and $w_i$ to $E$.
\State Bob adds to $E$ a clique between the vertices $w_i$ that belongs to the same hyperedge $\mathbf{e}$ in the $p$-hypermatching $\mathcal{M}$.
\end{algorithmic}
\end{algorithm}

We shall use the graph created by Algorithm \ref{algorithm: reduction from BHH to matching size} to build a hard distribution for our \emph{rank testing} problem. The following claim guarantees the correctness of this reduction from $\mathsf{BHH}_{n,p}^0$ to the problem of estimating matrix rank in a data stream.

\begin{lemma}
\label{lemma: reduction from BHH to rank testing}
Let $G(V\cup W,E)$ be the graph derived from an instance $(\mathbf{x},\mathcal{M})$ of $\mathsf{BHH}_{n,p}^0$ (for even integers $p$ and $n$) with the property that $\|\mathbf{x}\|_0=n/2$ (see Algorithm \ref{algorithm: reduction from BHH to matching size}). Denote by $\mathbf{A}$ the $2n\times 2n$ adjacency matrix of $G$. Then with probability at least $1-e^{-n/p^4}$, we have
\begin{itemize}
\item
if $\mathcal{M}\mathbf{x}=\mathbf{0}^{n/p}$ (i.e., \textup{$\mathsf{YES}$} case), then $\mathsf{rank}(\mathbf{A})\ge \frac{3n}{2}-\frac{n}{2p^2}$;
\item
if $\mathcal{M}\mathbf{x}=\mathbf{1}^{n/p}$ (i.e., \textup{$\mathsf{NO}$} case), then $\mathsf{rank}(\mathbf{A})\le \frac{3n}{2}-\frac{3n}{2p^2}$.
\end{itemize}
\end{lemma}

\begin{proof}
According to Algorithm \ref{algorithm: reduction from BHH to matching size}, the graph consists of $n$ vertices $v_1,\dots,v_n$ and $n/p$ cliques, together with edges which connect $v_i$'s with the cliques according to $\mathbf{x}\in\{0,1\}^n$. We call these latter edges `tentacles'.

Let $\mathbf{A}$ be the adjacency matrix of $G$ where both the rows and columns are indexed by the nodes in $G$. The diagonals of $\mathbf{A}$ are all zeros. For each pair $w$, $u$ of clique nodes in $G$, we have $\mathbf{A}_{w,u}=1$. For each `tentacle' pair $(v,w)$, $\mathbf{A}_{v,w}=1$. All other entries of $\mathbf{A}$ are zeros. Then $\mathbf{A}$ is an $n\times n$ block diagonal matrix, where each block $\mathbf{A}_{q_i}$ ($\mathbf{A}_{q_i}$ represents the block with $q_i$ `tentacles') is of the following form modulo permutations of rows and columns (The red rows and columns represent `tentacles'):
\begin{equation*}
\mathbf{A}_{q_i}=
\begin{bmatrix}
0 & 1 & \cdots & 1 & 1 & \red{1} & \red{0} & \red{\cdots}\\
1 & 0 & \cdots & 1 & 1 & \red{0} & \red{1} & \red{\cdots}\\
\vdots & \vdots & & \vdots & \vdots & \red{\vdots} & \red{\vdots}\\
1 & 1 & \cdots & 0 & 1 & \red{0} & \red{0} & \red{\cdots}\\
1 & 1 & \cdots & 1 & 0 & \red{0} & \red{0} & \red{\cdots}\\
\red{1} & \red{0} & \red{\cdots} & \red{0} & \red{0} & \red{0} & \red{0} & \red{\cdots}\\
\red{0} & \red{1} & \red{\cdots} & \red{0} & \red{0} & \red{0} & \red{0} & \red{\cdots}\\
\red{\vdots} & \red{\vdots} &  & \red{\vdots} & \red{\vdots} & \red{\vdots} & \red{\vdots}\\
\end{bmatrix}
\end{equation*}

According to the reduction from $\mathsf{BHH}_{n/2,p}$ to $\mathsf{BHH}_{n,p}^0$, the hypermatching in the hard distribution of $\mathsf{BHH}_{n,p}^0$ can be divided into $n/(2p)$ groups. Each group consists of two hyperedges such that the sum of the number of `tentacles' connecting to these two hyperedges is $p$ for every group, i.e., $(q_i,p-q_i)$ where $q_i$ is the number of `tentacles' connecting to one of hyperedges, which is either even ($\mathsf{YES}$ case) or odd ($\mathsf{NO}$ case) according to the promise. Moreover, the $q_i$'s are independent across the $n/p$ groups, because we can process each group one by one and after processing each group, the number of remaining `tentacles' decreases by $p$.

Let $r_{q_i}=\mathsf{rank}(\mathbf{A}_{q_i})$. Denote by $A=\mathbb{E}_{\mathsf{YES}}(r_{q_i}+r_{p-q_i})$ and $B=\mathbb{E}_{\mathsf{NO}}(r_{q_i}+r_{p-q_i})$, where $A$ and $B$ will be calculated later. Summing up $n/(2p)$ \emph{independent} groups and by the Chernoff bound, with probability at least $1-e^{-\delta^2\frac{n}{2p}A/2}$ and $1-e^{-\delta^2\frac{n}{2p}B/3}$, respectively, $\mathsf{rank}(\mathbf{A})\ge (1-\delta)\frac{n}{2p}A$ in the even case and $\mathsf{rank}(\mathbf{A})\le (1+\delta)\frac{n}{2p}B$ in the odd case, where $\delta>0$ is an absolute constant. We note that $A=3p$ and $B=3p-4/p$. Therefore, $\mathsf{rank}(\mathbf{A})\ge (1-\delta)3n/2$ in the even case and $\mathsf{rank}(\mathbf{A})\le (1+\delta)(3n/2-2n/p^2)$ in the odd case. Choosing $\delta=\frac{1}{3p^2}$ finishes the proof.
\end{proof}





In the following we shall set $\epsilon=\Theta(1/\log n)$ and $p=\Theta(\log n)$. Denote by $\mathsf{Matching}_{n,k,\epsilon}$ the \emph{$k$-player simultaneous communication} problem of estimating the size of maximum matching up to a factor of $(1\pm\epsilon)$, where the edges of an $n$-vertex input graph are partitioned across the $k$ players and the referee. For our purpose, we reduce from the problem of $\mathsf{Matching}_{n,k,\epsilon}$ to our problem of \emph{rank testing}. We use the hard distribution $\mathcal{D}_{\mathsf{M}}$ in Algorithm \ref{algorithm: hard distribution for matching} for $\mathsf{Matching}_{n,k,\epsilon}$. Notice that the hard instance of $\mathsf{BHH}_{r,p}^0$ in Step \ref{alg: BHH^0} is reduced from that of $\mathsf{BHH}_{r/2,p}$ as we did before in this section.

\begin{algorithm}[ht]
\caption{A construction of a hard distribution $\mathcal{D}_{\mathsf{M}}$ for $\mathsf{Matching}_{n,k,\epsilon}$}
\label{algorithm: hard distribution for matching}
\begin{algorithmic}[1]
\INPUT $r=N^{1-o(1)}$, $t=\frac{\binom{N}{2}-o(N^2)}{r}$, $k=\frac{N}{\epsilon r}$, $n=N+2r(k-1)$, and $p=\lfloor\frac{1}{8\epsilon}\rfloor$.
\State Fix an $(r,t)$-RS graph $G^{\mathsf{RS}}$ on $N$ vertices.
\State Pick $j^*\in[t]$ uniformly at random and draw a $\mathsf{BHH}_{r,p}^0$ instance $(\mathbf{x}^{(j^*)},\mathcal{M})$ from the distribution $\mathcal{D}_{\mathsf{BHH}}$. \label{alg: BHH^0}
\For{each player $P^{(i)}$ independently}
	\State (a) Let $G_i$ be the input graph of $P^{(i)}$, initialized by a copy of $G^{\mathsf{RS}}$ with vertices $V_i=[N]$.
	\State (b) Let $V_i^*$ be the set of vertices matched in the $j^*$-th induced matching of $G_i$. Change the induced matching $M_{J^*}^{\mathsf{RS}}$ of $G_i$ to $M_{j^*}:=M_{j^*}^{\mathsf{RS}}|_{\mathbf{x}^{(j^*)}}$.
	\State (c) For any $j\in[t]\backslash\{j^*\}$, draw a vector $\mathbf{x}^{(i,j)}\in\{0,1\}^r$ from the distribution $\mathcal{D}_{\mathsf{BHH}}$ for $\mathsf{BHH}_{r,p}^0$, and change the induced matching $M_j^{\mathsf{RS}}$ of $G_i$ to $M_j:=M_j^{\mathsf{RS}}|_{\mathbf{x}^{(i,j)}}$.
	\State (d) Create the family of $p$-cliques of $\mathcal{M}$ on the vertices $R(M_{j^*}^{\mathsf{RS}})$, and give the edges of the $p$-clique family to the referee.
\EndFor
\State Choose a random permutation $\sigma$ of $[n]$. For each player $P^{(i)}$, relabel $v$ to $\sigma(j)$ for each vertex $v$ in $V_i\backslash V_i^*$ with label $j\in [N-2r]$. Enumerate the vertices in $V_i^*$ from the one with the smallest label to the one with the largest label, and relabel the $j$-th vertex to $\sigma(N+(i-2)2r+j)$. Finally, let the vertices with the same label correspond to the same vertex.
\end{algorithmic}
\end{algorithm}

\begin{claim}
\label{claim: BHH and rank}
Let $I_{\mathsf{BHH}}$ be the embedded $\mathsf{BHH}_{r,p}^0$ instance $(\mathbf{x}^{(i)},\mathcal{M})$ in Algorithm \ref{algorithm: hard distribution for matching}. The adjacency matrix $\mathbf{A}\in\mathbb{F}^{n\times n}$ of the graph that is drawn from distribution $\mathcal{D}_{\mathsf{M}}$ (Algorithm \ref{algorithm: hard distribution for matching}) obeys
\begin{itemize}
\item[1.]
If $I_{\mathsf{BHH}}$ is a $\mathsf{YES}$ instance, then $\mathsf{rank}(\mathbf{A})\ge k(\frac{3r}{2}-\frac{r}{2p^2})$;
\item[2.]
If $I_{\mathsf{BHH}}$ is a $\mathsf{NO}$ instance, then $\mathsf{rank}(\mathbf{A})\le k(\frac{3r}{2}-\frac{3r}{2p^2})+N-2r$,
\end{itemize}
with probability at least $1-ke^{-n/p^4}$.
\end{claim}
\begin{proof}
Note that by construction, the adjacency matrix of the graph drawn from $\mathcal{D}_{\mathsf{M}}$ is a $k$-block-diagonal matrix together with some `junk' (area of size $(N-2r)\times n$ union $n\times (N-2r)$) outside the block area such that each block is an independent sample of the matrix $\mathbf{A}$ in Lemma \ref{lemma: reduction from BHH to rank testing}. The claim then is a straightforward result of Lemma \ref{lemma: reduction from BHH to rank testing}.
\end{proof}


\medskip
\noindent{\textbf{Reduction from $\mathsf{Matching}_{n,k,\epsilon}$ to Problem \ref{problem: problem of property testing of rank in the sensing model}.}} Given a hard graph instance $G$ of $\mathsf{Matching}_{n,k,\epsilon}$, we can estimate the maximum matching size of $G$ by testing the rank of the adjacency matrix $\mathbf{A}_G$ of $G$: If we can distinguish out $\mathsf{rank}(\mathbf{A}_G)\ge k(\frac{3r}{2}-\frac{r}{2p^2})$, we ouput that the matching size is strictly larger than $\frac{3N}{\epsilon}$; If we can distinguish out $\mathsf{rank}(\mathbf{A}_G)\le k(\frac{3r}{2}-\frac{3r}{2p^2})+N-2r$, we output that the matching size is smaller than $\frac{3N}{\epsilon}-3N$. The correctness for the reduction follows from Claim \ref{claim: BHH and rank}, the construction that the hard distributions of $\mathsf{Matching}_{n,k,\epsilon}$ and Problem \ref{problem: problem of property testing of rank in the sensing model} are derived from the same graph, and the fact that the matching size is strictly larger than $\frac{3N}{\epsilon}$ when $I_\mathsf{BHH}$ is a $\mathsf{YES}$ instance and is smaller than $\frac{3N}{\epsilon}-3N$ when $I_\mathsf{BHH}$ is a $\mathsf{NO}$ instance (see Claim 6.3, \cite{assadi2017estimating}).

\medskip
The hardness of $\mathsf{Matching}_{n,k,\epsilon}$ by the construction in Algorithm \ref{algorithm: hard distribution for matching} was proved in \cite{assadi2017estimating}.
\begin{theorem}[Theorem 10, \cite{assadi2017estimating}]
\label{theorem: hardness of maximum matching}
For any sufficiently large $n$ and sufficiently small $\epsilon<\frac{1}{2}$, there exists some $k=n^{o(1)}$ such that the distribution $\mathcal{D}_{\mathsf{M}}$ for $\mathsf{Matching}_{n,k,\epsilon}$ in Algorithm \ref{algorithm: hard distribution for matching} satisfies
\begin{equation*}
\mathsf{IC}_{\mathsf{SMP},\mathcal{D}_{\mathsf{M}}}^\delta(\mathsf{Matching}_{n,k,\epsilon})=n^{2-\mathcal{O}(\epsilon)},
\end{equation*}
where $\mathsf{IC}_{\mathsf{SMP},\mathcal{D}_{\mathsf{M}}}^\delta(\mathsf{Matching}_{n,k,\epsilon})$ is the information complexity of $\mathsf{Matching_{n,k,\epsilon}}$ in the multi-party number-in-hand simultaneous message passing model (SMP).
\end{theorem}

The following theorem summarizes the results in this section, providing a lower bound for Problem \ref{problem: problem of property testing of rank in the sensing model}.

\begin{theorem}
\label{theorem: lower bound over finite fields in general basis}
Any non-adaptive algorithm for Problem \ref{problem: problem of property testing of rank in the sensing model} over $\mathsf{GF}(p)$ requires $\Omega(d^2/\log p)$ queries.
\end{theorem}

\begin{proof}
We first discuss the case when $d=\Omega(n)$, where we will give an $\Omega(n^2)$ lower bound. Let $\mathbf{A}_G$ be the hard instance given by Algorithm \ref{algorithm: hard distribution for matching}. We want to find an $n\times n$ random matrix $\H'$ such that: (1) $\mathsf{rank}(\H'\mathbf{A})=\mathsf{rank}(\mathbf{A})$ (Multiplying $\H'$ does not change the rank of $\mathbf{A}$ so that testing $\mathbf{A}$ is equivalent to testing $\H'\mathbf{A}$); (2) $\mathbf{M}=\H'\mathbf{A}$ is rigid (Multiplying $\H'$ makes matrix $\mathbf{A}$ rigid). We now show how to do this. Let $\mathbf{B}$ be a random matrix such that we want to distinguish rank $n$ v.s. rank $n-n/\log^2 n$ for matrix $\mathbf{A}:=\mathbf{A}_G+\mathbf{B}$. Let $k = \mathsf{rank}(\mathbf{A})$, $\H$ be a $3nk/\delta\times n$ uniformly sampled matrix over $\mathsf{GF}(p)^{3nk/\delta\times n}$ and $\H'$ be the first $n$ rows of $\H$. One can see that any subset of at most $n$ rows of $\H$ has full rank with a large probability.


\medskip
\noindent{\textbf{Proof of (1).}} We note that $\mathsf{rank}(\H'\mathbf{A})\le k$. We will show that $\H'\mathbf{A}$ has rank $k$ with probability at least $1-\delta$. We will use the following lemma.
\begin{lemma}[Lemma 5.3, \cite{clarkson2009numerical}]
If $\mathcal{L}\subseteq \mathsf{GF}(p)^n$ is a $j$-dimensional linear subspace, and $\mathbf{A}$ has rank $k\ge j$, then the dimension of $\mathcal{L}_{\mathbf{A}}:=\{\mathbf{w}\in\mathsf{GF}(p)^n\mid \mathbf{w}^\top\mathbf{A}\in\mathcal{L}\}$ is at most $n-k+j$.
\end{lemma}
For $j<n$, consider the linear subspace $\mathcal{L}_j$ spanned by the first $j$ rows of $\H\mathbf{A}$. By the above lemma, the dimension of the subspace $\mathcal{L}_j':=\{\mathbf{w}\in\mathbb{R}^n\mid \mathbf{w}^\top\mathbf{A}\in\mathcal{L}_j\}$ is at most $n-k+j$. Given that the rows of $\H$ are linearly independent with high probability, at most $n-k+j$ of them can be in $\mathcal{L}_j'$. Thus the probability that $\H_{(j+1),:}'\mathbf{A}$ is not in $\mathcal{L}_j$ is at least $1-(n-k+j)/(3nk/\delta-j)$, and the probability that all such events hold, for $j=0,\dots,k-1$, is at least
\begin{equation*}
\left(1-\frac{n}{3nk/\delta-k}\right)^k= \left(1-\frac{1}{k}\frac{\delta/3}{1-\delta/(3n)}\right)^k\ge 1-\frac{\delta}{2}
\end{equation*}
for small $\delta$. All such independence events occur if and only if $\H'_{1:k,:}\mathbf{A}$ has rank $k$. Therefore, the probability that $\H'\mathbf{A}$ is of rank $k$ is at least $1-\delta/2$.

\medskip
\noindent{\textbf{Proof of (2).}} We need the following result on matrix rigidity.

\begin{lemma}[Matrix Rigidity, Theorem 6.4, \cite{valiant1977graph}]
\label{lemma: matrix rigidity over GF(p)}
The fraction of matrices over $\mathsf{GF}(p)^{n\times n}$ with matrix rigidity $\mathcal{R}^{\mathsf{GF}(p)}(r)=\Omega((n-r)^2/\log_p n)$ is at least $0.99$, for $r<n-\sqrt{2n\log_p 2+\log n}$.
\end{lemma}

For uniform matrix $\H'$, we note that $\H'\mathbf{A}$ is uniform as well: for any given matrix $\mathbf{T}$ in $\mathsf{GF}(p)^{n\times n}$
\begin{equation*}
\Pr_{\H'\sim\mathsf{Unif}}[\H'\mathbf{A}=\mathbf{T}]=\Pr_{\H'\sim\mathsf{Unif}}[\H'=\mathbf{T}\mathbf{A}^{-1}]=\left(\frac{1}{p}\right)^{kn}.
\end{equation*}
Then by Lemma \ref{lemma: matrix rigidity over GF(p)}, $\mathcal{R}_{\H'\mathbf{A}}^{\mathsf{GF}(p)}(n-n/\log n)=\Omega(n^2/\log^2 n)$ with high probability.

Now we are ready to prove the hardness of Problem \ref{problem: problem of property testing of rank in the sensing model} with parameter $(n,n-\frac{n}{\log^2(n)},\frac{1}{\log^4 (n)\log_p(n)})$. For any non-adaptive algorithm $\mathcal{A}_{test}$ for Problem \ref{problem: problem of property testing of rank in the sensing model} with $\epsilon=1/\log n$ and $d=n-n/\log n$, assume that the required number of queries is $q$. We use such algorithms to estimate the maximum matching size by our reduction. Given a graph $G$ with maximum matching size $\ge 3N/\epsilon$ v.s. $\le 3N/\epsilon-3N$. We know that the rank of $\mathbf{A}:=\mathbf{A}_G+\mathbf{B}$ is of rank $n$ v.s. $n-n/\log^2 n$. By left multiplying matrix $\mathbf{A}$ with above-mentioned $\H'$, the rank of resulting matrix $\H'\mathbf{A}$ remains the same and is of rigidity $\mathcal{R}_{\mathbf{B}}^{\mathsf{GF}(p)}(n-n/\log^2 n)=\Omega(n^2/(\log^4 (n)\log_p (n)))$ according to properties (1) and (2) that we have proven. By assumption, $\mathcal{A}_{test}$ can distinguish rank $n$ from rank $n-n/\log^2 n$ for matrix $\H'\mathbf{A}$ in $q$ queries with high probability. So $\mathcal{A}_{test}$ can be used to compute the maximum matching size with $(1\pm 1/\log n)$-approximation rate with $\mathcal{O}(q\log p)$ bits of communication. By Theorem \ref{theorem: hardness of maximum matching}, we have $q\log p=\Omega(n^2)$, which implies that $q=\Omega(n^2/\log p)$.

We now prove the lower bound for arbitrary $d$. Let $\mathbf{1}\in\mathsf{GF}(p)^{\frac{n(1-1/\log d)}{d}\times \frac{n(1-1/\log d)}{d}}$ be the all-ones matrix and $\mathbf{A}\in\mathsf{GF}(p)^{\frac{d}{1-1/\log d}\times \frac{d}{1-1/\log d}}$ be the above hard instance. We do the Kronecker product to generate matrix $\mathbf{C}=\mathbf{1}\otimes\mathbf{A}\in\mathsf{GF}(p)^{n\times n}$. If there exists a non-adaptive algorithm $\mathcal{A}_{test}$ that can correctly test whether $\mathbf{C}$ has rank at most $d$ or is far from having rank $d$ with $cd^2/\log p$ queries and high probability for an absolute constant $c$, the algorithm $\mathcal{A}_{test}$ can also test whether $\mathbf{A}$ has rank at most $d$ or is far from having rank $d$ with $cd^2/\log p$ queries by outputting the same result as testing $\mathbf{C}$. This leads to a contradiction.
\end{proof}

Theorem \ref{theorem: lower bound over finite fields in general basis} is tight up to a logarithmic factor. Indeed, there is an $\mathcal{O}(d^2)$ upper bound for every field, independent of $\epsilon$, as follows. If $\mathbf{A}$ is an (unknown) $n\times n$ matrix and has rank at least $d+1$, the matrix $\S\mathbf{A}\mathbf{T}$ will have rank at least $d+1$ with high probability for random $\S$ of $d+1$ rows and $\mathbf{T}$ of $d+1$ columns; furthermore, this matrix product can be computed in the matrix sensing model because $(\S\mathbf{A}\mathbf{T})_{i,j}$ can be written as ${\langle \mathbf{A}, \S_{i,:}\mathbf{T}_{:,j}\rangle}_{i,j}$, which is in the form of matrix sensing. Computing $\S\mathbf{A}\mathbf{T}$ uses only $(d+1)^2$ measurements instead of the $d^2/\epsilon$ we need for reading entries.










\section{Non-Adaptive Stable Rank Testing}

In this section and onwards, we study the problem of non-adaptively testing numerical properties of real-valued matrices. They can be studied under a unified framework in this section.

Roughly, our analytical framework reduces the testing problem to a sequence of estimation problems \emph{without involving $\mathsf{poly}(n)$ in the sample complexity}. Our framework consists of two levels of estimation: (1) a constant-factor approximation to the statistic $X$ of interest (e.g., stable rank), and (2) a more accurate $(1\pm\tau)$-approximation to $X$.




\begin{definition}[Stable Rank]
The stable rank of $\mathbf{A}$ is defined by $\mathsf{srank}(\mathbf{A})=\|\mathbf{A}\|_F^2/\|\mathbf{A}\|^2$, where $\|\mathbf{A}\|_F$ is the Frobenius norm and $\|\mathbf{A}\|$ the spectral norm (largest singular value).
\end{definition}

\begin{problem}[Stable Rank Testing in the Entry Model]
Let $\mathbf{A}\in\mathbb{R}^{n\times n}$ be a matrix which satisfies $\|\mathbf{A}\|_\infty\leq 1$ and has one of promised properties:
\begin{itemize}
\item[$\mathsf{H0.}$]
$\mathbf{A}$ has stable rank at most $d$;
\item[$\mathsf{H1.}$]
$\mathbf{A}$ is $\epsilon/d$-far from having stable rank at most $d$, meaning that $\mathbf{A}$ requires changing at least an $\epsilon/d$-fraction of its entries to have stable rank at most $d$.
\end{itemize}
The problem is to design a property testing algorithm that outputs $\mathsf{H0}$ with probability at least $0.99$ if $\mathbf{A}\in \mathsf{H0}$, and output $\mathsf{H1}$ with probability at least 0.99 if $\mathbf{A}\in\mathsf{H1}$, with the least number of queried entries.
\end{problem}

\subsection{Upper Bounds}

\comment{
\begin{lemma}
\label{lemma: f and 2 norm when far from stable rank d}
If matrix $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$ and $\|\mathbf{A}\|_\infty=1$, then
\begin{equation*}
\|\mathbf{A}\|_F^2> \left(\frac{\epsilon n}{d}-1\right)(d-1),
\end{equation*}
and
\begin{equation*}
\|\mathbf{A}\|^2< \left[1+\left(1-\frac{1}{d}\right)\frac{1}{n}\left(\frac{\epsilon n}{d}-1\right)\right]\frac{\|\mathbf{A}\|_F^2}{d}+\left(\frac{n}{d}-1\right)\left(\frac{\epsilon n}{d}-1\right).
\end{equation*}
\end{lemma}

\begin{proof}
Suppose that $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$. Let $\mathbf{x}\in \mathbb{S}^{n-1}$ be the unit vector such that $\|\mathbf{A}\|=\|\mathbf{A}\mathbf{x}\|_2$, i.e., $\mathbf{x}$ is the right singular vector corresponding to the largest singular value. Without loss of generality, we assume that $\langle\mathbf{A}_{1,:},\mathbf{x}\rangle^2\le \langle\mathbf{A}_{2,:},\mathbf{x}\rangle^2\le...\le \langle\mathbf{A}_{n,:},\mathbf{x}\rangle^2$. Let $m=\lceil\epsilon n/d\rceil-1$. Replacing each $A_{i,:}$, $i\in [m]$ with vector $\mathbf{x}^\top/\|\mathbf{x}\|_\infty$ forms a new matrix $\mathbf{B}$. Since $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$ and $\|\mathbf{A}\|_\infty=1$, it must hold that $\mathsf{srank}(\mathbf{B})>d$ and $\|\mathbf{B}\|_\infty=1$.

By our construction of $\mathbf{B}$, we have $\|\mathbf{B}\|^2\ge \frac{m}{\|\mathbf{x}\|_\infty^2}$ and $\|\mathbf{B}\|_F^2\le \|\mathbf{A}\|_F^2+\frac{m}{\|\mathbf{x}\|_\infty^2}$. Therefore,
\begin{equation*}
d<\mathsf{srank}(\mathbf{B})=\frac{\|\mathbf{B}\|_F^2}{\|\mathbf{B}\|^2}\le \frac{\|\mathbf{A}\|_F^2+\frac{m}{\|\mathbf{x}\|_\infty^2}}{\frac{m}{\|\mathbf{x}\|_\infty^2}},
\end{equation*}
which implies that
\begin{equation*}
\|\mathbf{A}\|_F^2> \frac{m(d-1)}{\|\mathbf{x}\|_\infty^2}\ge \left(\frac{\epsilon n}{d}-1\right)(d-1).
\end{equation*}
Here the last inequality holds because $\|\mathbf{x}\|_\infty\le 1$.

We now prove the second conclusion. Notice that
\begin{equation*}
S_m:=\sum_{i=1}^m\langle\mathbf{A}_{i,:},\mathbf{x}\rangle^2 \le \frac{m}{n} \sum_{i=1}^n\langle\mathbf{A}_{i,:},\mathbf{x}\rangle^2=\frac{m}{n}\|\mathbf{A}\|^2< \frac{m}{n}\frac{\|\mathbf{A}\|_F^2}{d},
\end{equation*}
where the last inequality holds because $\mathsf{srank}(\mathbf{A})=\frac{\|\mathbf{A}\|_F^2}{\|\mathbf{A}\|^2}>d$ by assumption. We also observe that
\begin{equation*}
\|\mathbf{B}\|_F^2\le \|\mathbf{A}\|_F^2-\sum_{i=1}^m\|\mathbf{A}_{i,:}\|_2^2+\frac{m}{\|\mathbf{x}\|_\infty^2}\le \|\mathbf{A}\|_F^2-S_m+\frac{m}{\|\mathbf{x}\|_\infty^2},
\end{equation*}
where the last inequality holds since $S_m=\sum_{i=1}^m\langle\mathbf{A}_{i,:},\mathbf{x}\rangle^2\le \sum_{i=1}^m \|\mathbf{A}_{i,:}\|_2^2$ by the Cauchy-Schwartz inequality.
Because
\begin{equation*}
\|\mathbf{B}\|^2\ge \|\mathbf{B}\mathbf{x}\|_2^2= \sum_{i=m+1}^n \langle\mathbf{A}_{i,:},\mathbf{x}\rangle^2+m\left\langle\frac{\mathbf{x}}{\|\mathbf{x}\|_\infty},\mathbf{x}\right\rangle^2=\|\mathbf{A}\|^2-S_m+\frac{m}{\|\mathbf{x}\|_\infty^2},
\end{equation*}
it follows that
\begin{equation*}
d<\mathsf{srank}(\mathbf{B})=\frac{\|\mathbf{B}\|_F^2}{\|\mathbf{B}\|^2}\le \frac{\|\mathbf{A}\|_F^2-S_m+\frac{m}{\|\mathbf{x}\|_\infty^2}}{\|\mathbf{A}\|^2-S_m+\frac{m}{\|\mathbf{x}\|_\infty^2}}.
\end{equation*}
Thus
\begin{equation*}
\|\mathbf{A}\|^2< \left[1+\left(1-\frac{1}{d}\right)\frac{1}{n}\left(\frac{\epsilon n}{d}-1\right)\right]\frac{\|\mathbf{A}\|_F^2}{d}+\left(\frac{n}{d}-1\right)\left(\frac{\epsilon n}{d}-1\right).
\end{equation*}
\end{proof}
}

\comment{
\begin{lemma}
\label{lemma: concentration}
Let $\widetilde\mathbf{A}\in\mathbb{R}^{n\times n}$ be the matrix which uniformly samples $q$ rows of $\mathbf{A}$. Denote by $X=\frac{n}{q}\|\widetilde\mathbf{A}\|_F^2$. Then it holds that $|X-\|\mathbf{A}\|_F^2|\le \frac{1}{8}(1-\frac{1}{d})^2\epsilon n^2$ with probability at least $0.9$.
\end{lemma}

\begin{proof}
By the Chernoff bound, sampling $q$ rows uniformly gives
\begin{equation*}
\Pr\left[\left|X-\|\mathbf{A}\|_F^2\right|\le \frac{1}{8}\left(1-\frac{1}{d}\right)^2\epsilon n^2\right]\ge \Pr\left[\left|X-\|\mathbf{A}\|_F^2\right|\le \frac{1}{8}\left(1-\frac{1}{d}\right)^2\epsilon n^2\right].
\end{equation*}
\end{proof}
}


\begin{lemma}[{\cite[Theorem 1.8]{rudelson2007sampling}}]
\label{Lemma: Vershynin}
Let $\mathbf{A}$ be an $n\times n$ matrix. Let $\mathcal{Q}$ be a uniformly random subset of $\{1,2,\dots,n\}$ of expected cardinality $q$ with replacement.
Then
\begin{equation*}
\bbE\left\|\mathbf{A}|_{\mathcal{Q}}\right\|\lesssim \sqrt{\frac{q}{n}}\|\mathbf{A}\|+\sqrt{\log q}\|\mathbf{A}\|_{(n/q)},
\end{equation*}
where $\mathbf{A}|_{\mathcal{Q}}=(\mathbf{A}_{i,j})_{i\in\mathcal{Q},j\le n}$ is a random row-submatrix of $\mathbf{A}$, and $\|\mathbf{A}\|_{(n/q)}$ is the average of $n/q$ biggest Euclidean lengths of the columns of $\mathbf{A}$.
\end{lemma}

\comment{
\begin{proof}
Denote by $\delta_1,\delta_2,\dots,\delta_n$ the $\{0,1\}$-valued independent random variables with $\bbE\delta_i=p_i$. Thus our random set is $Q=\{j\mid \delta_j=1\}$.

Denote by $\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_n$ the columns of $\mathbf{A}$. So
\begin{equation*}
\mathbf{A}=\sum_{j=1}^n \mathbf{e}_j\otimes \mathbf{x}_j,\qquad \mathbf{A}|_Q=\sum_{j=1}^n \delta_j \mathbf{e}_j\otimes\mathbf{x}_j.
\end{equation*}
The spectral norm of $\mathbf{A}$ is
\begin{equation*}
\|\mathbf{A}\|=\|\mathbf{A}\A^\top\|^{1/2}=\left\|\sum_{j=1}^n \mathbf{x}_j\otimes\mathbf{x}_j\right\|^{1/2},
\end{equation*}
and the spectral norm of $\mathbf{A}|_Q$ is
\begin{equation*}
\|\mathbf{A}|_Q\|=\left\|\sum_{j=1}^n\delta_j\mathbf{x}_j\otimes \mathbf{x}_j\right\|^{1/2}.
\end{equation*}
Let
\begin{equation*}
E=\bbE\|\mathbf{A}|_Q\|.
\end{equation*}
The symmetrization argument yields
\begin{equation*}
\begin{split}
E&=\bbE\left\|\sum_{j=1}^n(\delta_j-\bbE\delta_j+\bbE\delta_j)\mathbf{x}_j\otimes \mathbf{x}_j\right\|^{1/2}\\
&\le\mathbb{E}\left\|\sum_{j=1}^n(\delta_j-\bbE\delta_j)\mathbf{x}_j\otimes \mathbf{x}_j\right\|^{1/2}+\left\|\sum_{j=1}^n \bbE\delta_j\mathbf{x}_j\otimes \mathbf{x}_j\right\|^{1/2}\\
&\le \bbE_\delta\left(\bbE_\epsilon\left\|\sum_{j=1}^n\epsilon_j\delta_j\mathbf{x}_j\otimes\mathbf{x}_j\right\|\right)^{1/2}+\frac{}{}
\end{split}
\end{equation*}
\end{proof}
}



\begin{lemma}
\label{Lemma: infty norm of uniform sampling from unit sphere}
Let $\mathbf{x}\sim\mathsf{Unif}(\mathbb{S}^{n-1})$. Then with probability at least $1-n^{-2}$, we have $\|\mathbf{x}\|_\infty\le \sqrt{\frac{2\log n}{n}}$.
\end{lemma}

\comment{
\begin{theorem}
Suppose that $d/\epsilon\ge 2$. Then Algorithm \ref{algorithm: algorithm for the stable rank testing problem} is a correct algorithm for the stable rank testing problem with failure probability at most $\frac{1}{3}$ in the entry model. It reads $\widetilde\mathcal{O}(\frac{d^6}{\epsilon^6})$ entries.
\end{theorem}

\begin{proof}
When $\mathbf{A}$ is far from being stable rank at most $d$, we claim that $\|\mathbf{A}\|_F^2\ge \epsilon n^2(1-\frac{1}{d})$. Otherwise, changing the first $\frac{\epsilon n}{d}$ rows of $\mathbf{A}$ to be all-one vectors $\mathbf{1}^\top$ leads to a new matrix $\mathbf{B}$ such that $\|\mathbf{B}\|^2\ge \frac{\epsilon n^2}{d}$ and $\|\mathbf{B}\|_F^2\le \epsilon n^2(1-\frac{1}{d})+\frac{\epsilon n^2}{d}=\epsilon n^2$, leading to $\mathsf{srank}(\mathbf{B})\le d$, a contradiction. By the Chernoff bound, it holds that with probability at least $1-e^{-\tau^2\|\mathbf{A}\|_F^2/3}\ge 1-e^{-\tau^2\epsilon n^2(1-1/d)/3}$, by sampling $q$ rows from $\mathbf{A}$, the resulting matrix $\mathbf{A}_{\mathsf{row}}$ satisfies
\begin{equation}
\label{equ: F norm}
(1-\tau)\|\mathbf{A}\|_F^2\le \frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|_F^2\le (1+\tau)\|\mathbf{A}\|_F^2.
\end{equation}
Conditioning on this event, by sampling $q$ columns from $\mathbf{A}_{\mathsf{row}}$ and using Chernoff bound again, with probability at least $1-e^{-\tau^2\epsilon n^2(1-1/d)/3}-e^{-\tau^2\|\mathbf{A}_{\mathsf{row}}\|^2/3}\ge 1-2e^{-\tau^2\epsilon n^2(1-1/d)q(1-\tau)/(3n)}$ we have
\begin{equation}
\label{equ: F norm entry level}
(1-\tau)^2\|\mathbf{A}\|_F^2\le (1-\tau)\frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|_F^2\le X\le (1+\tau)\frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|_F^2\le (1+\tau)^2\|\mathbf{A}\|_F^2.
\end{equation}

\comment{
Conditioned on the event $|X-\|\mathbf{A}\|_F^2|\le \frac{1}{8}(1-\frac{1}{d})^2\epsilon n$ in Lemma \ref{lemma: concentration}, it holds that
\begin{equation*}
X\ge \|\mathbf{A}\|_F^2-\frac{1}{8}\left(1-\frac{1}{d}\right)^2\epsilon n\ge \frac{9}{10}\epsilon n^2\left(1-\frac{1}{d}\right).
\end{equation*}
Therefore, Algorithm \ref{algorithm: algorithm for the stable rank testing problem} is correct on Line 5.

To prove the correctness of Lines 8 and 10, we only need to discuss the case when $X\ge \frac{9}{10}\epsilon n^2\left(1-\frac{1}{d}\right)$. So
\begin{equation*}
\|\mathbf{A}\|_F^2\ge X-\frac{1}{8}\left(1-\frac{1}{d}\right)^2\epsilon n\ge \frac{8}{10}\epsilon n^2\left(1-\frac{1}{d}\right).
\end{equation*}
Let $\eta:=\frac{c\epsilon n}{\|\mathbf{A}\|_F^2}\le \frac{10cd}{8(d-1)}=:\eta'$. We have
\begin{equation}
\left(1-\frac{\tau\eta'}{c}\right)\|\mathbf{A}\|_F^2\le X\le \left(1+\frac{\tau\eta'}{c}\right)\|\mathbf{A}\|_F^2.
\end{equation}
}

Let $c_1>1$ be a value to be specified later. We discuss two separate cases.




\medskip
\noindent{\textbf{Case (i). $\mathsf{srank}(\mathbf{A})> c_1 d$.}}

Let $\mathbf{U}$ be a uniformly random $n\times n$ orthogonal matrix. Note that $\|\mathbf{A}_{\mathsf{row}}\|=\|\mathbf{A}_{\mathsf{row}}\mathbf{U}\|$, and $(\mathbf{A}\mathbf{U})_{i,:}=\mathbf{A}_{i,:}\mathbf{U}$ uniformly distributes on $\|\mathbf{A}_{i,:}\|_2\cdot\mathbb{S}^{n-1}$. So $\|\mathbf{A}_{i,:}\mathbf{U}\|_\infty^2\le 2\|\mathbf{A}_{i,:}\mathbf{U}\|_2^2\log (n)/n$ for all $i$ with probability at least $1-1/n^2$ by Lemma \ref{Lemma: infty norm of uniform sampling from unit sphere}. Therefore, with probability at least $1-1/n$ by union bound over all rows, $\|\mathbf{A}\mathbf{U}\|_{\mathsf{col}}^2\le 2\|\mathbf{A}\|_F^2\log (n)/n$, where $\|\mathbf{A}\|_{\mathsf{col}}$ represents the maximum norm among all columns of $\mathbf{A}$. By Lemma \ref{Lemma: Vershynin},
\begin{equation*}
\bbE\|\mathbf{A}_{\mathsf{row}}\|\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F
\end{equation*}
for absolute constants $C_1$ and $C_2$, and by the Markov bound, with probability at least $0.9$,
\begin{equation*}
\begin{split}
\|\mathbf{A}_{\mathsf{row}}\|&\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\\
&\le C_1\sqrt{\frac{q}{n}}\frac{\|\mathbf{A}\|_F}{\sqrt{c_1 d}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\\
&\le \frac{1}{\sqrt{1-\tau}}\left(C_1\sqrt{\frac{q}{c_1d}}+C_2\sqrt{\log q\log n}\right)\sqrt{\frac{X}{n}}.
\end{split}
\end{equation*}
Conditioning on this event, by applying the same argument on the column sampling of $\mathbf{A}_{\mathsf{row}}$, we have
\begin{equation*}
\begin{split}
\|\widetilde\mathbf{A}\|&\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}_{\mathsf{row}}\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}_{\mathsf{row}}\|_F\\
&\le C_1\sqrt{\frac{q}{n}} \frac{1}{\sqrt{1-\tau}}\left(C_1\sqrt{\frac{q}{c_1d}}+C_2\sqrt{\log q\log n}\right)\sqrt{\frac{X}{n}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\sqrt{\frac{q}{1-\tau}}\sqrt{\frac{X}{n}},
\end{split}
\end{equation*}
where $\widetilde\mathbf{A}$ is the matrix after column sampling of $\mathbf{A}_{\mathsf{row}}$.
On the other hand, when $\mathsf{srank}(\mathbf{A})\le d$, by setting $\beta=\|\mathbf{A}\|_F^2/n^2$ and applying Corollary \ref{lemma: Ismail}, we have with probability at least $0.9$ that
\begin{equation}
\label{equ: row operator norm}
\|\mathbf{A}_{\mathsf{row}}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\|\mathbf{A}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\frac{\|\mathbf{A}\|_F}{\sqrt{d}}\ge \sqrt{\frac{1-\tau}{1+\tau}}\sqrt{\frac{q}{n}}\sqrt{\frac{X}{d}}.
\end{equation}
Conditioning on this event and applying Corollary \ref{lemma: Ismail} to column sampling of $\mathbf{A}_{\mathsf{row}}$, we have
\begin{equation*}
\|\widetilde\mathbf{A}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\|\mathbf{A}_{\mathsf{row}}\|\ge \frac{1-\tau}{\sqrt{1+\tau}}\frac{q}{n}\sqrt{\frac{X}{d}},
\end{equation*}
where we have used the fact that (by Eqns. \eqref{equ: F norm} and \eqref{equ: row operator norm})
\begin{equation}
\label{equ: stable rank of row sampling}
\mathsf{srank}(\mathbf{A}_{\mathsf{row}})=\frac{\|\mathbf{A}_{\mathsf{row}}\|_F^2}{\|\mathbf{A}_{\mathsf{row}}\|^2}\le \frac{1+\tau}{1-\tau}\mathsf{srank}(\mathbf{A})\le \frac{1+\tau}{1-\tau}d.
\end{equation}
By setting $c_1$ larger than a constant times $(1+\tau)/(1-\tau)^3$, we have
\begin{equation*}
\frac{1-\tau}{\sqrt{1+\tau}}\frac{q}{n}\sqrt{\frac{X}{d}} > C_1\sqrt{\frac{q}{n}} \frac{1}{\sqrt{1-\tau}}\left(C_1\sqrt{\frac{q}{c_1d}}+C_2\sqrt{\log q\log n}\right)\sqrt{\frac{X}{n}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\sqrt{\frac{q}{1-\tau}}\sqrt{\frac{X}{n}}.
\end{equation*}
Thus we can distinguish the two cases of $\mathsf{srank}(\mathbf{A})\le d$ and $\mathsf{srank}(\mathbf{A})$ far from being at most $d$.

\medskip
\noindent{\textbf{Case (ii). $\mathsf{srank}(\mathbf{A})\le c_1 d$.}}

Note that in this case, $\|\mathbf{A}\|^2\ge \frac{\|\mathbf{A}\|_F^2}{c_1 d}\ge \frac{\epsilon n^2(1-\frac{1}{d})}{c_1d}$. Let $\beta=\|\mathbf{A}\|_F^2/n^2$. So $\beta \|\mathbf{A}_{i,:}\|_2^2/\|\mathbf{A}\|_F^2\le 1/n$ for all $i$'s, namely, uniform sampling obeys the condition of Corollary \ref{lemma: Ismail}. It then follows from Corollary \ref{lemma: Ismail} that with probability at least $0.9$,
\begin{equation*}
(1-\tau)\|\mathbf{A}\|^2\le \frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|^2\le (1+\tau)\|\mathbf{A}\|^2.
\end{equation*}
Conditioning on this event, by applying Corollary \ref{lemma: Ismail} again to the column sampling of $\mathbf{A}_{\mathsf{row}}$, we have with high probability,
\begin{equation}
\label{equ: small stable rank, operator norm}
(1-\tau)^2\|\mathbf{A}\|^2\le (1-\tau)\frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|^2\le \frac{n^2}{q^2}\|\widetilde\mathbf{A}\|^2\le (1+\tau)\frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|^2\le (1+\tau)^2\|\mathbf{A}\|^2,
\end{equation}
where we have used the fact that $\mathsf{srank}(\mathbf{A}_{\mathsf{row}})\le \mathcal{O}(d)$ by Eqn. \eqref{equ: stable rank of row sampling}. Combining Eqn. \eqref{equ: small stable rank, operator norm} with Eqn. \eqref{equ: F norm entry level}, we obtain an estimation of stable rank of $\mathbf{A}$ from $\mathsf{srank}(\widetilde\mathbf{A})$:
\begin{equation}
\label{equ: stable rank estimator}
(1-\Theta(\tau))\cdot\mathsf{srank}(\mathbf{A})\le \mathsf{srank}(\widetilde\mathbf{A})\le (1+\Theta(\tau))\cdot\mathsf{srank}(\mathbf{A}).
\end{equation}

We now show that we can distinguish the two cases of $\mathsf{srank}(\mathbf{A})\le d$ and $\mathsf{srank}(\mathbf{A})$ far from being at most $d$ by the above estimator $\mathsf{srank}(\widetilde\mathbf{A})$. Let $\mathbf{x}\in \mathbb{S}^{n-1}$ be the unit vector such that $\|\mathbf{A}\|=\|\mathbf{A}\mathbf{x}\|_2$, i.e., $\mathbf{x}$ is the right singular vector corresponding to the largest singular value. Decompose $\mathbf{x}$ as $\mathbf{x}_H+\mathbf{x}_L$, where $\mathbf{x}_H$ represents the ``heavy'' part of $\mathbf{x}$, i.e., zeroing out those entries whose values are smaller than a hard threshold $x_0=\Theta(\sqrt{\frac{d}{n}})$, and $\mathbf{x}_L$ represents the ``light'' part of $\mathbf{x}$ defined by $\mathbf{x}_L=\mathbf{x}-\mathbf{x}_H$. We note that $\mathbf{x}_H$ is sparse, i.e., $\|\mathbf{x}_H\|_0\le 1/x_0^2$, because $\|\mathbf{x}\|^2=1$. So
\begin{equation*}
\begin{split}
\|\mathbf{A}\|&=\|\mathbf{A}\mathbf{x}\|_2\\
&\le \|\mathbf{A}\mathbf{x}_H\|_2+\|\mathbf{A}\mathbf{x}_L\|_2\\
&\le \sqrt{\sum_{i\in H} \langle\mathbf{A}_{i,:},\mathbf{x}_H\rangle^2}+\|\mathbf{A}\mathbf{x}_L\|_2\\
&\le \frac{\sqrt{n}}{x_0}+\|\mathbf{A}\mathbf{x}_L\|_2\\
&\le \frac{\sqrt{n}}{x_0}+\|\mathbf{A}\|\|\mathbf{x}_L\|_2.
\end{split}
\end{equation*}
Therefore, $\|\mathbf{x}_L\|_2\ge 1-\frac{\sqrt{n}}{x_0\|\mathbf{A}\|}\ge 1-\frac{\sqrt{n}c_1d}{x_0\epsilon n^2(1-1/d)}=\Omega(1)$.
Suppose that $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$. Without loss of generality, we assume that $\langle\mathbf{A}_{1,:},\mathbf{x}\rangle^2\le \langle\mathbf{A}_{2,:},\mathbf{x}\rangle^2\le...\le \langle\mathbf{A}_{n,:},\mathbf{x}\rangle^2$. Let $m=\lceil\epsilon n/d\rceil-1$. Replacing each $\mathbf{A}_{i,:}$, $i\in [m]$ with vector $\mathbf{x}_L^\top/x_0$ forms a new matrix $\mathbf{B}$. Since $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$, it must hold that $\mathsf{srank}(\mathbf{B})>d$ and $\|\mathbf{B}\|_\infty\le 1$.

Notice that
\begin{equation}
\label{equ: S_m}
S_m:=\sum_{i=1}^m\langle\mathbf{A}_{i,:},\mathbf{x}\rangle^2 \le \frac{m}{n} \sum_{i=1}^n\langle\mathbf{A}_{i,:},\mathbf{x}\rangle^2=\frac{m}{n}\|\mathbf{A}\|^2< \frac{m}{n}\frac{\|\mathbf{A}\|_F^2}{d}\le \frac{2\epsilon\|\mathbf{A}\|_F^2}{d^2},
\end{equation}
where the penultimate inequality holds because $\mathsf{srank}(\mathbf{A})=\frac{\|\mathbf{A}\|_F^2}{\|\mathbf{A}\|^2}>d$ by assumption. We also observe that
\begin{equation}
\label{equ: F norm of B}
\|\mathbf{B}\|_F^2\le \|\mathbf{A}\|_F^2-\sum_{i=1}^m\|\mathbf{A}_{i,:}\|_2^2+\frac{m\|\mathbf{x}_L\|_2^2}{x_0^2}\le \|\mathbf{A}\|_F^2-S_m+\frac{m}{x_0^2},
\end{equation}
where the last inequality holds since $S_m=\sum_{i=1}^m\langle\mathbf{A}_{i,:},\mathbf{x}\rangle^2\le \sum_{i=1}^m \|\mathbf{A}_{i,:}\|_2^2$ by the Cauchy-Schwartz inequality.
Because
\begin{equation}
\label{equ: operator norm of B}
\|\mathbf{B}\|^2\ge \|\mathbf{B}\mathbf{x}\|_2^2= \sum_{i=m+1}^n \langle\mathbf{A}_{i,:},\mathbf{x}\rangle^2+m\left\langle\frac{\mathbf{x}_L}{x_0},\mathbf{x}\right\rangle^2= \|\mathbf{A}\|^2-S_m+\frac{m}{x_0^2}\|\mathbf{x}_L\|_2^2,
\end{equation}
it follows that
\begin{equation*}
\begin{split}
d&<\mathsf{srank}(\mathbf{B})=\frac{\|\mathbf{B}\|_F^2}{\|\mathbf{B}\|^2}\\
&\le \frac{\|\mathbf{A}\|_F^2-S_m+\frac{m}{x_0^2}}{\|\mathbf{A}\|^2-S_m+\frac{m}{x_0^2}\|\mathbf{x}_L\|_2^2}\qquad (\text{by Eqns. } \eqref{equ: F norm of B} \text{ and } \eqref{equ: operator norm of B})\\
&\le \frac{\|\mathbf{A}\|_F^2+\frac{m}{x_0^2}}{\|\mathbf{A}\|^2-S_m+\frac{m}{x_0^2}\|\mathbf{x}_L\|_2^2}\\
&\le \frac{\|\mathbf{A}\|_F^2+\frac{2\epsilon n}{x_0^2d}}{\|\mathbf{A}\|^2-\frac{2\epsilon}{d}\frac{\|\mathbf{A}\|_F^2}{d}+\frac{2\epsilon n}{2x_0^2d}}.\qquad (\mbox{by Eqn. } \eqref{equ: S_m}\mbox{, }\|\mathbf{x}_L\|_2=\Omega(1) \mbox{ and } m=\Theta(\epsilon n/d))
\end{split}
\end{equation*}
Thus
\begin{equation*}
\begin{split}
\|\mathbf{A}\|^2&< \frac{\|\mathbf{A}\|_F^2}{d}+\frac{2\epsilon n}{x_0^2d^2}+\frac{2\epsilon}{d}\frac{\|\mathbf{A}\|_F^2}{d}-\frac{\epsilon n}{x_0^2d}\\
&\le \frac{\|\mathbf{A}\|_F^2}{d}+\frac{2\epsilon}{d}\frac{\|\mathbf{A}\|_F^2}{d}-\frac{\epsilon n}{x_0^2d}\left(1-\frac{2}{d}\right)\\
&\le \frac{\|\mathbf{A}\|_F^2}{d}+\frac{2\epsilon}{d}\frac{\|\mathbf{A}\|_F^2}{d}-\frac{\epsilon n}{2x_0^2d}\qquad \left(\mbox{since } \frac{1}{2}\le 1-\frac{2}{d}\right)\\
&\le \frac{\|\mathbf{A}\|_F^2}{d}+\frac{2\epsilon}{d}\frac{\|\mathbf{A}\|_F^2}{d}-\frac{\epsilon}{2x_0^2n}\frac{\|\mathbf{A}\|_F^2}{d}\qquad \left(\mbox{since }\frac{\|\mathbf{A}\|_F^2}{n}\le n\right)\\
&=\frac{\|\mathbf{A}\|_F^2}{d}\left(1-\left(\frac{\epsilon}{2x_0^2n}-\frac{2\epsilon}{d}\right)\right)\\
&=\frac{\|\mathbf{A}\|_F^2}{d}\left(1-\Theta\left(\frac{\epsilon}{d}\right)\right),\qquad \left(\mbox{since } x_0^2=\Theta\left(\frac{d}{n}\right)\right)
\end{split}
\end{equation*}
namely, $(1+\Theta(\epsilon/d))\cdot\mathsf{srank}(\mathbf{A})>d$.
Setting $\tau$ in Eqn. \eqref{equ: stable rank estimator} as $\Theta(\frac{\epsilon}{d})$, we can distinguish the two cases of ``$\mathsf{srank}(\mathbf{A})<d$'' from ``$\mathsf{srank}(\mathbf{A})$ being far from stable rank $\le d$'' with sample complexity $\widetilde\mathcal{O}(\frac{d^2}{\beta^2 \tau^4})=\widetilde\mathcal{O}(\frac{d^6}{\epsilon^6})$.


\end{proof}


\red{Improved Proof:}
\begin{theorem}
Suppose that $d/\epsilon\ge 2$ and $d\ge 2$. Then Algorithm \ref{algorithm: algorithm for the stable rank testing problem} is a correct algorithm for the stable rank testing problem with failure probability at most $\frac{1}{3}$ in the entry model. It reads $\widetilde\mathcal{O}(\frac{d^2}{\epsilon^6})$ entries.
\end{theorem}

\begin{proof}
When $\mathbf{A}$ is far from being stable rank at most $d$, we claim that $\|\mathbf{A}\|_F^2\ge \epsilon n^2(1-\frac{1}{d})$. Otherwise, changing the first $\frac{\epsilon n}{d}$ rows of $\mathbf{A}$ to be all-one vectors $\mathbf{1}^\top$ leads to a new matrix $\mathbf{B}$ such that $\|\mathbf{B}\|^2\ge \frac{\epsilon n^2}{d}$ and $\|\mathbf{B}\|_F^2\le \epsilon n^2(1-\frac{1}{d})+\frac{\epsilon n^2}{d}=\epsilon n^2$, leading to $\mathsf{srank}(\mathbf{B})\le d$, a contradiction. By the Chernoff bound, it holds that with probability at least $1-e^{-\tau^2\|\mathbf{A}\|_F^2/3}\ge 1-e^{-\tau^2\epsilon n^2(1-1/d)/3}$, by sampling $q$ rows from $\mathbf{A}$, the resulting matrix $\mathbf{A}_{\mathsf{row}}$ satisfies
\begin{equation}
\label{equ: F norm}
(1-\tau)\|\mathbf{A}\|_F^2\le \frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|_F^2\le (1+\tau)\|\mathbf{A}\|_F^2.
\end{equation}
Conditioning on this event, by sampling $q$ columns from $\mathbf{A}_{\mathsf{row}}$ and using Chernoff bound again, with probability at least $1-e^{-\tau^2\epsilon n^2(1-1/d)/3}-e^{-\tau^2\|\mathbf{A}_{\mathsf{row}}\|^2/3}\ge 1-2e^{-\tau^2\epsilon n^2(1-1/d)q(1-\tau)/(3n)}$ we have
\begin{equation}
\label{equ: F norm entry level}
(1-\tau)^2\|\mathbf{A}\|_F^2\le (1-\tau)\frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|_F^2\le X\le (1+\tau)\frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|_F^2\le (1+\tau)^2\|\mathbf{A}\|_F^2.
\end{equation}

\comment{
Conditioned on the event $|X-\|\mathbf{A}\|_F^2|\le \frac{1}{8}(1-\frac{1}{d})^2\epsilon n$ in Lemma \ref{lemma: concentration}, it holds that
\begin{equation*}
X\ge \|\mathbf{A}\|_F^2-\frac{1}{8}\left(1-\frac{1}{d}\right)^2\epsilon n\ge \frac{9}{10}\epsilon n^2\left(1-\frac{1}{d}\right).
\end{equation*}
Therefore, Algorithm \ref{algorithm: algorithm for the stable rank testing problem} is correct on Line 5.

To prove the correctness of Lines 8 and 10, we only need to discuss the case when $X\ge \frac{9}{10}\epsilon n^2\left(1-\frac{1}{d}\right)$. So
\begin{equation*}
\|\mathbf{A}\|_F^2\ge X-\frac{1}{8}\left(1-\frac{1}{d}\right)^2\epsilon n\ge \frac{8}{10}\epsilon n^2\left(1-\frac{1}{d}\right).
\end{equation*}
Let $\eta:=\frac{c\epsilon n}{\|\mathbf{A}\|_F^2}\le \frac{10cd}{8(d-1)}=:\eta'$. We have
\begin{equation}
\left(1-\frac{\tau\eta'}{c}\right)\|\mathbf{A}\|_F^2\le X\le \left(1+\frac{\tau\eta'}{c}\right)\|\mathbf{A}\|_F^2.
\end{equation}
}

Let $c_1>1$ be a value to be specified later. We discuss two separate cases.




\medskip
\noindent{\textbf{Case (i). $\mathsf{srank}(\mathbf{A})> c_1 d$.}}

Let $\mathbf{U}$ be a uniformly random $n\times n$ orthogonal matrix. Note that $\|\mathbf{A}_{\mathsf{row}}\|=\|\mathbf{A}_{\mathsf{row}}\mathbf{U}\|$, and $(\mathbf{A}\mathbf{U})_{i,:}=\mathbf{A}_{i,:}\mathbf{U}$ uniformly distributes on $\|\mathbf{A}_{i,:}\|_2\cdot\mathbb{S}^{n-1}$. So $\|\mathbf{A}_{i,:}\mathbf{U}\|_\infty^2\le 2\|\mathbf{A}_{i,:}\mathbf{U}\|_2^2\log (n)/n$ for all $i$ with probability at least $1-1/n^2$ by Lemma \ref{Lemma: infty norm of uniform sampling from unit sphere}. Therefore, with probability at least $1-1/n$ by union bound over all rows, $\|\mathbf{A}\mathbf{U}\|_{\mathsf{col}}^2\le 2\|\mathbf{A}\|_F^2\log (n)/n$, where $\|\mathbf{A}\|_{\mathsf{col}}$ represents the maximum norm among all columns of $\mathbf{A}$. By Lemma \ref{Lemma: Vershynin},
\begin{equation*}
\bbE\|\mathbf{A}_{\mathsf{row}}\|\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F
\end{equation*}
for absolute constants $C_1$ and $C_2$, and by the Markov bound, with probability at least $0.9$,
\begin{equation*}
\begin{split}
\|\mathbf{A}_{\mathsf{row}}\|&\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\\
&\le C_1\sqrt{\frac{q}{n}}\frac{\|\mathbf{A}\|_F}{\sqrt{c_1 d}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\\
&\le \frac{1}{\sqrt{1-\tau}}\left(C_1\sqrt{\frac{q}{c_1d}}+C_2\sqrt{\log q\log n}\right)\sqrt{\frac{X}{n}}.
\end{split}
\end{equation*}
Conditioning on this event, by applying the same argument on the column sampling of $\mathbf{A}_{\mathsf{row}}$, we have
\begin{equation*}
\begin{split}
\|\widetilde\mathbf{A}\|&\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}_{\mathsf{row}}\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}_{\mathsf{row}}\|_F\\
&\le C_1\sqrt{\frac{q}{n}} \frac{1}{\sqrt{1-\tau}}\left(C_1\sqrt{\frac{q}{c_1d}}+C_2\sqrt{\log q\log n}\right)\sqrt{\frac{X}{n}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\sqrt{\frac{q}{1-\tau}}\sqrt{\frac{X}{n}},
\end{split}
\end{equation*}
where $\widetilde\mathbf{A}$ is the matrix after column sampling of $\mathbf{A}_{\mathsf{row}}$.
On the other hand, when $\mathsf{srank}(\mathbf{A})\le d$, by setting $\beta=\|\mathbf{A}\|_F^2/n^2$ and applying Corollary \ref{lemma: Ismail}, we have with probability at least $0.9$ that
\begin{equation}
\label{equ: row operator norm}
\|\mathbf{A}_{\mathsf{row}}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\|\mathbf{A}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\frac{\|\mathbf{A}\|_F}{\sqrt{d}}\ge \sqrt{\frac{1-\tau}{1+\tau}}\sqrt{\frac{q}{n}}\sqrt{\frac{X}{d}}.
\end{equation}
Conditioning on this event and applying Corollary \ref{lemma: Ismail} to column sampling of $\mathbf{A}_{\mathsf{row}}$, we have
\begin{equation*}
\|\widetilde\mathbf{A}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\|\mathbf{A}_{\mathsf{row}}\|\ge \frac{1-\tau}{\sqrt{1+\tau}}\frac{q}{n}\sqrt{\frac{X}{d}},
\end{equation*}
where we have used the fact that (by Eqns. \eqref{equ: F norm} and \eqref{equ: row operator norm})
\begin{equation}
\label{equ: stable rank of row sampling}
\mathsf{srank}(\mathbf{A}_{\mathsf{row}})=\frac{\|\mathbf{A}_{\mathsf{row}}\|_F^2}{\|\mathbf{A}_{\mathsf{row}}\|^2}\le \frac{1+\tau}{1-\tau}\mathsf{srank}(\mathbf{A})\le \frac{1+\tau}{1-\tau}d.
\end{equation}
By setting $c_1$ larger than a constant times $(1+\tau)/(1-\tau)^3$, we have
\begin{equation*}
\frac{1-\tau}{\sqrt{1+\tau}}\frac{q}{n}\sqrt{\frac{X}{d}} > C_1\sqrt{\frac{q}{n}} \frac{1}{\sqrt{1-\tau}}\left(C_1\sqrt{\frac{q}{c_1d}}+C_2\sqrt{\log q\log n}\right)\sqrt{\frac{X}{n}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\sqrt{\frac{q}{1-\tau}}\sqrt{\frac{X}{n}}.
\end{equation*}
Thus we can distinguish the two cases of $\mathsf{srank}(\mathbf{A})\le d$ and $\mathsf{srank}(\mathbf{A})$ far from being at most $d$.

\medskip
\noindent{\textbf{Case (ii). $\mathsf{srank}(\mathbf{A})\le c_1 d$.}}

Let $\beta=\|\mathbf{A}\|_F^2/n^2$. So $\beta \|\mathbf{A}_{i,:}\|_2^2/\|\mathbf{A}\|_F^2\le 1/n$ for all $i$'s, namely, uniform sampling obeys the condition of Corollary \ref{lemma: Ismail}. It then follows from Corollary \ref{lemma: Ismail} that with probability at least $0.9$,
\begin{equation*}
(1-\tau)\|\mathbf{A}\|^2\le \frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|^2\le (1+\tau)\|\mathbf{A}\|^2.
\end{equation*}
Conditioning on this event, by applying Corollary \ref{lemma: Ismail} again to the column sampling of $\mathbf{A}_{\mathsf{row}}$, we have with high probability,
\begin{equation}
\label{equ: small stable rank, operator norm}
(1-\tau)^2\|\mathbf{A}\|^2\le (1-\tau)\frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|^2\le \frac{n^2}{q^2}\|\widetilde\mathbf{A}\|^2\le (1+\tau)\frac{n}{q}\|\mathbf{A}_{\mathsf{row}}\|^2\le (1+\tau)^2\|\mathbf{A}\|^2,
\end{equation}
where we have used the fact that $\mathsf{srank}(\mathbf{A}_{\mathsf{row}})\le \mathcal{O}(d)$ by Eqn. \eqref{equ: stable rank of row sampling}. Combining Eqn. \eqref{equ: small stable rank, operator norm} with Eqn. \eqref{equ: F norm entry level}, we obtain an estimation of stable rank of $\mathbf{A}$ from $\mathsf{srank}(\widetilde\mathbf{A})$:
\begin{equation}
\label{equ: stable rank estimator}
(1-\Theta(\tau))\cdot\mathsf{srank}(\mathbf{A})\le \mathsf{srank}(\widetilde\mathbf{A})\le (1+\Theta(\tau))\cdot\mathsf{srank}(\mathbf{A}).
\end{equation}

We now show that we can distinguish the two cases of $\mathsf{srank}(\mathbf{A})\le d$ and $\mathsf{srank}(\mathbf{A})$ far from being at most $d$ by the above estimator $\mathsf{srank}(\widetilde\mathbf{A})$. Let $\mathbf{x}\in \mathbb{S}^{n-1}$ be the unit vector such that $\|\mathbf{A}\|=\|\mathbf{A}\mathbf{x}\|_2$, i.e., $\mathbf{x}$ is the right singular vector corresponding to the largest singular value. Let $\mathbf{x}^{(i)}$ be the projection of $\mathbf{x}$ on those coordinates with absolute value in $(1/2^i,1/2^{i-1})$, so that $\mathbf{x}=\sum_{i=0}^\infty\mathbf{x}^{(i)}$. Then $\|\mathbf{A}\mathbf{x}\|_2\le \sum_{i=0}^\infty\|\mathbf{A}\mathbf{x}^{(i)}\|_2$ by the triangle inequality. Also, for all $i$'s, we have
\begin{equation*}
\|\mathbf{A}\mathbf{x}^{(i)}\|_2\le \|\mathbf{A}\| \|\mathbf{x}^{(i)}\|_2\le \frac{\sqrt{n}\|\mathbf{A}\|}{2^{i-1}}\le \frac{\sqrt{n}\|\mathbf{A}\|_F}{2^{i-1}}\le \frac{n^{3/2}}{2^{i-1}},
\end{equation*}
which implies that
\begin{equation*}
\sum_{i>2\log n} \|\mathbf{A}\mathbf{x}^{(i)}\|_2\le \sum_{i>2\log n} \frac{n^{3/2}}{2^{i-1}}\le \frac{2}{\sqrt{n}}.
\end{equation*}
On the other hand, notice that $\|\mathbf{A}\|\ge \|\mathbf{A}\|_F/\sqrt{n}\ge \sqrt{\epsilon n}\sqrt{1-\frac{1}{d}}$. Therefore,
\begin{equation*}
\sum_{i=0}^{2\log n}\|\mathbf{A}\mathbf{x}^{(i)}\|_2 \ge \|\mathbf{A}\|-\sum_{i=2\log n}^{\infty}\|\mathbf{A}\mathbf{x}^{(i)}\|_2\ge \frac{\|\mathbf{A}\|}{2}.
\end{equation*}
So by averaging, there must exist a $k\in[2\log n]$ such that $\|\mathbf{A}\mathbf{x}^{(k)}\|_2\ge \|\mathbf{A}\|/(4\log n)$. Denote by $\mathbf{x}_L:=\mathbf{x}^{(k)}$ and $x_0:=1/2^{k-1}$, where $\|\mathbf{x}_L\|_\infty\le x_0$. Note that $\|\mathbf{x}_L\|_2\le \|\mathbf{x}\|_2\le 1$.



Suppose that $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$. Without loss of generality, we assume that $\langle\mathbf{A}_{1,:},\mathbf{x}\rangle^2\le \langle\mathbf{A}_{2,:},\mathbf{x}\rangle^2\le...\le \langle\mathbf{A}_{n,:},\mathbf{x}\rangle^2$. Let $m=\frac{\epsilon' n^2}{d \|\mathbf{x}_L\|_0}$, where $\epsilon'=\frac{\epsilon(1-\frac{1}{d})}{512c_1 \log^4 (n)}<\epsilon$. Replacing each $\mathbf{A}_{i,\mathsf{supp}(\mathbf{x}_L)}$, $i\in [m]$ with $\mathbf{x}_L^\top/x_0$ forms a new matrix $\mathbf{B}$. Since $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$, it must hold that $\mathsf{srank}(\mathbf{B})>d$ and $\|\mathbf{B}\|_\infty\le 1$.
Let $\mathsf{supp}(\mathbf{x}_L)$ be the support set of $\mathbf{x}_L$. We also have
\begin{equation*}
\begin{split}
\|\mathbf{A}\|^2&\le 16\log^2 (n)\|\mathbf{A}\mathbf{x}_L\|_2^2\\
&=16\log^2(n) \sum_{i=1}^n \langle\mathbf{A}_{i,:},\mathbf{x}_L\rangle^2\\
&\le 16\log^2(n) \sum_{i=1}^n \|\mathbf{A}_{i,\mathsf{supp}(\mathbf{x}_L)}\|_2^2 \|\mathbf{x}_L\|_2^2\qquad (\text{by Cauchy-Schwartz})\\
&\le 16\log^2(n) n\|\mathbf{x}_L\|_0\qquad (\text{since } \|\mathbf{x}_L\|_2\le 1,\ \|\mathbf{A}_{i,\mathsf{supp}(\mathbf{x}_L)}\|_2^2\le \|\mathbf{x}_L\|_0),
\end{split}
\end{equation*}
which implies that
\begin{equation*}
c_1d\ge \mathsf{srank}(\mathbf{A})=\frac{\|\mathbf{A}\|_F^2}{\|\mathbf{A}\|^2}\ge \frac{\epsilon n(1-\frac{1}{d})}{16\log^2(n) \|\mathbf{x}_L\|_0},
\end{equation*}
i.e., $\|\mathbf{x}_L\|_0\ge \frac{\epsilon n(1-\frac{1}{d})}{16c_1 d\log^2 (n)}=\frac{32\epsilon' n \log^2 (n)}{d}$.

Notice that
\begin{equation}
\label{equ: S_m}
S_m:=\sum_{i=1}^m\langle\mathbf{A}_{i,:},\mathbf{x}_L\rangle^2 \le \frac{m}{n} \sum_{i=1}^n\langle\mathbf{A}_{i,:},\mathbf{x}_L\rangle^2=\frac{m}{n}\|\mathbf{A}\mathbf{x}_L\|_2^2\le \frac{m}{n}\|\mathbf{A}\|^2,
\end{equation}
where the penultimate inequality holds because $\mathsf{srank}(\mathbf{A})=\frac{\|\mathbf{A}\|_F^2}{\|\mathbf{A}\|^2}>d$ by assumption. We also observe that
\begin{equation}
\label{equ: F norm of B}
\|\mathbf{B}\|_F^2\le \|\mathbf{A}\|_F^2+\frac{m\|\mathbf{x}_L\|_2^2}{x_0^2}.
\end{equation}
Because
\begin{equation}
\label{equ: operator norm of B}
\begin{split}
\|\mathbf{B}\|^2&=\max_{\|\mathbf{y}\|_2\le 1} \|\mathbf{B}\mathbf{y}\|_2^2\\
&\ge \|\mathbf{B}\mathbf{x}_L\|_2^2\qquad (\text{because } \|\mathbf{x}_L\|_2\le 1)\\
&= \sum_{i=m+1}^n \langle\mathbf{A}_{i,:},\mathbf{x}_L\rangle^2+m\left\langle\frac{\mathbf{x}_L}{x_0},\mathbf{x}_L\right\rangle^2\\
&=\|\mathbf{A}\mathbf{x}_L\|_2^2-S_m+\frac{m}{x_0^2}\|\mathbf{x}_L\|_2^2\\
&\ge \frac{\|\mathbf{A}\|^2}{16\log^2 n}-S_m+\frac{m}{4}\|\mathbf{x}_L\|_0\quad \left(\text{since non-zero entries of } \mathbf{x}_L \text{ in }\left[\frac{x_0}{2},x_0\right] \text{ so } \|\mathbf{x}_L\|_2^2\ge \frac{\|\mathbf{x}_L\|_0x_0^2}{4}\right)\\
&\ge \frac{\|\mathbf{A}\|^2}{16\log^2 n}-\frac{m}{n}\|\mathbf{A}\|^2+\frac{m}{4}\|\mathbf{x}_L\|_0\qquad (\text{by Eqn. \eqref{equ: S_m}})\\
&\ge \frac{\|\mathbf{A}\|^2}{32\log^2 n}+\frac{m}{4}\|\mathbf{x}_L\|_0,\qquad \left(\text{since }\frac{\|\mathbf{A}\|^2}{32\log ^2n}\ge \frac{m}{n}\|\mathbf{A}\|^2\right)
\end{split}
\end{equation}
and the fact that the number of changed entries is $\frac{\epsilon' n^2}{d}<\frac{\epsilon n^2}{d}$, it follows from the definition of being $\epsilon/d$-far from having stable rank at most $d$ that
\begin{equation*}
\begin{split}
d&<\mathsf{srank}(\mathbf{B})=\frac{\|\mathbf{B}\|_F^2}{\|\mathbf{B}\|^2}\\
&\le \frac{\|\mathbf{A}\|_F^2+\frac{m\|\mathbf{x}_L\|_2^2}{x_0^2}}{\frac{\|\mathbf{A}\|^2}{16\log^2 n}+\frac{m}{4}\|\mathbf{x}_L\|_0}\qquad (\text{by Eqns. } \eqref{equ: F norm of B} \text{ and } \eqref{equ: operator norm of B})\\
&\le \frac{\|\mathbf{A}\|_F^2+\frac{\epsilon' n^2\|\mathbf{x}_L\|_2^2}{x_0^2d\|\mathbf{x}_L\|_0}}{\frac{\|\mathbf{A}\|^2}{16\log^2 n}+\frac{\epsilon' n^2}{4d}}.\qquad (\mbox{by Eqn. } \eqref{equ: S_m} \mbox{ and } m=\epsilon' n^2/(\|\mathbf{x}_L\|_0d))
\end{split}
\end{equation*}
Thus
\begin{equation*}
\begin{split}
\frac{\|\mathbf{A}\|^2}{16\log^2 n}&< \frac{\|\mathbf{A}\|_F^2}{d}+\frac{\epsilon' n^2\|\mathbf{x}_L\|_2^2}{x_0^2d^2\|\mathbf{x}_L\|_0}-\frac{\epsilon' n^2}{4d}\\
&\le \frac{\|\mathbf{A}\|_F^2}{d}+\frac{\epsilon' n^2}{d^2}-\frac{\epsilon' n^2}{4d}\quad (\text{because } \|\mathbf{x}_L\|_2^2\le x_0^2\|\mathbf{x}_L\|_0)\\
&\le \frac{\|\mathbf{A}\|_F^2}{d}-\frac{\epsilon' n^2}{8d}\\
&\le \frac{\|\mathbf{A}\|_F^2}{d}-\frac{\epsilon' \|\mathbf{A}\|_F^2}{8d}\quad (\text{because } \|\mathbf{A}\|_F^2\le n^2)\\
&\le \frac{\|\mathbf{A}\|_F^2}{d}\left(1-\frac{\epsilon'}{8}\right).
\end{split}
\end{equation*}
That is, $(1+\Theta(\epsilon'))\cdot\mathsf{srank}(\mathbf{A})>d$.
Setting $\tau$ in Eqn. \eqref{equ: stable rank estimator} as $\Theta(\epsilon')$, we can distinguish the two cases of $\mathsf{srank}(\mathbf{A})<d$ and $\mathsf{srank}(\mathbf{A})$ being far from stable rank $\le d$ with sample complexity $\widetilde\mathcal{O}(\frac{d^2}{\beta^2 \tau^4})=\widetilde\mathcal{O}(\frac{d^2}{\epsilon^6})$, where we have used the fact that $\beta=\|\mathbf{A}\|_F^2/n^2\ge \epsilon (1-\frac{1}{d})\ge \frac{\epsilon}{2}$.

\comment{
To get $d^2/\epsilon^2$, we need $\log^2(1/\epsilon)$ algorithms. In particular, we run Ismail with each possible $\beta$ a power of $2$ between $1$ and $1/\epsilon$, and do this for both the row and then the column sampling. Then the idea is that if $\beta$ is large, e.g., $1/\epsilon$ for rows and $1$ for columns, this means the operator norm is concentrated on an $\epsilon n \times n$ submatrix, and so you need to change a $1/d$ fraction of entries on the submatrix, not an $\epsilon/d$, and so the second part of our algorithm can be run with constant eps on that submatrix. So in this case we only get in total $d^2/\epsilon$. But if $\beta=1$ originally then the second part of the algorithm needs changing $\epsilon/d$ fraction of entries but since $\beta=1$ this gives $d^2/\epsilon^2$ in this case.
}
\end{proof}
}


\begin{algorithm}
\caption{Algorithm for stable rank testing under sampling/sensing model}
\label{algorithm: algorithm for the stable rank testing problem}
\begin{algorithmic}[1]
\LineComment Lines 1-2 estimate the Frobenius norm of $\mathbf{A}$.
\State Uniformly sample $q_0=\mathcal{O}(\frac{\sqrt{d}}{\epsilon^{2.5}})$ entries $\mathbf{A}$, forming vector $\mathbf{y}$.
\State $X\leftarrow \frac{n^2}{q_0}\|\mathbf{y}\|_2^2$.\Comment{$X$ is an estimator of $\|\mathbf{A}\|_F^2$.}
\If{$X\le \frac{9}{10}(1-\frac{1}{d})\epsilon n^2$}
	\State Output ``stable rank $\le d$''.  \label{alg:F norm constant approximation}
\Else
	\State Uniformly sample a $q\times q$ submatrix $\widetilde\mathbf{A}'$ with $q=\mathcal{O}(\frac{d\log n}{\epsilon})$.
	\If {$\|\widetilde\mathbf{A}'\|\le C_0\frac{\sqrt{X}}{\sqrt{c_1d}}\frac{q}{n}$}
		\State Output ``$\epsilon/d$-far from being stable rank $\le d$''.
	\Else
		\State Run Algorithm \ref{algorithm: the sampling algorithm for even p} (with $\tau=\Theta(\epsilon/d^{1/4})$) for the sampling model or Algorithm \ref{algorithm: the sketching algorithm for even p} (with $\tau=\Theta(\epsilon/(d^{1/4}\sqrt{\log n}))$) for the sensing model to obtain an operator norm estimate $Z$.
		\If{$Z^2\ge \frac{X}{d}$}
			\State Output ``stable rank $\le d$''.
		\Else
			\State Output ``$\epsilon/d$-far from being stable rank $\le d$''.
		\EndIf
	\EndIf
\EndIf
\end{algorithmic}
\end{algorithm}


\begin{theorem}
\label{theorem: stable rank testing upper bound}
Suppose that $d=\Omega((1/\epsilon)^{1/3})$. Then (a) Algorithm \ref{algorithm: algorithm for the stable rank testing problem} is a correct algorithm for the stable rank testing problem with failure probability at most $1/3$ under the sampling model, and it reads $\mathcal{O}(\frac{d^3}{\epsilon^4}\log^2 n)$ entries; (b) Algorithm \ref{algorithm: algorithm for the stable rank testing problem} is a correct algorithm for the stable rank testing problem with failure probability at most $1/3$ under the sensing model, and it makes $\mathcal{O}(\frac{d^{2.5}}{\epsilon^2}\log n)$ sensing queries.
\end{theorem}

\begin{proof}
When $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$, we claim that $\|\mathbf{A}\|_F^2\ge \epsilon n^2(1-\frac{1}{d})$. Otherwise, replacing any $\frac{\epsilon n}{d}$ rows of $\mathbf{A}$ with all-one row vectors $\mathbf{1}^\top$'s results in a new matrix $\mathbf{B}$ such that $\|\mathbf{B}\|^2\ge \frac{\epsilon n^2}{d}$ and $\|\mathbf{B}\|_F^2= \|\mathbf{A}\|_F^2+\frac{\epsilon n^2}{d}\le \epsilon n^2(1-\frac{1}{d})+\frac{\epsilon n^2}{d}=\epsilon n^2$, leading to $\mathsf{srank}(\mathbf{B})\le d$, a contradiction. We note that by sampling $q_0$ entries from $\mathbf{A}$ and stacking them as vector $\mathbf{y}$, the resulting estimator $X=\frac{n^2}{q_0^2}\|\mathbf{y}\|_2^2$ satisfies $\bbE[X]=\|\mathbf{A}\|_F^2$ and $\mathsf{Var}[X]\le n^2(n^4/q_0^2)(q_0/n^2)=n^4/q_0$. So by the Chebyshev's inequality, when $q_0=\mathcal{O}(n^4/(\tau^2\|\mathbf{A}\|_F^4))$ we have
\begin{equation*}
\Pr\left[|X-\|\mathbf{A}\|_F^2|>\tau\|\mathbf{A}\|_F^2\right]\le \frac{n^4/q_0}{\tau^2\|\mathbf{A}\|_F^4}\le \frac{1}{3}.
\end{equation*}
Thus we have
\begin{equation}
\label{equ: F norm entry level}
(1-\tau)\|\mathbf{A}\|_F^2\le X\le (1+\tau)\|\mathbf{A}\|_F^2,
\end{equation}
where $\tau$ will be specified later multiple times.
So the algorithm is correct in Step \ref{alg:F norm constant approximation} with constant $\tau$ (although we over-sample entries here for later purpose).

\comment{
Conditioned on the event $|X-\|\mathbf{A}\|_F^2|\le \frac{1}{8}(1-\frac{1}{d})^2\epsilon n$ in Lemma \ref{lemma: concentration}, it holds that
\begin{equation*}
X\ge \|\mathbf{A}\|_F^2-\frac{1}{8}\left(1-\frac{1}{d}\right)^2\epsilon n\ge \frac{9}{10}\epsilon n^2\left(1-\frac{1}{d}\right).
\end{equation*}
Therefore, Algorithm \ref{algorithm: algorithm for the stable rank testing problem} is correct on Line 5.

To prove the correctness of Lines 8 and 10, we only need to discuss the case when $X\ge \frac{9}{10}\epsilon n^2\left(1-\frac{1}{d}\right)$. So
\begin{equation*}
\|\mathbf{A}\|_F^2\ge X-\frac{1}{8}\left(1-\frac{1}{d}\right)^2\epsilon n\ge \frac{8}{10}\epsilon n^2\left(1-\frac{1}{d}\right).
\end{equation*}
Let $\eta:=\frac{c\epsilon n}{\|\mathbf{A}\|_F^2}\le \frac{10cd}{8(d-1)}=:\eta'$. We have
\begin{equation}
\left(1-\frac{\tau\eta'}{c}\right)\|\mathbf{A}\|_F^2\le X\le \left(1+\frac{\tau\eta'}{c}\right)\|\mathbf{A}\|_F^2.
\end{equation}
}

Let $c_1>1$ be an absolute constant to be specified later. We discuss two separate cases.




\medskip
\noindent{\textbf{Case (i). $\mathsf{srank}(\mathbf{A})> c_1 d$ when $\mathbf{A}$ is far from $\mathsf{srank}(\mathbf{A})\le d$.}}

We first discuss the case when $\mathbf{A}$ is far from $\mathsf{srank}(\mathbf{A})\le d$. Let $\mathbf{U}$ be a uniformly random $n\times n$ orthogonal matrix and let $\mathbf{A}_{\mathsf{row}}'$ be the matrix after uniform row sampling of $\mathbf{A}$ of expected cardinality $q$. Note that $\|\mathbf{A}_{\mathsf{row}}'\|=\|\mathbf{A}_{\mathsf{row}}'\mathbf{U}\|$, and $(\mathbf{A}\mathbf{U})_{i,:}=\mathbf{A}_{i,:}\mathbf{U}$ uniformly distributes on $\|\mathbf{A}_{i,:}\|_2\cdot\mathbb{S}^{n-1}$. So $\|\mathbf{A}_{i,:}\mathbf{U}\|_\infty^2\le 2\|\mathbf{A}_{i,:}\mathbf{U}\|_2^2\log (n)/n$ for any fixed $i$ with probability at least $1-1/n^2$ by Lemma \ref{Lemma: infty norm of uniform sampling from unit sphere}. Therefore, with probability at least $1-1/n$ by a union bound over all rows, $\|\mathbf{A}\mathbf{U}\|_{\mathsf{col}}^2\le 2\|\mathbf{A}\|_F^2\log (n)/n$, where $\|\mathbf{A}\|_{\mathsf{col}}$ represents the maximum $\ell_2$ norm among all columns of $\mathbf{A}$. By Lemma \ref{Lemma: Vershynin},
\begin{equation*}
\bbE\|\mathbf{A}_{\mathsf{row}}'\|\le C_1'\sqrt{\frac{q}{n}}\|\mathbf{A}\|+C_2'\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F
\end{equation*}
for absolute constants $C_1'$ and $C_2'$, and by the Markov bound, with probability at least $0.9$,
\begin{equation*}
\begin{split}
\|\mathbf{A}_{\mathsf{row}}'\|&\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\\
&\le C_1\sqrt{\frac{q}{n}}\frac{\|\mathbf{A}\|_F}{\sqrt{c_1 d}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\quad(\text{since }\mathsf{srank}(\mathbf{A})>c_1d)\\
&\le \frac{1}{\sqrt{1-\tau}}\left(C_1\sqrt{\frac{q}{c_1d}}+C_2\sqrt{\log q\log n}\right)\sqrt{\frac{X}{n}}\quad(\text{by Eqn. \eqref{equ: F norm entry level}})
\end{split}
\end{equation*}
for absolute constants $C_1$ and $C_2$. By the Markov bound, we also have with constant probability that
\begin{equation*}
\|\mathbf{A}_{\mathsf{row}}'\|_F^2\le c'\frac{q}{n}\|\mathbf{A}\|_F^2\le c\frac{q}{n}X.
\end{equation*}
Conditioning on this event, by applying the same argument on the column sampling of $\mathbf{A}_{\mathsf{row}}'$, we have
\begin{equation*}
\begin{split}
\|\widetilde\mathbf{A}'\|&\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}_{\mathsf{row}}'\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}_{\mathsf{row}}'\|_F\\
&\le C_1\sqrt{\frac{q}{n}} \frac{1}{\sqrt{1-\tau}}\left(C_1\sqrt{\frac{q}{c_1d}}+C_2\sqrt{\log q\log n}\right)\sqrt{\frac{X}{n}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\sqrt{qc}\sqrt{\frac{X}{n}}\\
&\le C_0\frac{1}{\sqrt{1-\tau}}\frac{\sqrt{X}}{\sqrt{c_1d}}\frac{q}{n}\qquad(\text{because the first term dominates as } q\gg d)\\
&\le C_0'\sqrt{\frac{1+\tau}{1-\tau}}\frac{\|\mathbf{A}\|_F}{\sqrt{c_1d}}\frac{q}{n},\qquad(\text{by Eqn. }\eqref{equ: F norm entry level})
\end{split}
\end{equation*}
where $\widetilde\mathbf{A}'$ is the matrix after the column sampling of $\mathbf{A}_{\mathsf{row}}'$, and $C_0,C_0'$ are absolute constants.


On the other hand, when $\mathsf{srank}(\mathbf{A})\le d$ and $q=\mathcal{O}(\frac{d\log n}{\epsilon})$, we have with high probability that
\begin{equation*}
\|\widetilde\mathbf{A}'\|\ge C\frac{q}{n}\|\mathbf{A}\|= C\frac{q}{n}\frac{\|\mathbf{A}\|_F}{\sqrt{\mathsf{srank}(\mathbf{A})}}\ge C\frac{q}{n}\frac{\|\mathbf{A}\|_F}{\sqrt{d}},
\end{equation*}
where the first inequality holds by applying Lemma \ref{lemma: Ismail} twice on row and column sampling (set $\beta=\Theta(\epsilon)$ and $\tau=\Theta(1)$ there).
\comment{
by setting $\beta=\|\mathbf{A}\|_F^2/n^2$ and applying Corollary \ref{lemma: Ismail}, we have with probability at least $0.9$ that
\begin{equation}
\label{equ: row operator norm}
\|\mathbf{A}_{\mathsf{row}}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\|\mathbf{A}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\frac{\|\mathbf{A}\|_F}{\sqrt{d}}\ge \sqrt{\frac{1-\tau}{1+\tau}}\sqrt{\frac{q}{n}}\sqrt{\frac{X}{d}}.
\end{equation}
Conditioning on this event and applying Corollary \ref{lemma: Ismail} to the column sampling of $\mathbf{A}_{\mathsf{row}}$, we have
\begin{equation*}
\|\widetilde\mathbf{A}\|\ge \sqrt{1-\tau}\sqrt{\frac{q}{n}}\|\mathbf{A}_{\mathsf{row}}\|\ge \frac{1-\tau}{\sqrt{1+\tau}}\frac{q}{n}\sqrt{\frac{X}{d}},
\end{equation*}
where we have used the fact that (by Eqns. \eqref{equ: F norm} and \eqref{equ: row operator norm})
\begin{equation}
\label{equ: stable rank of row sampling}
\mathsf{srank}(\mathbf{A}_{\mathsf{row}})=\frac{\|\mathbf{A}_{\mathsf{row}}\|_F^2}{\|\mathbf{A}_{\mathsf{row}}\|^2}\le \frac{1+\tau}{1-\tau}\mathsf{srank}(\mathbf{A})\le \frac{1+\tau}{1-\tau}d.
\end{equation}
}
By setting $c_1$ as a large absolute constant, we have
\begin{equation*}
C_0'\sqrt{\frac{1+\tau}{1-\tau}}\frac{\|\mathbf{A}\|_F}{\sqrt{c_1d}}\frac{q}{n} < C\frac{q}{n}\frac{\|\mathbf{A}\|_F}{\sqrt{d}}.
\end{equation*}
Thus we can distinguish (a) $\mathsf{srank}(\mathbf{A})\le d$ from (b) $\mathsf{srank}(\mathbf{A})$ $\epsilon/d$-far from being at most $d$ by checking $\|\widetilde\mathbf{A}'\|$ in Case (i).

\medskip
\noindent{\textbf{Case (ii). $\mathsf{srank}(\mathbf{A})\le c_1 d$ when $\mathbf{A}$ is far from $\mathsf{srank}(\mathbf{A})\le d$.}}

We now show that we can distinguish the two cases of $\mathsf{srank}(\mathbf{A})\le d$ from $\mathsf{srank}(\mathbf{A})$ being $\epsilon/d$-far from at most $d$, suppose we have an accurate estimator to estimate the stable rank.

Let $\u\in \mathbb{S}^{n-1}$ be a unit vector such that $\|\mathbf{A}\|=\|\mathbf{A} \u\|_2$, i.e., $\u$ is a right singular vector corresponding to the largest singular value. First we claim that we can drop off coordinates in $\u$ that are at most $\theta/\sqrt{n}$ for some small constant $\theta$ without affecting $\|\mathbf{A} \u\|_2$ by too much.

Let $\u'$ be the vector obtained from $\u$ by zeroing out the coordinates of $\u$ which are \textit{at least} $\theta/\sqrt{n}$, then
\[
\|\mathbf{A} \u'\|_2^2 \leq \|\mathbf{A}\|^2 \|\u'\|_2^2 \leq \|\mathbf{A}\|^2 n \left(\frac{\theta}{\sqrt n}\right)^2 \leq \theta^2\|\mathbf{A}\|^2,
\]
and thus
\[
\|\mathbf{A}(\u-\u')\|_2 \geq \|\mathbf{A} \u\|_2 - \|\mathbf{A} \u'\|_2 \geq (1-\theta)\|\mathbf{A}\|.
\]
Let $\u'' = \u-\u'$ and $\v = \mathbf{A}\u''/\|\mathbf{A}\u''\|_2$, then $(1-\theta)\|\mathbf{A}\| \leq \langle \mathbf{A}\u'',\v\rangle$. Next we show similarly that we can drop off coordinates in $\v$ that are at most $\theta/\sqrt{n}$. Similarly we let $\v'$ be the vector obtained from $\v$ by zeroing out the coordinates of $\v$ which are at least $\theta/\sqrt{n}$, then
$\|\v'\|_2 \leq \theta$, hence
\[
\langle \mathbf{A}\u'',\v-\v'\rangle \geq (1-\theta)\|\mathbf{A}\| - \langle \mathbf{A}\u'',\v'\rangle
\geq (1-\theta)\|\mathbf{A}\| - \|\mathbf{A}\u''\|_2\|\v'\|_2
\geq (1-2\theta)\|\mathbf{A}\|.
\]
Let $\v'' = \v-\v'$. Observe that
\[
(1-2\theta)\frac{\|\mathbf{A}\|_F}{\sqrt{c_1 d}}\leq (1-2\theta)\|\mathbf{A}\| \leq \langle \mathbf{A}\u'',\v''\rangle \leq \|\mathbf{A}\u''\|_\infty \|\v''\|_1 \leq \|\u''\|_1\|\v''\|_1,
\]
where we used the fact that $|\mathbf{A}_{ij}|\leq 1$ in the last inequality. This implies that at least one of $\|\u''\|_1$ and $\|\v''\|_1$ is at least $\sqrt{(1-2\theta)\|\mathbf{A}\|_F}/(c_1 d)^{1/4}= c\sqrt{\|\mathbf{A}\|_F}/d^{1/4}$ for some constant $c = \sqrt{1-2\theta}/c_1^{1/4}$.

Without loss of generality, assume that $\|\u''\|_1 \geq c\sqrt{\|\mathbf{A}\|_F}/d^{1/4}$. Next we shall argue that we can drop large coordinates from $\u''$ by affecting $\|\u''\|_1$ by at most a constant factor. To see this, let $I = \{i: |\u''_i|\geq \kappa\}$ for some $\kappa$ to be determined later. It follows that $|I| \leq 1/\kappa^2$ and
\[
\|\u''_I\|_1 \leq \sqrt{|I|}\ \|\u''_I\|_2 \leq \frac{1}{\kappa} = \frac{c}{2} \frac{\sqrt{\|\mathbf{A}\|_F}}{d^{1/4}},
\]
provided that
\[
\kappa = \frac{2d^{1/4}}{c\sqrt{\|\mathbf{A}\|_F}}.
\]

Let $\hat \mathbf{x} = \u'' - \u''_I$, we see that $\|\hat \mathbf{x}\|_1\geq \frac{1}{2}\|\u''\|_1$. For notational simplicity let $S = \operatorname{supp}(\hat \mathbf{x})$.

Suppose that $\mathbf{A}$ is $\epsilon/d$-far from being stable rank at most $d$, and we reorder the rows of $\mathbf{A}$ such that $|\langle \mathbf{A}_{1,:},\u\rangle| \leq |\langle \mathbf{A}_{2,:},\u\rangle| \leq \cdots \leq |\langle \mathbf{A}_{n,:},\u\rangle|$. Let $m=\frac{\epsilon n^2}{d |S|}$ (we shall verify that $m\leq n$ later). For $i=1,\dots, m$, change $\mathbf{A}_{i,j}$ to $\operatorname{sgn}(\hat\mathbf{x}_j)$ for all $j\in S$ if $\langle \mathbf{A}_{i,S^c}, \u\rangle\geq 0$, and change $\mathbf{A}_{i,j}$ to $-\operatorname{sgn}(\hat\mathbf{x}_j)$ for all $j\in S$ if $\langle \mathbf{A}_{i,S^c}, \u\rangle < 0$, yielding a matrix $\mathbf{B}$ and we know that $\operatorname{srank}(\mathbf{B}) > d$.


Now we verify that $m\leq n$ so that the aforementioned change is valid. It is clear that $|S|\geq \|\hat \mathbf{x}\|_1/\kappa$, and so
\[
m\leq \frac{\epsilon n^2}{d\cdot \|\hat\mathbf{x}\|_1/\kappa} \leq \frac{\epsilon n^2}{d}\cdot \frac{4 \sqrt{d}}{ c^2 \|\mathbf{A}\|_F} \leq \frac{8\sqrt{\epsilon}}{c^2\sqrt d} n < n,
\]
provided that $\epsilon\leq \epsilon_0$ for some absolute constant $\epsilon_0$ small enough.

We observe that
\begin{equation}
\label{equ: F norm of B}
\|\mathbf{B}\|_F^2\le \|\mathbf{A}\|_F^2 + m|S|,
\end{equation}
and
\begin{equation}
\label{equ: operator norm of B}
\begin{split}
\|\mathbf{B}\|^2  \ge \|\mathbf{B}\u\|_2^2 &\geq \sum_{i=m+1}^n \langle\mathbf{A}_{i,:},\u\rangle^2+ m\|\hat\mathbf{x}\|_1^2\\
&\geq \left(1-\frac{m}{n}\right)\|\mathbf{A}\u\|_2^2 + m\|\hat\mathbf{x}\|_1^2\\
&= \left(1-\frac{m}{n}\right)\|\mathbf{A}\|^2 + m\|\hat\mathbf{x}\|_1^2.
\end{split}
\end{equation}
It follows from $\mathsf{srank}(\mathbf{B}) > d$ that
\[
d < \mathsf{srank}(\mathbf{B})=\frac{\|\mathbf{B}\|_F^2}{\|\mathbf{B}\|^2} \le \frac{\|\mathbf{A}\|_F^2 + m|S|}{(1-\frac{m}{n})\|\mathbf{A}\|^2+ m\|\hat \mathbf{x}\|_1^2},
\]
or,
\begin{equation}\label{eqn:B_stable_rank}
d\left(1-\frac{m}{n}\right)\|\mathbf{A}\|^2 < \|\mathbf{A}\|_F^2 \left( 1 - \frac{m (d\|\hat\mathbf{x}\|_1^2-|S|)}{\|\mathbf{A}\|_F^2}\right).
\end{equation}

Next we claim that it holds under certain assumptions
\begin{equation}\label{eqn:subclaim1}
d \|\hat \mathbf{x}\|_1^2 \geq \frac{1}{\eta_1}|S|.
\end{equation}
Observe that
\begin{equation}\label{eqn:subclaim1_finer}
\frac{d \|\hat \mathbf{x}\|_1^2}{|S|} = d \|\hat \mathbf{x}\|_1 \frac{\|\hat \mathbf{x}\|_1}{|S|}\geq d\cdot\frac{\|\u''\|_1}{2}\cdot \frac{\theta}{\sqrt n} \geq d^{\frac{3}{4}}c\theta\sqrt{\frac{\|\mathbf{A}\|_F}{n}},
\end{equation}
which is at least $1/\eta_1$, provided that
\begin{equation}\label{eqn:condition_on_|A|_F}
\|\mathbf{A}\|_F \geq \frac{n}{d^{\frac{3}{2}}c^2\theta^2\eta_1^2}.
\end{equation}
This holds when $d=\Omega((1/\epsilon)^{1/3})$ since we know that $\|\mathbf{A}\|_F^2=\Omega(\epsilon n^2)$.

Hence under the assumption~\eqref{eqn:condition_on_|A|_F} it follows from~\eqref{eqn:B_stable_rank} that
\begin{equation}\label{eqn:B_stable_rank_2}
d\left(1-\frac{m}{n}\right)\|\mathbf{A}\|^2 < \|\mathbf{A}\|_F^2 \left( 1 - (1-\eta_1)\frac{m d\|\hat\mathbf{x}\|_1^2}{\|\mathbf{A}\|_F^2}\right).
\end{equation}
Note that
\[
(1-\eta_1)\frac{m d\|\hat\mathbf{x}\|_1^2}{\|\mathbf{A}\|_F^2} \geq (1-\eta_1)m d\cdot \frac{\frac{c^2}{4}\cdot \frac{\|\mathbf{A}\|_F}{\sqrt d}}{\|\mathbf{A}\|_F^2} = \frac{(1-\eta_1)c^2}{4}m \cdot \frac{\sqrt{d}}{\|\mathbf{A}\|_F} \geq \frac{1}{\eta_2}\cdot \frac{m}{n},
\]
provided that
\begin{equation}\label{eqn:condition2_on_|A|_F}
\|\mathbf{A}\|_F \leq \frac{\eta_2(1-\eta_1)c^2}{4}n\sqrt{d}.
\end{equation}
Combining \eqref{eqn:condition_on_|A|_F} and \eqref{eqn:condition2_on_|A|_F} leads to that
\begin{equation}\label{eqn:condition_on_d}
d \geq \frac{2}{c^2\theta\eta_1\sqrt{(1-\eta_1)\eta_2}} = \frac{2\sqrt{c_1}}{\theta(1-2\theta)\eta_1\sqrt{(1-\eta_1)\eta_2}}.
\end{equation}

Now, under both assumptions~\eqref{eqn:condition_on_|A|_F} and~\eqref{eqn:condition_on_d}, it follows from~\eqref{eqn:B_stable_rank_2} that
\begin{align*}
\frac{\|\mathbf{A}\|_F^2}{d\|\mathbf{A}\|^2} &\geq 1 + (1-\eta_1-\eta_2)\frac{m d\|\hat\mathbf{x}\|_1^2}{\|\mathbf{A}\|_F^2}
\\
&\geq 1 + (1-\eta_1-\eta_2)\frac{\epsilon n^2}{d\|\mathbf{A}\|_F^2}\cdot \frac{d\|\hat\mathbf{x}\|_1^2}{|S|}\\
&\geq 1 + (1-\eta_1-\eta_2)c\theta \frac{\epsilon n^{3/2}}{d^{1/4}\|\mathbf{A}\|_F^{3/2}},\qquad (\text{by }\eqref{eqn:subclaim1_finer})
\end{align*}
Choosing $\theta=1/4$, $\eta_1+\eta_2<1$, we see from \eqref{eqn:condition_on_d} that we shall need $d = \Omega(\sqrt{c_1})$. It is also easy to verify that \eqref{eqn:condition2_on_|A|_F} is satisfied for such $d$. Overall, we see that we shall need $\tau=\Theta\left(\frac{\epsilon n^{3/2}}{d^{1/4}\|\mathbf{A}\|_F^{3/2}}\right)$ in \eqref{equ: F norm entry level}.

\medskip
We are now ready to prove Theorem \ref{theorem: stable rank testing upper bound}.

\noindent{\textbf{Result (a):}} In fact, We have an accurate estimator to estimate the stable rank by reading an $\mathcal{O}(d^{1.5}\log (n)/\epsilon^2)\times \mathcal{O}(d^{1.5}\log (n)/\epsilon^2)$ submatrix:
combining Theorem \ref{theorem: operator norm estimator by Ismail} with Eqn. \eqref{equ: F norm entry level} yields an accurate estimator of the stable rank of $\mathbf{A}$:
\begin{equation*}
\label{equ: stable rank estimator}
(1-\Theta(\tau))\cdot\mathsf{srank}(\mathbf{A})\le \frac{X}{\|\widetilde\mathbf{A}\|^2}\le (1+\Theta(\tau))\cdot\mathsf{srank}(\mathbf{A}).
\end{equation*}
Setting $\tau$ as $\Theta(\frac{\epsilon}{d^{1/4}})$ gives the claimed result immediately.

\medskip
\noindent{\textbf{Result (b):}} It follows from setting $\tau = \Theta(\frac{\epsilon}{d^{1/4}})$ in Theorem \ref{theorem: operator norm estimator under sensing model} on sketching complexity.
\end{proof}





\subsection{Lower Bounds}

\begin{lemma}[Corollary 5.35, \cite{vershynin2010introduction}]
\label{lemma: vershynin concentration of Gaussian operator norm}
Let $\mathbf{A}$ be an $m\times n$ ($m>n$) matrix whose entries are independent standard normal random variables. Then for every $t\ge 0$ and fixed $\v\in\mathbb{R}^n$, it holds with probability at least $1-2\exp(-t^2/2)$ that
\[
\sqrt{m}-\sqrt{n}-t\le \sigma_{\min}(\mathbf{A}) \leq \sigma_{\max}(\mathbf{A}) \le \sqrt{m}+\sqrt{n}+t.
\]
\end{lemma}

\begin{lemma}[Lemma 1, \cite{laurent2000adaptive}]
\label{lemma: tail bound of chi-square}
Let $X\sim \chi^2(k)$. Then we have the tail bound
\begin{equation*}
\Pr[k-2\sqrt{kx}\le X\le k+2\sqrt{kx}+2x] \ge 1-2e^{-x}.
\end{equation*}
\end{lemma}

\begin{lemma}[Theorem 4, \cite{li2016tight}]
\label{lemma: total variation distance of L1 and L2}
Let $\u_1,...,\u_r$ be i.i.d. $\mathcal{N}(\mathbf{0},\mathbf{I}_m)$ vectors and $\v_1,...,\v_r$ be i.i.d. $\mathcal{N}(\mathbf{0},\mathbf{I}_n)$ vectors and further suppose that $\{\u_i\}$ and $\{\v_i\}$ are independent. Let $\mathcal{D}_1=\mathcal{G}(m,n)$ and $\mathcal{D}_2=\mathcal{G}(m,n)+\sum_{i=1}^r s_i\u_i\v_i^\top$, where $\mathbf{s}=[s_1,...,s_r]^\top$ and $\mathcal{G}(m,n)$ represents $m\times n$ i.i.d. standard Gaussian matrix over $\mathbb{R}$. Denote by $\mathcal{L}_1$ and $\mathcal{L}_2$ the corresponding distribution of the linear sketch of size $k$ on $\mathcal{D}_1$ and $\mathcal{D}_2$. Then
there exists an absolute constant $c>0$ such that $d_{TV}(\mathcal{L}_1,\mathcal{L}_2)\le 1/10$ whenever $k\le c/\|\mathbf{s}\|_2^4$, where $d_{TV}(\cdot,\cdot)$ represents the total variation distance between two distributions.
\end{lemma}



\begin{theorem}
\label{theorem: stable rank lower bound}
Let $\epsilon\in (0,1/3)$ and let $d\ge 4$. For $\mathbf{A}\in\mathbb{R}^{(d/\epsilon^2)\times d}$, any algorithm that distinguishes ``$\mathsf{srank}(\mathbf{A})\le d_0$'' from ``$\mathbf{A}$ being $\epsilon_0/d_0$-far from stable rank $\le d_0$'' with error probability at most $1/6$ requires measurements $\Omega(d^2/(\epsilon^2\log(d/\epsilon)))$ for any linear sketch, where $d_0=\frac{d}{1+\Theta(\epsilon)}$ and $\epsilon_0=\Theta(\frac{\epsilon}{\log^2(d/\epsilon)})$.
\end{theorem}

\begin{remark}
Theorem \ref{theorem: stable rank lower bound} can be generalized to the $(d/\epsilon^2)\times (d/\epsilon^2)$ matrix by concatenating the columns of two hard instances in Theorem \ref{theorem: stable rank lower bound} $(1/\epsilon^2)$ times. This scales up all singular values in our $(d/\epsilon^2)\times d$ hard instances by a factor of $1/\epsilon$, and thus the stable rank remains the same. Observe that the bounds on $\|\mathbf{G}\|$, $\|\mathbf{G}\|_F$ and $\|\S\|_F$ in \eqref{eqn:upper_bound_perturbed} and \eqref{eqn:lower_bound_perturbed} in the proof below are also scaled up by $1/\epsilon$. The concatenated matrix is therefore $\epsilon_0/d_0$-far from having stable rank at most $d_0$ following the same argument.
\end{remark}

\begin{proof}
Let $m=d/\epsilon^2$ and $n=d$. We will apply Lemma \ref{lemma: total variation distance of L1 and L2} with $r=1$. To this end, we need to justify that
\begin{equation*}
\frac{C}{\log(d/\epsilon)}\mathbf{G} \qquad \text{and} \qquad \frac{C}{\log(d/\epsilon)}(\mathbf{G}_0+s_1\u\v^\top)
\end{equation*}
differ in the stable rank (i.e., $\mathsf{srank}(\mathbf{G})> d_0\ge \mathsf{srank}(\mathbf{G}_0+s_1\u\v^\top)$) and that $\mathbf{G}$ is rigid (i.e., changing $\epsilon_0/d_0$-fraction of entries of $\mathbf{G}$ would not change the stable rank of $\mathbf{G}$ to be less than $d_0$), where the multiplicative factor $C/\log(d/\epsilon)$ is to keep the maximum absolute value of entries in the two hard instances less than $1$, $\mathbf{G},\mathbf{G}_0\sim\mathcal{G}(m,n)$, $\u\sim\mathcal{N}(\mathbf{0},\mathbf{I}_m)$, $\v\sim\mathcal{N}(\mathbf{0},\mathbf{I}_n)$, and $s_1=3\sqrt{\epsilon/d}$. Note that by Lemma \ref{lemma: total variation distance of L1 and L2}, we cannot distinguish $\mathbf{G}$ from $\mathbf{G}':=\mathbf{G}_0+s_1\u\v^\top$ with $\Omega(d^2/\epsilon^2)$ samples. So if the stable ranks of $\mathbf{G}$ and $\mathbf{G}'$ have a gap, we cannot detect the gap either.

For the operator norm, on one hand, it follows from Lemma \ref{lemma: vershynin concentration of Gaussian operator norm} that with probability at least $1-2\exp(-d/2)$,
\begin{equation*}
(1-1.1\epsilon)\frac{\sqrt{d}}{\epsilon}\le \sigma_{\min}(\mathbf{G}) \leq \sigma_{\max}(\mathbf{G})\le (1+1.1\epsilon)\frac{\sqrt{d}}{\epsilon},
\end{equation*}
for an absolute constant $C_0>0$.
On the other hand, with probability $\ge 1-\exp(-\Omega(d))$ we have
\begin{equation*}
\begin{split}
\left\|\mathbf{G}_0+s_1\u\v^\top\right\|^2 &=\sup_{\mathbf{x}\in \mathbb{S}^{n-1}} \left\|\mathbf{G}_0\mathbf{x}+s_1\u\v^\top\mathbf{x}\right\|_2^2\\
&\ge \frac{\left\|\mathbf{G}_0\v+s_1\u\v^\top\v\right\|_2^2}{\|\v\|_2^2}\\
&=\frac{\|\mathbf{G}_0\v\|_2^2}{\|\v\|_2^2}+s_1^2\|\u\|_2^2\|\v\|_2^2+2\langle\mathbf{G}_0\v,s_1\u\rangle\\
&\ge \left((1-1.1\epsilon)\sqrt{\frac{d}{\epsilon^2}}\right)^2+0.9^2 s_1^2 \frac{d^2}{\epsilon^2}-\mathcal{O}\left(\frac{d}{\sqrt{\epsilon}}\right)\\
&\ge \left((1-1.1\epsilon)\sqrt{\frac{d}{\epsilon^2}}\right)^2+0.9^2 s_1^2 \frac{d^2}{\epsilon^2}-\mathcal{O}\left(\frac{d}{\sqrt{\epsilon}}\right)\\
&\ge ((1-1.1\epsilon)^2+7.29\epsilon)\frac{d}{\epsilon^2}-\mathcal{O}\left(\frac{d}{\sqrt{\epsilon}}\right)\\
&\ge ((1-1.1\epsilon)^2+7.29\epsilon)\frac{d}{\epsilon^2}-\mathcal{O}\left(\frac{d}{\sqrt{\epsilon}}\right)\\
&\ge (1+2\epsilon)^2\frac{d}{\epsilon^2},
\end{split}
\end{equation*}
where the second inequality (line 4) follows from the concentration of the quadratic form (see, e.g., \cite{RV:hanson-wright})
\begin{equation}\label{equ: inner product}
\Pr_{\u,\v}\{|\v^T \mathbf{G}_0 \u|>t\}\leq 2\exp\left(-c\min\left\{ \frac{t}{\|\mathbf{G}_0\|}, \frac{t^2}{\|\mathbf{G}_0\|_F^2} \right\}\right)
\end{equation}
for fixed $\mathbf{G}_0$; since $\|\mathbf{G}_0\|\simeq \sqrt{d}/\epsilon$ and $\|\mathbf{G}_0\|_F^2\simeq d^2/\epsilon^2$ with high probability, we can take $t = \Theta(d^{3/2}/\epsilon)$.
For the Frobenius norm, we note that
\begin{equation*}
\begin{split}
\left\|\mathbf{G}_0+3\sqrt{\frac{\epsilon}{d}}\u\v^\top\right\|_F^2=\|\mathbf{G}_0\|_F^2+9\frac{\epsilon}{d}\|\u\v^\top\|_F^2+6\sqrt{\frac{\epsilon}{d}}\langle \mathbf{G}_0,\u\v^\top\rangle.
\end{split}
\end{equation*}
Observe that $\|\mathbf{G}_0\|_F^2\sim \chi^2(\frac{d^2}{\epsilon^2})$ so $\|\mathbf{G}_0\|_F^2=(1\pm \Theta(\frac{\epsilon}{d}))\frac{d^2}{\epsilon^2}$ with probability $\ge 0.9$ by Lemma \ref{lemma: tail bound of chi-square}, and $9\frac{\epsilon}{d}\|\u\v^\top\|_F^2=9\frac{\epsilon}{d}\|\u\|_2^2\|\v\|_2^2=\Theta(\frac{d}{\epsilon})$ with high probability. And also, setting $t = \Theta(d/\epsilon)$ in \eqref{equ: inner product}, we have with probability at least $0.9$ that $|\langle \mathbf{G}_0,\u\v^\top\rangle| = \mathcal{O}(\frac{d}{\epsilon})$ and thus $6\sqrt{\frac{\epsilon}{d}}|\langle\mathbf{G}_0,\u\v^\top\rangle|=\mathcal{O}(\sqrt{\frac{d}{\epsilon}})$.
Therefore,
\begin{equation*}
\left(1-\Theta\left(\frac{\epsilon}{d}\right)\right)\|\mathbf{G}_0\|_F^2\le \left\|\mathbf{G}_0+3\sqrt{\frac{\epsilon}{d}}\u\v^\top\right\|_F^2\le \left(1+\Theta\left(\frac{\epsilon}{d}\right)\right)\|\mathbf{G}_0\|_F^2.
\end{equation*}
As a result,
\begin{equation*}
\mathsf{srank}(\mathbf{G})=\frac{\|\mathbf{G}\|_F^2}{\|\mathbf{G}\|^2}\ge \frac{d}{(1+1.2\epsilon)^2},
\end{equation*}
and
\begin{equation*}
\mathsf{srank}(\mathbf{G}')=\frac{\|\mathbf{G}'\|_F^2}{\|\mathbf{G}'\|^2}\le \frac{d}{(1+1.9\epsilon)^2}.
\end{equation*}
By Lemma \ref{lemma: total variation distance of L1 and L2}, it is therefore hard to distinguish
\begin{equation*}
\mathsf{srank}\left(\frac{C}{\log(d/\epsilon)}\mathbf{G}'\right)=\mathsf{srank}(\mathbf{G}')=\frac{\|\mathbf{G}'\|_F^2}{\|\mathbf{G}'\|^2}\le \frac{d}{(1+1.9\epsilon)^2}\triangleq d_0
\end{equation*}
from
\begin{equation}
\label{equ: stable rank of G}
\mathsf{srank}\left(\frac{C}{\log(d/\epsilon)}\mathbf{G}\right)=\mathsf{srank}(\mathbf{G})=\frac{\|\mathbf{G}\|_F^2}{\|\mathbf{G}\|^2}\ge \frac{d}{(1+1.2\epsilon)^2}\geq (1+1.3\epsilon)d_0,
\end{equation}
with sample size $\mathcal{O}(d^2/\epsilon^2)$, provided that $\epsilon$ is sufficiently small.


We now show that $\frac{C}{\log(d/\epsilon)}\mathbf{G}$ is rigid, i.e., changing $\epsilon_0/d_0$-fraction of entries of $\frac{C}{\log(d/\epsilon)}\mathbf{G}$ will not make $\mathsf{srank}\left(\frac{C}{\log(\frac{d}{\epsilon})}\mathbf{G}\right)\le d_0$. For any $\S\in\mathbb{R}^{(d/\epsilon^2)\times d}$ such that $\|\S\|_0=\frac{\theta d}{\epsilon\log^2(\frac{d}{\epsilon})}$ (where $0<\theta<1$) and $\left\|\frac{C}{\log(\frac{d}{\epsilon})}\mathbf{G}+\S\right\|_\infty\le 1$ (thus $\S$ has an $\frac{\epsilon_0}{d_0}$-fraction of non-zero entries and $\|\S\|_\infty\le 2$), we have
\begin{equation*}
\begin{split}
&\quad\ \left\|\frac{C}{\log(d/\epsilon)}\mathbf{G}+\S\right\|^2\\
&=\sup_{\|\u\|_2=1,\|\v\|_2=1} \left\langle\left(\frac{C}{\log(d/\epsilon)}\mathbf{G}+\S\right)\u,\v\right\rangle^2\\
&\le \frac{C^2}{\log^2(d/\epsilon)}\sup_{\substack{\|\u\|_2=1\\ \|\v\|_2=1}} \langle \mathbf{G}\u,\v\rangle^2+ \sup_{\substack{\|\u\|_2=1\\ \|\v\|_2=1}} \langle\S\u,\v\rangle^2+\frac{2C}{\log(d/\epsilon)}\sup_{\substack{\|\u\|_2=1\\ \|\v\|_2=1}} \langle\mathbf{G}^\top\S\u,\v\rangle\\
&= \frac{C^2}{\log^2(d/\epsilon)}\|\mathbf{G}\|^2+\|\S\|^2+\frac{2C}{\log(d/\epsilon)}\|\mathbf{G}^\top\S\|\\
&\le \frac{C^2}{\log^2(d/\epsilon)}\|\mathbf{G}\|^2+\|\S\|^2+\frac{2C}{\log(d/\epsilon)}\|\mathbf{G}^\top\| \|\S\|\\
&\le \frac{C^2}{\log^2(d/\epsilon)}\|\mathbf{G}\|^2+\|\S\|_F^2+\frac{2C}{\log(d/\epsilon)}\|\mathbf{G}^\top\| \|\S\|_F
\end{split}
\end{equation*}
Now, observe that
\[
\|\S\|_F^2\le \frac{4 \theta d}{\epsilon\log^2(d/\epsilon)}
\]
and that, by setting $t = O(\sqrt{d}/\epsilon)$ in Lemma~\ref{lemma: vershynin concentration of Gaussian operator norm},
\[
\|\mathbf{G}\| = \mathcal{O}\left(\frac{\sqrt{d}}{\epsilon}\right)
\]
with probability at least $1-2\exp(-\Omega(d/\epsilon^2))$, we have that
\begin{equation}\label{eqn:upper_bound_perturbed}
\left\|\frac{C}{\log(d/\epsilon)}\mathbf{G}+\S\right\|^2\le \frac{C^2}{\log^2(d/\epsilon)}\|\mathbf{G}\|^2+\mathcal{O}\left(\frac{(\theta+\sqrt{\theta})d}{\epsilon\log^2(d/\epsilon)}\right)\le \left(1+c_1\sqrt{\theta}\epsilon\right)\frac{C^2}{\log^2(d/\epsilon)}\|\mathbf{G}\|^2,
\end{equation}
where $c_1 > 0$ is an absolute constant.

On the other hand, with probability at least $1-c'\exp(-\Omega(d/\epsilon))$ it holds that
\begin{equation}\label{eqn:lower_bound_perturbed}
\begin{aligned}
\left\|\frac{C}{\log(d/\epsilon)}\mathbf{G}+\S\right\|_F^2
&\ge \left(\frac{C}{\log(d/\epsilon)}\|\mathbf{G}\|_F - \|\S\|_F\right)^2\\
&\ge \left(1-c_2\sqrt{\frac{\epsilon \theta}{d}}\right)\frac{C^2}{\log^2(d/\epsilon)}\|\mathbf{G}\|_F^2,
\end{aligned}
\end{equation}
where $c_2 > 0$ is an absolute constant.

Therefore,
\begin{equation*}
\mathsf{srank}\left(\frac{C}{\log(d/\epsilon)}\mathbf{G}+\S\right)\ge \left(1-c_3\sqrt{\theta}\epsilon\right)\mathsf{srank}\left(\frac{C}{\log(d/\epsilon)}\mathbf{G}\right)>d_0,
\end{equation*}
where $c_3 > 0$ is an absolute constant, and $\theta$ is small enough such that the last inequality holds.

We conclude that $\frac{C}{\log(d/\epsilon)}\mathbf{G}$ is $\epsilon_0/d_0$-far from having stable rank $\le d_0$. The proof is complete.
\end{proof}










\section{Non-Adaptive Testing of Schatten-$p$ Norm}

We study the problem of testing Schatten-$p$ norms in this section.





\subsection{Upper Bounds}

\begin{problem}[Schatten-$p$ Norm Testing in the Bounded Entry Model for $p>2$]
Let $p>2$ and $\mathbf{A}\in\mathbb{R}^{n\times n}$ be a matrix such that $\|\mathbf{A}\|_\infty\leq 1$. For an absolute constant $c$, the matrix $\mathbf{A}$ satisfies one of the promised properties:
\begin{itemize}
\item[$\mathsf{H0.}$]
$\|\mathbf{A}\|_{\mathcal{S}_p}^p\geq cn^{p}$;
\item[$\mathsf{H1.}$]
$\mathbf{A}$ is $\epsilon$-far from $\|\mathbf{A}\|_{\mathcal{S}_p}^p\geq cn^{p}$, meaning that it requires changing at least an $\epsilon$-fraction of the entries of $\mathbf{A}$ such that that $\|\mathbf{A}\|_{\mathcal{S}_p}^p\geq cn^{p}$.
\end{itemize}
The problem is to design a non-adaptive property testing algorithm that outputs $\mathsf{H0}$ with probability at least $0.9$ if $\mathbf{A}\in \mathsf{H0}$, and output $\mathsf{H1}$ with probability at least $0.99$ if $\mathbf{A}\in\mathsf{H1}$, with the least number of queried entries.
\end{problem}

First we prove a lemma showing that $\mathsf{H0}$ and $\mathsf{H1}$ can be distinguished by the Schatten $p$-norm.
\begin{lemma}\label{lem:schatten_norm_gap}
Suppose that $p>2$ is a constant. There exist constants $c = c(p)$, $C = C(p)$ and $\epsilon_0 = \epsilon(p)$ such that for any $\epsilon \in [C/n, \epsilon_0]$, when $\mathbf{A}\in \mathsf{H1}$ it holds that $\|\mathbf{A}\|_{\mathcal{S}_p}^p\leq (c-c'\epsilon)n^p$ for some small constant $c'$ that may depend on $p$.
\end{lemma}
\begin{proof}
Assume that $\|\mathbf{A}\|_{\mathcal{S}_p}^p \geq c_1 n^p$ for some constant $c_1 < c$, otherwise there is already a constant-factor gap. Together with the assumption that $\|\mathbf{A}\|_\infty\leq 1$ and thus $\|\mathbf{A}\|_F^2\leq n^2$, it must hold that $\|\mathbf{A}\| \geq c_2 n$ for $c_2 = c_1^{1/(p-1)}$.

We claim that we can find a set $T$ of $\epsilon n$ rows such that $\|\mathbf{A}_{T^c,:}\|_{\mathcal{S}_p}^p \geq (1-C'\epsilon)\|\mathbf{A}\|_{\mathcal{S}_p}^p$ for some $C'$ (which may depend on $p$) and therefore $\|\mathbf{A}_{T^c,:}\| \geq c_2' n$, where $\mathbf{A}_{T^c,:}$ stands for a submatrix of $\mathbf{A}$ with rows restricted on the set $T^c$. Consider a random subset $T$ formed by including rows independently with probability $\epsilon$, that is, let $\delta_i$ be the indicator variable whether $i\in T$ and $\bbE \delta_i = \epsilon$. Denote by $\mathbf{A}_{i,:}\in\mathbb{R}^{1\times n}$ the $i$-th row of $\mathbf{A}$. Then we have, by the standard symmetrization trick (see, e.g.,~\cite[Lemma 6.3]{LT91}), that
\begin{align*}
\bbE_{\delta_i}\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}^2 = \bbE_{\delta_i}\left\|\sum_i \delta_i \mathbf{A}_{i,:}^\top \mathbf{A}_{i,:}\right\|_{\mathcal{S}_{p/2}}  &\le  \bbE_{\delta_i}\left(\left\|\sum_i (\delta_i-\epsilon) \mathbf{A}_{i,:}^\top \mathbf{A}_{i,:}\right\|_{\mathcal{S}_{p/2}} + \left\| \sum_i \epsilon \mathbf{A}_{i,:}^\top\mathbf{A}_{i,:} \right\|_{\mathcal{S}_{p/2}} \right)\\
&\leq 2\bbE_{\delta_i}\bbE_{\epsilon_i}\left\| \sum_i \epsilon_i\delta_i \mathbf{A}_{i,:}^\top\mathbf{A}_{i,:} \right\|_{\mathcal{S}_{p/2}} + \epsilon\|\mathbf{A}\|_{\mathcal{S}_p}^2,
\end{align*}
where $\epsilon_i$'s are i.i.d.\ $\{\pm 1\}$-valued Rademacher variables with $\Pr(\epsilon_i=+1)=\Pr(\epsilon_i=-1)=1/2$.
Applying the Non-Commutative Khintchine Inequality (abbreviated as NCKI)~\cite{LP86} yields that
\begin{align*}
\bbE_{\epsilon_i}\left\| \sum_i \epsilon_i\delta_i \mathbf{A}_{i,:}^\top\mathbf{A}_{i,:} \right\|_{\mathcal{S}_{p/2}}
&\leq \left(\bbE_{\epsilon_i}\left\| \sum_i \epsilon_i\delta_i \mathbf{A}_{i,:}^\top\mathbf{A}_{i,:} \right\|_{\mathcal{S}_{p/2}}^{p/2}\right)^{2/p}\quad (\text{by Jensen's inequality})\\
&\leq C_1\sqrt{\frac{p}{2}} \left\|\left(\sum_i \delta_i (\mathbf{A}_{i,:}^\top\mathbf{A}_{i,:})^2\right)^{\frac12}\right\|_{\mathcal{S}_{p/2}}\quad (\text{by NCKI})\\
&\leq C_1\sqrt{\frac{p}{2}} \left\|\max_i \|\mathbf{A}_{i,:}\|_2 \cdot \left(\sum_i \delta_i\mathbf{A}_{i,:}^\top\mathbf{A}_{i,:}\right)^{\frac12}\right\|_{\mathcal{S}_{p/2}}\\
&\leq C_1\sqrt{\frac{p}{2}} \sqrt{n} \|\mathbf{A}_{T,:}\|_{\mathcal{S}_{p/2}}\\
&\leq C_1\sqrt{\frac{p}{2}} n^{\frac12}|T|^{\frac1p} \|\mathbf{A}_{T,:}\|_{\mathcal{S}_p},\quad (\text{by H\"older's inequality})
\end{align*}
where the third inequality holds since $\sum_i \delta_i(\mathbf{A}_{i,:}^\top\mathbf{A}_{i,:})^2\preceq \max_i \|\mathbf{A}_{i,:}\|_2^2\cdot \sum_i\delta_i \mathbf{A}_{i,:}^\top\mathbf{A}_{i,:}$.
Hence, taking expectation on both sides w.r.t.\ $\delta_i$,
\begin{align*}
\bbE\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}^2 &\leq C_1\sqrt{\frac{p}{2}}n^{\frac{1}{2}} (\bbE|T|^{\frac 2p})^{\frac{1}{2}} (\bbE\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}^2)^{\frac 12} + \epsilon\|\mathbf{A}\|_{\mathcal{S}_p}^2 \quad (\text{by Cauchy-Schwarz inequality})\\
&\leq C_1\sqrt{\frac{p}{2}}n^{\frac{1}{2}} (\bbE|T|)^{\frac{1}{p}} (\bbE\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}^2)^{\frac 12} + \epsilon\|\mathbf{A}\|_{\mathcal{S}_p}^2\quad (\text{by Jensen's inequality})\\
&\leq C_1\sqrt{\frac{p}{2}} n^{\frac12}(\epsilon n)^{\frac 1p} (\bbE\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}^2)^{\frac 12} + \epsilon\|\mathbf{A}\|_{\mathcal{S}_p}^2,
\end{align*}
whence we can solve that
\[
\bbE\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}^2 \leq C_1^2 \frac{p}{2}\epsilon^{\frac2p}n^{1+\frac2p} + 4\epsilon\|\mathbf{A}\|_{\mathcal{S}_p}^2 \leq C_2\epsilon\|\mathbf{A}\|_{\mathcal{S}_p}^2.
\]
That is, we can find $T$ such that $\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}^2\leq C_2\epsilon\|\mathbf{A}\|_{\mathcal{S}_p}^2$ and thus
\[
\|\mathbf{A}_{T^c,:}\|_{\mathcal{S}_p}^2 = \|\mathbf{A}_{T^c,:}^\top\mathbf{A}_{T^c,:}\|_{\mathcal{S}_{p/2}} = \|\mathbf{A}^\top\mathbf{A} - \mathbf{A}_{T,:}^\top\mathbf{A}_{T,:}\|_{\mathcal{S}_{p/2}}\geq (1-C_2\epsilon)\|\mathbf{A}^\top\mathbf{A}\|_{\mathcal{S}_{p/2}} = (1-C_2\epsilon)\|\mathbf{A}\|_{\mathcal{S}_p}^2
\]
as desired. A Chernoff bound shows that $|T|\geq 0.9\epsilon n$ with at least a high constant probability. We can assume that it happens, since conditioning on this event will increase $\bbE\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}^2$ just by a constant factor. When $|T| > \epsilon n$ we can just remove rows from $T$, which only decreases $\|\mathbf{A}_{T,:}\|_{\mathcal{S}_p}$.

Let $\v$ be the normalized eigenvector associated with the largest eigenvalue of $\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:}$. We shall change the rows of $T$ all to $\tilde\v := \operatorname{sgn}(\v)$, obtaining a matrix $\mathbf{B}$. Note that $\mathbf{B}^\top \mathbf{B} = \mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:} + |T| \v\v^\top\succeq \mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:}$ is a rank-$1$ PSD perturbation of $\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:}$ and $\v$ is the leading eigenvector of $\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:}$, we have that for the $i$-th eigenvalue $\lambda_i(\cdot)$,
\[
\lambda_i(\mathbf{B}^\top\mathbf{B}) \geq \lambda_i(\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:}),\quad i\geq 2.
\]
and the largest eigenvalue
\begin{align*}
\lambda_1(\mathbf{B}^\top\mathbf{B}) &= \sup_{\mathbf{x}: \|\mathbf{x}\|_2 = 1} \mathbf{x}^\top (\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:} + \epsilon n \tilde{\v} \tilde{\v}^\top)\mathbf{x} \\
&\geq \v^\top (\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:} + |T| \tilde{\v} \tilde{\v}^\top)\v \\
&= \lambda_1(\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:}) + |T| \|\v\|_1^2.
\end{align*}
Observe that
\[
\lambda_1(\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:}) = \|\mathbf{A}_{T^c,:} \v\|_2^2 = \sum_{i\in T^c} \langle \mathbf{A}_{i,:},\v\rangle^2 \leq \sum_{i\in T^c} \|\mathbf{A}_{i,:}\|_\infty^2 \|\v\|_1^2 \leq (n-|T|) \|\v\|_1^2.
\]
Then
\[
\lambda_1(\mathbf{B}^\top\mathbf{B}) \geq \left(1+\frac{0.9\epsilon}{1-\epsilon}\right)\lambda_1(\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:})
\]
and so
\begin{align*}
c n^p > \|\mathbf{B}\|_{\mathcal{S}_p}^p &\geq \left(1+\frac{0.9\epsilon}{1-\epsilon}\right)^{\frac p2}\lambda_1^{\frac{p}{2}}(\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:}) + \sum_{i\geq 2} \lambda_i^{\frac p2}(\mathbf{A}_{T^c,:}^\top \mathbf{A}_{T^c,:})\\
&\geq \left(\left(1+\frac{0.9\epsilon}{1-\epsilon}\right)^{\frac p2}-1\right)(c_2' n)^p + \|\mathbf{A}_{T^c,:}\|_{\mathcal{S}_p}^p\\
&\geq c_3 p \epsilon n^p + (1-C'\epsilon)\|\mathbf{A}\|_{\mathcal{S}_p}^p,
\end{align*}
whence it follows that
\[
\|\mathbf{A}\|_{\mathcal{S}_p}^p \leq (c - (c_3 p - c C') \epsilon) n^p,
\]
provided that $c$ and $\epsilon$ are sufficiently small.
\end{proof}


\begin{algorithm}
\caption{Algorithm for Schatten-$p$ norm testing ($p>2$)}
\label{algorithm: algorithm for the Schatten-$p$ norm testing problem}
\begin{algorithmic}[1]
\LineComment Lines 1-2 estimate the Frobenius norm of $\mathbf{A}$.
\State Uniformly sample $q_0=\mathcal{O}(\frac{1}{\epsilon^2})$ entries $\mathbf{A}$, forming vector $\mathbf{y}$.
\State $X\leftarrow \frac{n^2}{q_0}\|\mathbf{y}\|_2^2$.  \Comment{$X$ is an estimator of $\|\mathbf{A}\|_F^2$}.
\State Uniformly sample a $q\times q$ submatrix $\widetilde\mathbf{A}'$ with $q=\mathcal{O}(\frac{\log n}{\epsilon})$.
\If {$\|\widetilde\mathbf{A}'\|\le C_0\sqrt{X}\frac{q}{n}$}
	\State Output ``$\mathbf{A}\in\mathsf{H1}$''.
\Else
	\State Run Algorithm \ref{algorithm: the sampling algorithm for even p} with $\tau=\Theta(\epsilon^{p/(p-2)}/p)$ and obtain indices $\mathcal{I}_{\mathsf{row}}$ and $\mathcal{I}_{\mathsf{col}}$. \label{alg: step 7}
	\State $\mathbf{A}_0\gets \mathbf{A}_{\mathcal{I}_{\mathsf{row}},\mathcal{I}_{\mathsf{col}}}$. \label{alg: step 8}
	\State $\mathcal{I}\gets \{i\mid \sigma_i(\mathbf{A}_0) > (1+\epsilon/(3p))n(c\epsilon/3)^{1/(p-2)}\}$. \label{alg: step 9}
	\If {$\sum_{i\in\mathcal{I}}\sigma_i^p(\mathbf{A}_0)\ge cn^p$}  \label{alg: step 10}
		\State Output ``$\mathbf{A}\in\mathsf{H0}$''.
	\Else
		\State Output ``$\mathbf{A}\in\mathsf{H1}$''.
	\EndIf
\EndIf
\end{algorithmic}
\end{algorithm}



\begin{theorem}
\label{theorem: Schatten-p norm upper bound}
Let $p>2$ be a constant, and $c$ and $\epsilon$ be as in Lemma~\ref{lem:schatten_norm_gap}. Then Algorithm \ref{algorithm: algorithm for the Schatten-$p$ norm testing problem} is a correct algorithm for the Schatten-$p$ norm testing problem under the sampling model with probability at least $0.99$. It reads $\mathcal{O}\left(\frac{\log^2 n}{\epsilon^{4p/(p-2)}}\right)$ entries.
\end{theorem}



\begin{proof}

When $\mathbf{A}\in \mathsf{H0}$, we claim that $\mathsf{srank}(\mathbf{A})=\mathcal{O}(1)$ which is independent of $n$ and $1/\epsilon$. Otherwise, suppose $\mathsf{srank}(\mathbf{A})=f(n,1/\epsilon)$. Then $\|\mathbf{A}\|=\|\mathbf{A}\|_F/\sqrt{\mathsf{srank}(\mathbf{A})}\le n/f(n,1/\epsilon)=o(n)$. In this case, $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ is maximized when the first $r$ singular values are equal to $\|\mathbf{A}\|$, where $r\le n^2/\|\mathbf{A}\|^2$ in order to satisfy $\|\mathbf{A}\|_F\le n$. So the maximal $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ is $r\|\mathbf{A}\|^p\le n^2\|\mathbf{A}\|^{p-2}=o(n^p)$, which leads to a contradiction with $\mathbf{A}\in\mathsf{H0}$. That is, $\mathsf{srank}(\mathbf{A})$ is an absolute constant which is independent of $n$ and $1/\epsilon$, say $4e^2$. Thus, when $\mathbf{A}\in\mathsf{H0}$ we have $\|\mathbf{A}\|=\Theta(n)$ and $\|\mathbf{A}\|_F=\Theta(n)$, because
$
n\ge \|\mathbf{A}\|_F\ge \|\mathbf{A}\|_{\mathcal{S}_p}\ge c^{1/p}n.
$

We note that by sampling $q_0$ entries from $\mathbf{A}$ and stacking them as vector $\mathbf{y}$, the resulting estimator $X=\frac{n^2}{q_0^2}\|\mathbf{y}\|_2^2$ satisfies $\mathbb{E}[X]=\|\mathbf{A}\|_F^2$ and $\mathsf{Var}[X]\le n^2(n^4/q_0^2)(q_0/n^2)=n^4/q_0$. Taking $q_0=\mathcal{O}(1/\epsilon^2)$,  we have, by Chebyshev's inequality, that
\begin{equation*}
\Pr\left[|X-\|\mathbf{A}\|_F^2|>\epsilon n^2\right]\le \frac{n^4/q_0}{\epsilon^2 n^4}\le 0.999.
\end{equation*}
Thus with constant probability,
$
\left|X-\|\mathbf{A}\|_F^2\right| \le \epsilon n^2.
$

We argue that uniformly sampling an $\mathcal{O}(\log (n)/\epsilon)\times \mathcal{O}(\log(n)/\epsilon)$ submatrix of $\mathbf{A}$ suffices to distinguish $\mathsf{srank}(\mathbf{A})\le 4e^2$ v.s. $\mathsf{srank}(\mathbf{A})> 4c_1e^2$ for a large absolute constant $c_1$ with a constant probability. To see this, when $\mathsf{srank}(\mathbf{A})> 4c_1e^2$, let $\mathbf{U}$ be a uniformly random $n\times n$ orthogonal matrix and let $\mathbf{A}_{\mathsf{row}}'$ be the matrix after uniform row sampling of $\mathbf{A}$ of expected cardinality $q$. Note that $\|\mathbf{A}_{\mathsf{row}}'\|=\|\mathbf{A}_{\mathsf{row}}'\mathbf{U}\|$, and $(\mathbf{A}\mathbf{U})_{i,:}=\mathbf{A}_{i,:}\mathbf{U}$ is uniform on $\|\mathbf{A}_{i,:}\|_2\cdot\mathbb{S}^{n-1}$. So $\|\mathbf{A}_{i,:}\mathbf{U}\|_\infty^2\le 2\|\mathbf{A}_{i,:}\mathbf{U}\|_2^2\log (n)/n$ for any fixed $i$ with probability at least $1-1/n^2$ by Lemma \ref{Lemma: infty norm of uniform sampling from unit sphere}. Therefore, with probability at least $1-1/n$ by union bound over all rows, $\|\mathbf{A}\mathbf{U}\|_{\mathsf{col}}^2\le 2\|\mathbf{A}\|_F^2\log (n)/n$, where $\|\mathbf{A}\|_{\mathsf{col}}$ represents the maximum $\ell_2$ norm among all columns of $\mathbf{A}$. By Lemma \ref{Lemma: Vershynin},
\begin{equation*}
\mathbb{E}\|\mathbf{A}_{\mathsf{row}}'\|\le C_1'\sqrt{\frac{q}{n}}\|\mathbf{A}\|+C_2'\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F
\end{equation*}
for absolute constants $C_1'$ and $C_2'$, and by a Markov bound, with probability at least $0.999$,
\begin{equation*}
\begin{split}
\|\mathbf{A}_{\mathsf{row}}'\|&\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\\
&\le C_1\sqrt{\frac{q}{n}}\frac{\|\mathbf{A}\|_F}{\sqrt{4c_1 e^2}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\quad(\text{since }\mathsf{srank}(\mathbf{A})>4c_1 e^2)
\end{split}
\end{equation*}
for absolute constants $C_1$ and $C_2$. By a Markov bound, we also have with constant probability that
\begin{equation*}
\|\mathbf{A}_{\mathsf{row}}'\|_F^2\le c\frac{q}{n}\|\mathbf{A}\|_F^2.
\end{equation*}
Conditioning on this event, by applying the same argument on the column sampling of $\mathbf{A}_{\mathsf{row}}'$, we have
\begin{equation*}
\begin{split}
\|\widetilde\mathbf{A}'\|&\le C_1\sqrt{\frac{q}{n}}\|\mathbf{A}_{\mathsf{row}}'\|+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}_{\mathsf{row}}'\|_F\\
&\le C_1\sqrt{\frac{q}{n}} \left(C_1\sqrt{\frac{q}{n}}\frac{\|\mathbf{A}\|_F}{\sqrt{4c_1 e^2}}+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\|\mathbf{A}\|_F\right)+C_2\sqrt{\log q}\sqrt{\frac{\log n}{n}}\sqrt{\frac{cq}{n}}\|\mathbf{A}\|_F\\
&\le C_0\frac{\|\mathbf{A}\|_F}{\sqrt{4c_1e^2}}\frac{q}{n},\qquad(\text{because the first term dominates as } q\gg \text{a constant})
\end{split}
\end{equation*}
where $\widetilde\mathbf{A}'$ is the matrix after the column sampling of $\mathbf{A}_{\mathsf{row}}'$, and $C_0$ is an absolute constant.
On the other hand, when $\mathsf{srank}(\mathbf{A})\le 4e^2$ and $q=\mathcal{O}(\frac{\log n}{\epsilon})$, we have with high probability that
\begin{equation*}
\|\widetilde\mathbf{A}'\|\ge C\frac{q}{n}\|\mathbf{A}\|= C\frac{q}{n}\frac{\|\mathbf{A}\|_F}{\sqrt{\mathsf{srank}(\mathbf{A})}}\ge C\frac{q}{n}\frac{\|\mathbf{A}\|_F}{\sqrt{4e^2}},
\end{equation*}
where the first inequality holds by applying Lemma \ref{lemma: Ismail} twice on row and column sampling (set $\beta=\Theta(\epsilon)$ and $\tau=\Theta(1)$ there). By setting $c_1$ as a large absolute constant, we have
\begin{equation*}
C_0\frac{\|\mathbf{A}\|_F}{\sqrt{4c_1e^2}}\frac{q}{n} < C\frac{q}{n}\frac{\|\mathbf{A}\|_F}{\sqrt{4e^2}}.
\end{equation*}
Thus we can distinguish (a) $\mathsf{srank}(\mathbf{A})\le 4e^2$ and (b) $\mathsf{srank}(\mathbf{A})>4c_1e^2$ by checking $\|\widetilde\mathbf{A}'\|$. If we find $\mathsf{srank}(\mathbf{A})> 4c_1e^2$, then we can safely output ``$\mathbf{A}\in \mathsf{H1}$''. Therefore, in the following we can assume $\mathsf{srank}(\mathbf{A})\le 4c_1e^2$.

Recall that, according to Lemma~\ref{lem:schatten_norm_gap}, there is a multiplicative gap in the Schatten-$p$ norm between case $\mathsf{H0}$ and case $\mathsf{H1}$. Without loss of generality, we assume $\|\mathbf{A}\|_{\mathcal{S}_p}^p=(1\pm\epsilon)cn^p$ in the following, which represents the hardest case to distinguish $\mathsf{H0}$ from $\mathsf{H1}$. In that case, $\mathsf{srank}(\mathbf{A})=\mathcal{O}(1)$ and $\|\mathbf{A}\|_F^2=\Theta(n^2)$, as we have shown in the beginning of the proof.


We now show that with $\mathsf{poly}(1/\epsilon)$ sampled entries, we can have an estimator which approximates $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ up to $(1\pm\epsilon)$ factor; therefore, we can distinguish $\mathsf{H0}$ from $\mathsf{H1}$ due to the gap of $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ in the two cases.
Consider all singular values of $\mathbf{A}$ which are at most $n/\sqrt{r}$ and consider $\|\mathbf{A}\|_{\mathcal{S}_p}^p$. This is maximized when there are as many singular values as possible that are equal to $n/\sqrt{r}$. Note that there can be at most $r$ singular values of value $n/\sqrt{r}$, since $\|\mathbf{A}\|_F^2 \leq n^2$ for $\|\mathbf{A}\|_\infty\leq 1$. Therefore, the total contribution of singular values which are no larger than $n/\sqrt{r}$ is at most $n^p r^{1-p/2}$. So if $r=(c\epsilon/3)^{\frac{2}{2-p}}$, this quantity is at most $c\epsilon n^p/3$. Thus all singular values less than $n(c\epsilon/3)^{\frac{1}{p-2}}$ contribute not too much, at most $c\epsilon n^p/3$. For the remaining singular values (i.e., $\sigma_i(\mathbf{A})>n(c\epsilon/3)^{\frac{1}{p-2}}$), by Theorem \ref{theorem: operator norm estimator by Ismail}, with $\mathcal{O}\left(\frac{p^4}{\epsilon^{4p/(p-2)}}\log^2 n\right)$ samples we have
\begin{equation*}
\begin{split}
\left|\sigma_i^2(\mathbf{A})-\sigma_i^2(\mathbf{A}_0)\right|&=\left|\sigma_i(\mathbf{A}^\top\mathbf{A})-\sigma_i(\mathbf{A}_0^\top\mathbf{A}_0)\right|\le \|\mathbf{A}^\top\mathbf{A}-\mathbf{A}_0^\top\mathbf{A}_0\|\le \frac{2\epsilon}{3p}\left(\frac{c\epsilon}{3}\right)^{\frac{2}{p-2}}\|\mathbf{A}\|^2 \\
&\le \frac{2\epsilon}{3p}\left(\frac{c\epsilon}{3}\right)^{\frac{2}{p-2}} n^2<\frac{2\epsilon}{3p}\sigma_i^2(\mathbf{A}),
\end{split}
\end{equation*}
namely, $\sigma_i^p(\mathbf{A}_0) = (1\pm\epsilon/3)\sigma_i^p(\mathbf{A})$. Therefore,
\begin{equation*}
\sum_{i:\ \sigma_i(\mathbf{A}) > n(c\epsilon/3)^{1/(p-2)}} \sigma_i^p(\mathbf{A}_0)= (1\pm \epsilon/3)\sum_{i:\ \sigma_i(\mathbf{A}) > n(c\epsilon/3)^{1/(p-2)}} \sigma_i^p(\mathbf{A})= (1\pm 2\epsilon/3)\|\mathbf{A}\|_{\mathcal{S}_p}^p,
\end{equation*}
where the last $\subseteq$ holds because all singular values less than $n(c\epsilon/3)^{\frac{1}{p-2}}$ contribute at most $c\epsilon n^p/3$. Let $\mathcal{I}=\{i\mid \sigma_i(\mathbf{A}_0) > (1+\epsilon/(3p))n(c\epsilon/3)^{1/(p-2)}\}$ and $\mathcal{J}=\{i\mid \sigma_i(\mathbf{A}) > n(c\epsilon/3)^{1/(p-2)}\}$. We note that $\mathcal{I}\subseteq \mathcal{J}$, and that all singular values of $\mathbf{A}$ less than $(1+\epsilon/(3p))n(c\epsilon/3)^{\frac{1}{p-2}}$ contribute not too much, at most $c\epsilon n^p/2$, by a similar analysis as above. Therefore, those singular values of $\mathbf{A}$ that lie in $\mathcal{J}\backslash\mathcal{I}$ contribute at most $c\epsilon n^p/6$, and by the relation $\sigma_i^p(\mathbf{A}_0) = (1\pm\epsilon/3)\sigma_i^p(\mathbf{A})$ for all $i\in\mathcal{J}$, those singular values of $\mathbf{A}_0$ that lie in $\mathcal{J}\backslash\mathcal{I}$ contribute at most $c\epsilon n^p/5$.
Therefore
\begin{equation*}
\sum_{i\in\mathcal{I}} \sigma_i^p(\mathbf{A}_0)=\sum_{i\in\mathcal{J}} \sigma_i^p(\mathbf{A}_0)\pm \frac{c\epsilon n^p}{5} =(1\pm \epsilon)\|\mathbf{A}\|_{\mathcal{S}_p}^p,
\end{equation*}
as desired.
\end{proof}











\subsection{Lower Bounds}

\begin{problem}[Schatten-$p$ Norm Testing in the Bounded Entry Model for $p\in [1,2)$]
Let $p\in [1,2)$ and $\mathbf{A}\in\mathbb{R}^{n\times n}$ with $\|\mathbf{A}\|_\infty\leq 1$. For a constant $c$, the matrix $\mathbf{A}$ satisfies one of the promised properties:
\begin{itemize}
\item[$\mathsf{H0.}$]
$\|\mathbf{A}\|_{\mathcal{S}_p}^p\geq cn^{1+p/2}$;
\item[$\mathsf{H1.}$]
$\mathbf{A}$ is $\epsilon$-far from $\|\mathbf{A}\|_{\mathcal{S}_p}^p\geq cn^{1+p/2}$, meaning that it requires changing at least an $\epsilon$-fraction of entries of $\mathbf{A}$ such that $\|\mathbf{A}\|_{\mathcal{S}_p}^p\geq cn^{1+p/2}$.
\end{itemize}
The problem is to design a non-adaptive property testing algorithm that outputs $\mathsf{H0}$ with probability at least $0.9$ if $\mathbf{A}\in \mathsf{H0}$, and output $\mathsf{H1}$ with probability at least $0.9$ if $\mathbf{A}\in\mathsf{H1}$, with the least number of queried entries.
\end{problem}

Suppose that $\mathbf{G}\sim \mathcal{G}(n,n)$ and $\mathbf{O}$ is a random $n\times n$ orthogonal matrix. Consider two distributions $\mathcal{D}_1 = \frac{1+\eta}{\sqrt n}\mathbf{G}$ and $\mathcal{D}_2 = \mathbf{O} + \frac{\eta}{\sqrt n}\mathbf{G}$, where $\eta > 0$ is a small absolute constant. The following lemma comes from a manuscript of Li et al.~\cite{LNW:schatten_unpublished}.

\begin{lemma}[\cite{LNW:schatten_unpublished}]
\label{lem:schatten_p_lb_hard_instance}
Consider a linear sketch of length $m$ for random matrices drawn from $\mathcal{D}_1$ or $\mathcal{D}_2$. Let $\mathcal{L}_1$ and $\mathcal{L}_2$ be the induced distribution of the linear sketch of $\mathcal{D}_1$ and $\mathcal{D}_2$, respectively. There exists $\alpha = \alpha(\eta)\in (0,1)$ such that whenever $m\leq \alpha n$, it holds that $d_{TV}(\mathcal{L}_1,\mathcal{L}_2) < 1/10$.
\end{lemma}



\begin{theorem}
\label{thm:schatten_p_lb}
Let $p\in [1,2)$ be a constant. There exist constants $c = c(p)$ and $\epsilon_0 = \epsilon_0(p)$ such that for any $\epsilon \leq \epsilon_0$ and $\mathbf{A}\in\mathbb{R}^{n\times n}$, any non-adaptive algorithm that correctly tests $\mathsf{H0}$ against $\mathsf{H1}$ with probability at least $0.99$ must make $\Omega(n)$ queries (i.e., the sketch size is $\Omega(n)$). 
\end{theorem}
\begin{proof}
Consider the hard distributions $\mathcal{D}_1$ and $\mathcal{D}_2$ for Lemma~\ref{lem:schatten_p_lb_hard_instance}. For $p<2$, it is a well-known fact that with high probability over $\mathbf{G}\sim \mathcal{G}(n,n)$, it holds that $\|\frac{1}{\sqrt n}\mathbf{G}\| \leq 2(1+o(1))$ and $\|\frac{1}{\sqrt n}\mathbf{G}\|_{\mathcal{S}_p}^p \leq (1+o(1))c_p n$ for some constant $c_p < 1$ that depends only on $p$. Hence with high probability, when $\mathbf{A}\sim \mathcal{D}_1$, it holds that $\|\mathbf{A}\|_{\mathcal{S}_p}^p \leq (1+o(1))(1+\eta)c_p n$. On the other hand, with high probability, when $\mathbf{A}\sim \mathcal{D}_2$, it follows from the triangle inequality that $\|\mathbf{A}\|_{\mathcal{S}_p}^p\geq (1-(1+o(1))\eta c_p^{1/p})^p n$. Therefore, when $\eta$ is sufficiently small (depending on $p$ only), there is a constant-factor multiplicative gap in $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ between $\mathcal{D}_1$ and $\mathcal{D}_2$.

Let $C$ be a large constant to be determined. We truncate $\mathcal{D}_1$ and $\mathcal{D}_2$ by applying the map
\[
x\mapsto \max\left\{\min\left\{x, \frac{C}{\sqrt n}\right\}, -\frac{C}{\sqrt n}\right\}
\]
entrywise to the matrices, resulting in two new distributions $\widetilde \mathcal{D}_1$ and $\widetilde \mathcal{D}_2$. We claim that with high probability, there remains a constant-factor multiplicative gap in $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ between $\widetilde\mathcal{D}_1$ and $\widetilde\mathcal{D}_2$. It suffices to show that with high probability, truncation incurs only a change of $c n$ for some small constant $c>0$ in $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ for both $\mathcal{D}_1$ and $\mathcal{D}_2$.

Suppose that $\mathbf{A}\sim \mathcal{D}_1$, and let $\widetilde \mathbf{A}$ be the truncated matrix. We can write $\widetilde\mathbf{A} = \mathbf{A} + \frac{1}{\sqrt n}\mathbf{B}$, where $\mathbf{B}$ is a random matrix with i.i.d.\ entries following a truncated Gaussian distribution $\tilde\mathcal{N}_C(0,1)$ whose probability density function is
\[
f_C(t) = (1-p_C)\delta(t) + \frac{1}{\sqrt{2\pi}}\exp\left(-\frac{(|t|+C)^2}{2}\right),
\]
where $\delta(t)$ is the Dirac delta function and
\[
p_C = \frac{2}{\sqrt{2\pi}}\int_{C}^{\infty}\exp\left(-\frac{x^2}{2}\right)dx =: \erfc\left(\frac{C}{\sqrt 2}\right).
\]
One can also calculate that
\begin{equation}
\label{equ: m_C}
m_C := \bbE|\mathbf{B}_{ij}|^2
\end{equation}
has a subgaussian decay w.r.t.\ $C$. It follows from a Chernoff bound that $\|\mathbf{B}\|_F^2\leq 2m_C n^2$ with high probability. Since $\|\mathbf{B}\|_{\mathcal{S}_p} \leq n^{\frac1p-\frac12}\|\mathbf{B}\|_F \leq \sqrt{2m_C}n^{\frac1p+\frac12}$, we see that $\|\frac{1}{\sqrt n}\mathbf{B}\|_{\mathcal{S}_p} \leq \sqrt{2m_C}n^{\frac{1}{p}}$, where the constant factor can be made arbitrarily small by choosing $C$ large enough; that is, truncating $\mathbf{A}\sim \mathcal{D}_1$ incurs only a constant factor loss (where the constant can be made arbitrarily small) in $\|\mathbf{A}\|_{\mathcal{S}_p}^p$ with probability $\geq 0.999$.

Next, suppose that $\mathbf{A}'\sim \mathcal{D}_2$ and we write the truncation as $\tilde \mathbf{A}' = \mathbf{A}' + \mathbf{B}'$. It is a classical result~\cite{borel} that
\begin{equation}\label{eqn:orthogonal_matrix_entry}
\lim_{n\to\infty} \Pr\{\sqrt{n}\mathbf{O}_{ij} \leq t\} = \Pr_{g\sim\mathcal{N}(0,1)}\{g \leq t\}.
\end{equation}
Observe that $\mathbf{A}'_{ij} \stackrel{\text{dist}}{=} \mathbf{O}_{ij} + \frac{\eta}{\sqrt n}g'$ and $\mathbf{A}_{ij} \stackrel{\text{dist}}{=} \frac{1}{\sqrt{n}}g + \frac{\eta}{\sqrt n} g'$ with the same additive `noise' $\frac{\eta}{\sqrt n}g'$, where $g,g'\sim N(0,1)$ are independent, it follows that $\Pr\{\sqrt n\mathbf{A}'_{ij} \leq t\} \to \Pr\{\sqrt{n}\mathbf{A}_{ij} \leq t\}$ for any (fixed) $t$ as $n\to\infty$ (note that $\sqrt{n}\mathbf{A}_{ij} \stackrel{\text{dist}}{=} (1+\eta)g$ and does not depend on $n$). Hence each entry of $\mathbf{B}_{ij}'$ is stochastically dominated by $\frac{1}{\sqrt n}\tilde\mathcal{N}_{C/2}(0,1)$. Similarly to before, $\bbE\|\mathbf{B}'\|_{\mathcal{S}_p} \leq n^{\frac1p-\frac12}\bbE\|\mathbf{B}'\|_F \leq \sqrt{m_{C/2}}n^{\frac1p}$, and thus by Markov's inequality, with probability $\geq 0.999$ it holds that $\|\mathbf{B}'\|_{\mathcal{S}_p} \leq 1000\sqrt{m_{C/2}}n^{\frac1p}$; that is, truncating $\mathbf{A}'\sim \mathcal{D}_2$ incurs only a constant factor loss (where the constant can be made arbitrarily small) in $\|\mathbf{A}'\|_{\mathcal{S}_p}^p$ with probability $\geq 0.999$.


Now, the matrices from $\frac{\sqrt n}{C}\widetilde{\mathcal{D}_1}$ and $\frac{\sqrt n}{C}\widetilde{\mathcal{D}_2}$ have entries bounded by $1$, and with high probability, $\|\mathbf{A}\|_{\mathcal{S}_p}\leq c_1 n^{\frac{1}{2}+\frac{1}{p}}$ when $\mathbf{A}\sim \frac{\sqrt n}{C}\widetilde{\mathcal{D}_1}$ and
$\|\mathbf{A}\|_{\mathcal{S}_p}\geq c_2 n^{\frac{1}{2}+\frac{1}{p}}$ when $\mathbf{A}\sim \frac{\sqrt n}{C}\widetilde{\mathcal{D}_2}$, for constants $c_1 < c_2$ (depending on $\eta$ and $C$). Our result of the theorem would follow immediately from Theorem~\ref{thm:schatten_p_lb} once we establish that with high probability, a random matrix from $\frac{\sqrt n}{C}\widetilde{\mathcal{D}_1}$ is $\epsilon$-far from having Schatten $p$-norm at least $c_2 n^{\frac{1}{2}+\frac{1}{p}}$. Indeed, let $\mathbf{E}$ denote the pertubation to $\mathbf{A}$ such that $\|\mathbf{E}\|_0\leq \epsilon n^2$ and $\|\mathbf{A}+\mathbf{E}\|_\infty\leq 1$. Since $\|\mathbf{A}\|_\infty\leq 1$, it must hold that $\|\mathbf{E}\|_\infty\leq 2$. Thus $\|\mathbf{E}\|_{\mathcal{S}_p} \leq n^{\frac1p-\frac12}\|\mathbf{E}\|_F \leq 2 \sqrt{\epsilon}  n^{\frac1p+\frac12}$. When $\epsilon$ is sufficiently small, it is easy to see via triangle inequality that there remains a constant-factor gap between $\|\mathbf{A}+\mathbf{E}\|_{\mathcal{S}_p}$ and $c_2 n^{\frac12+\frac1p}$.
\end{proof}







\section{Non-adaptive Testing of Matrix Entropy}
\label{section: Entropy}

Recall that we defined in Eq.~\eqref{eqn:entropy_defn} the entropy of a matrix $\mathbf{A}\in \mathbb{R}^{n\times n}$ as
\[
H(\mathbf{A}) = \frac{-\sum_i \frac{\sigma_i^2(\mathbf{A})}{n^2}\log\frac{\sigma_i^2(\mathbf{A})}{n^2}}{\sum_i \frac{\sigma_i^2(\mathbf{A})}{n^2}},
\]
with the convention that $0\cdot\infty = 0$. For matrices $\mathbf{A}$ satisfying $\|\mathbf{A}\|_\infty\leq 1$, it holds that $\sigma_i(\mathbf{A})\leq n$ for all $i$ and the entropy above coincides with the usual Shannon entropy. Note that scaling only changes the entropy additively; that is, $H(\beta\mathbf{A}) = H(\mathbf{A}) - \log\beta^2$.

Our goal in this section is to show that the following testing problem on matrix entropy has a lower bound of $\Omega(n)$ queries. 

\begin{problem}[Entropy Testing in the Bounded Entry Model]
Let $\mathbf{A}\in\mathbb{R}^{n\times n}$ be a matrix with bounded absolute values of entries by $1$. For some absolute constant $c$, $\mathbf{A}$ has one of promised properties:
\begin{itemize}
\item[$\mathsf{H0.}$]
$H(\mathbf{A})\leq \log n + \log \log \log n - c$;
\item[$\mathsf{H1.}$]
$\mathbf{A}$ is $\frac{\epsilon}{\log n \log\log n}$-far from having entropy at most $\log n + \log\log \log n - c$, meaning that $\mathbf{A}$ requires changing at least an $\frac{\epsilon}{\log n\log\log n}$-fraction of its entries so that $H(\mathbf{A})\leq \log n + \log \log \log n - c$.
\end{itemize}
The problem is to design a non-adaptive property testing algorithm that outputs $\mathsf{H0}$ with probability at least $0.9$ if $\mathbf{A}\in \mathsf{H0}$, and output $\mathsf{H1}$ with probability at least $0.9$ if $\mathbf{A}\in\mathsf{H1}$, with the least number of queried entries.
\end{problem}

\begin{theorem}
\label{thm:entropy_lb}
There exist absolute constants $c > 0$ and $\epsilon_0 > 0$ such that for any $\epsilon \leq \epsilon_0$ and $\mathbf{A}\in\mathbb{R}^{n\times n}$, any non-adaptive algorithm that correctly tests $\mathsf{H0}$ against $\mathsf{H1}$ with probability at least $0.99$ must make $\Omega(n)$ queries (i.e., the sketch size is $\Omega(n)$). 
\end{theorem}
\begin{proof}
Consider the hard instances $\widetilde{\mathcal{D}}_1$ of truncated Gaussian random matrices and $\widetilde{\mathcal{D}}_2$ of truncated random orthogonal matrices in the proof of Theorem~\ref{thm:schatten_p_lb}. We first claim that with high probability, their entropies are different by an additive constant.

Suppose that $\mathbf{G}\sim\mathcal{G}(n,n)$ and $\mathbf{O}$ is a uniformly random orthogonal matrix. It is clear that $H(\sqrt n\mathbf{O}) = \log n$. Let $\mathbf{G}' = \frac{1}{\sqrt n}\mathbf{G}$, we have that
\[
H(\mathbf{G}) = H(\sqrt n \mathbf{G}') = -\frac{\sum_i \frac{\sigma_i^2(\mathbf{G}')}{n}\log\frac{\sigma_i^2(\mathbf{G}')}{n}}{\sum_i \frac{\sigma_i^2(\mathbf{G}')}{n}} = -\frac{\sum_i \sigma_i^2(\mathbf{G}')\log \sigma_i^2(\mathbf{G}')}{\sum_i \sigma_i^2(\mathbf{G}')} + \log n.
\]
It follows from the Marchenko-Pastur law that, even with truncation of entries (this fact is actually used in the proof of the Marchenko-Pastur law, see, e.g.,~\cite[Section 3.1.3]{BS10}), the denominator and the numerator both converge to its expected value almost surely, with a rate of convergence of $\mathcal{O}(1/\sqrt{n})$. Let
\[
p(x) = \frac{\sqrt{x(4-x)}}{2\pi x},\quad x\in[0,4]
\]
be the density function of the Marchenko-Pastur law, then the first term is concentrated around
\[
-\frac{\int_0^4 (x \log x)p(x) \,dx}{\int_0^4  x p(x)\, dx} = -\frac{1}{2}.
\]
This shows an additive constant difference between the entropy of truncated Gaussian random matrices and scaled random orthogonal matrices. Specifically, $H(\frac{1}{C}\mathbf{G}) \leq \log n + 2\log C - c$ with high probability for some absolute constant $c$ close to $1/2$, and $H(\frac{\sqrt n}{C}\mathbf{O}) = \log n + 2\log C$.

Next we shall show that the perturbation $\frac{\eta}{\sqrt{n}}\mathbf{G}$, truncation and the change of at most $\epsilon n^2/(\log n\log\log n)$ entries altogether will affect the entropy of $\frac{\sqrt n}{C}\mathbf{O}$ by at most an additive constant that can be made arbitrarily small (depending on $\eta$, the truncation threshold $C$ and $\epsilon$). Viewing all changes as a perturbation matrix $\mathbf{E}$, we have with probability $\geq 0.99$ that $\|\mathbf{E}\|_F^2\leq 3(\frac{2\eta}{n} + 100m_{C/2}+\frac{\epsilon}{\log n \log\log n})n^2$, where $\frac{2\eta}{n}n^2$ comes from $\frac{\eta}{\sqrt{n}}\mathbf{G}$, $100m_{C/2} n^2$ from the truncation of entries (recall the fact that an individual entry of $\mathbf{O}$ can be approximated by $\mathcal{N}(0,1/n)$; see the proof of Theorem~\ref{thm:schatten_p_lb}) and $\frac{\epsilon}{\log n \log \log n}n^2$ from the change of the entries. Setting $C = C_1\sqrt{\log\log n}$ for some large absolute value $C_1$, we have that
\[
\|\mathbf{E}\|_F^2 \leq 3\left(\frac{2\eta}{n} + \frac{1}{\operatorname{poly}(\log n)} + \frac{\epsilon_0}{\log n\log\log n}\right)n^2 \leq \frac{4\epsilon_0}{\log n \log\log n} n^2.
\]

For notational simplicity, let $\epsilon' = 4\epsilon_0$, $s_i = \sigma_i(\mathbf{O}+\frac{C}{\sqrt n}\mathbf{E})$ and $\delta_i = s_i - 1$. Since
\[
H\left(\frac{\sqrt{n}\mathbf{O}+\mathbf{E}}{C}\right) = H\left(\mathbf{O} + \frac{C}{\sqrt n}\mathbf{E}\right) - \log n + \log C^2 = - \frac{\sum_i s_i^2\log s_i^2}{\sum_i s_i^2} + \log n + \log C^2,
\]
we wish to show that the first term on the right-hand side is at most a constant. By the Hoffman-Wielandt inequality, we have that
\begin{equation}\label{eqn:constraint}
\sum_i \delta_i^2 \leq \left\|\frac{C}{\sqrt n}\mathbf{E}\right\|_{F}^2 \leq \frac{C_1^2\epsilon' n}{\log n}
\end{equation}
Consider the problem of minimizing
\[
f(\delta_1,\dots,\delta_n) = - \frac{\sum_i (1+\delta_i)^2\log (1+\delta_i)^2}{\sum_i (1+\delta_i)^2}
\]
subject to the constraint \eqref{eqn:constraint}. In the interior of the region, one can verify using calculus that the extremal value is attained when $\delta_i$'s are all equal for those $\delta_i\neq -1$. One can further verify that the extremal value in the interior of the region is the maximal value. On the boundary of the region, one can use Lagrange multipliers to obtain that the extremal value is attained when nonzero $\delta_i$'s are all equal. It then follows that the function attains the minimum value when $\delta_1 =  C_1\sqrt{\epsilon' n/\log n}$ and $\delta_2 = \cdots = \delta_n = 0$, in which case one can calculate
\[
f(\delta_1,\dots,\delta_n) = -C_1^2\epsilon' + o(1).
\]

We can take $\epsilon_0$ to be sufficiently small such that $C_1^2\epsilon'$ is smaller than the additive gap between $H(\frac{1}{C}\mathbf{G})$ and $H(\frac{\sqrt{n}}{C}\mathbf{O})$. This shows that there would still be an additive constant gap between $\widetilde{D}_1$ and $\widetilde{D}_2$ after changing $\epsilon n^2/(\log n \log\log n)$ entries to a matrix drawn from $\widetilde{D}_2$. The lower bound follows from Theorem~\ref{lem:schatten_p_lb_hard_instance}, where we can ignore the additive Gaussian term in the two hard instances there by letting $\eta$ be arbitrarily small.
\end{proof}






\paragraph{Acknowledgements} 
Part of this work was done while D.\@ W.\@ and H.\@ Z.\@ were visiting the Simons Institute for the Theory of Computing. We thank Sepehr Assadi, Yury Polyanskiy, Ran Raz, Avishay Tal, Zhengyu Wang, and Yihong Wu for useful discussions. This work was supported in part by grants NSF CCF-1422910, NSF CCF-1535967,  NSF IIS-1618714, Office of Naval Research (ONR) grant N00014-18-1-2562, and a Microsoft Research Fellowship.





\bibliographystyle{plain}
