High-Dimensional Matched Subspace Detection When Data are Missing

I Introduction

This paper considers a variation on this classical problem, motivated by high-dimensional applications where it is prohibitive or impossible to measure $v$ completely. We assume that only a small subset $\Omega\subset\{1,\dots,n\}$ of the elements of $v$ are observed (with or without noise), and based on these observations we want to test whether $v\in S$. For example, consider monitoring a large networked system such as a portion of the Internet. Measurement nodes in the network may have software that collects measurements such as upload and download rate, number of packets, or type of traffic given by the packet headers. In order to monitor the network these measurements will be collected in a central place for compilation, modeling and analysis. The effective dimension of the state of such systems is often much lower than the extrinsic dimension of the network itself. Subspace detection, therefore, can be a useful tool for detecting changes or anomalies. The challenge is that it may be impossible to obtain every measurement from every point in the network due to resource constraints, node outages, etc.

The main result of this paper answers the following question. Given a subspace $S$ of dimension $r\ll n$, how many elements of $v$ must be observed so that we can reliably decide if it belongs to $S$? The answer is that, under some mild incoherence conditions, the number is $O(r\log r)$. This means that reliable matched subspace detectors can be constructed from very few measurements, making them scalable and applicable to large-scale testing problems.

The main focus of this paper is an estimator of the energy of $v$ in $S$ based on only observing the elements $\{v_{i}\}_{i\in\Omega}$. Section II proposes the estimator. Section III presents a theorem giving quantitative bounds on the estimator’s performance and the proof using three lemmas that are proved in the Appendix. Section IV presents numerical experiments. Section V applies the main result to the subspace detection problem, both with and without noise.

II Energy Estimation from Incomplete Data

Let $v_{\Omega}$ be the vector of dimension $|\Omega|\times 1$ comprised of the elements $v_{i}$, $i\in\Omega$, ordered lexigraphically; here $|\Omega|$ denotes the cardinality of $\Omega$. The energy of $v$ in the subspace $S$ is $\|P_{S}v||_{2}^{2}$, where $P_{S}$ denotes the projection operator onto $S$. There are two natural estimators of $\|P_{S}v||_{2}^{2}$ based on $v_{\Omega}$. The first is simply to form the $n\times 1$ vector $\widetilde{v}$ with elements $v_{i}$ if $i\in\Omega$ and zero if $i\not\in\Omega$, for $i=1,\dots,n$. This ‘zero-filled’ vector yields the simple estimator $\|P_{S}\widetilde{v}\|_{2}^{2}$. Filling missing elements with zero is a fairly common, albeit naïve, approach to dealing with missing data. Unfortunately, the estimator $\|P_{s}\widetilde{v}\|_{2}^{2}$ is fundamentally flawed. Even if $v\in S$, the zero-filled vector $\widetilde{v}$ does not necessarily lie in $S$.

A better estimator can be constructed as follows. Let $U$ be an $n\times r$ matrix whose columns span the $r$-dimensional subspace $S$. Note that for any such $U$, $P_{S}=U(U^{T}U)^{-1}U^{T}$. With this representation in mind, let $U_{\Omega}$ denote the $|\Omega|\times r$ matrix, whose rows are the $|\Omega|$ rows of $U$ indexed by the set $\Omega$, arranged in lexigraphic order. Since we only observe $v$ on the set $\Omega$, another approach to estimating its energy in $S$ is to assess how well $v_{\Omega}$ can be represented in terms of the rows of $U_{\Omega}$. Define the projection operator $P_{S_{\Omega}}:=U_{\Omega}(U^{T}_{\Omega}U_{\Omega})^{\dagger}U_{\Omega}^{T}$, where † denotes the pseudoinverse. It follows immediately that if $v\in S$, then $\|v-P_{S}v||_{2}^{2}=0$ and $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}^{2}=0$, whereas $\|\widetilde{v}-P_{S}\widetilde{v}\|_{2}^{2}$ can be significantly greater than zero. This property makes $\|P_{S_{\Omega}}v_{\Omega}\|_{2}^{2}$ a much better candidate estimator than $\|P_{S}\widetilde{v}\|_{2}^{2}$. However, if $|\Omega|\leq r$, then it it is possible that $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}^{2}=0$, even if $\|v-P_{S}v||_{2}^{2}>0$. Our main result shows that if $|\Omega|$ is just slightly greater than $r$, then with high probability $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}^{2}$ is very close to $\frac{|\Omega|}{n}\|v-P_{S}v||_{2}^{2}$.

III Main Theorem

Let us now focus on our main goal of detecting from a very small number of samples whether there is energy in a vector $v$ outside the $r$-dimensional subspace $S$. In order to do so, we must first quantify how much information we can expect each sample to provide. The authors in defined the coherence of a subspace $S$ to be the quantity

That is, $\mu(S)$ measures the maximum magnitude attainable by projecting a standard basis element onto $S$. Note that $1\leq\mu(S)\leq\tfrac{n}{r}$. The minimum $\mu(S)=1$ can be attained by looking at the span of any $r$ columns of the discrete Fourier transform. Any subspace that contains a standard basis element will maximize $\mu(S)$. For a vector $z$, we let $\mu(z)$ denote the coherence of the subspace spanned by $z$. By plugging in the definition, we have

To state our main theorem, write $v=x+y$ where $x\in S$ and $y\in S^{\perp}$. Let the entries of $v$ be sampled uniformly with replacement. Again let $\Omega$ refer to the set of indices for observations of entries in $v$, and denote $|\Omega|=m$. Given these conventions, we have the following.

Let $\delta>0$ and $m\geq\frac{8}{3}r\mu(S)\log\left(\frac{2r}{\delta}\right)$. Then with probability at least $1-4\delta$,

where $\alpha=\sqrt{\frac{2\mu(y)^{2}}{m}\log\left(\frac{1}{\delta}\right)}$, $\beta=\sqrt{2\mu(y)\log\left(\frac{1}{\delta}\right)}$, and $\gamma=\sqrt{\frac{8r\mu(S)}{3m}\log\left(\frac{2r}{\delta}\right)}$.

In order to prove the theorem, we split the quantity of interest into three terms and bound each with high probability. Consider $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}^{2}=\|y_{\Omega}-P_{S_{\Omega}}y_{\Omega}\|_{2}^{2}$. Let the $r$ columns of $U$ be an orthonormal basis for the subspace $S$. We want to show that

is near $\frac{m}{n}\|y\|_{2}^{2}$ with high probability. To proceed, we need the following three Lemmas whose proofs can be found in the Appendix.

with probability at least $1-\delta$, provided that $\gamma<1$.

To apply these three Lemmas, write the second term of Equation (1) as

where $W_{\Omega}^{T}W_{\Omega}=\left(U_{\Omega}^{T}U_{\Omega}\right)^{-1}$. By Lemma 3, $U_{\Omega}^{T}U_{\Omega}$ is invertible under the assumptions of our theorem, and hence $W_{\Omega}$ is well-defined and has spectral norm bounded by the square root of the inverse of the smallest eigenvalue of $U_{\Omega}^{T}U_{\Omega}$. That is, we have

$\|\left(U_{\Omega}^{T}U_{\Omega}\right)^{-1}\|_{2}$ is bounded by Lemma 3 and $\|U_{\Omega}^{T}y_{\Omega}\|_{2}$ is bounded by Lemma 2. Putting these two bounds together with the bounds in Lemma 1 and using the union bound, we have that with probability at least $1-4\delta$

IV Discussion and Numerical Experiments

In this section we wish to give some intuition for the lower bound in Theorem 1 and show simulations of the estimate $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}$. If the parameters $\alpha,\beta,\gamma$ are very near $0$, our lower bound is approximately equal to

For an incoherent subspace, the parameter $\mu(S)=1$. In this case, for $m\leq r$ the bound is $\leq 0$, which is consistent with the fact that $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}=0$ always for $m\leq r$. Once $m\geq r+1$, linear algebraic reasoning tells us that $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}$ will be strictly positive with positive probability; Theorem 1 goes further to say the norm is strictly positive with high probability once $m\sim O(rlogr)$.

The parameters $\alpha,\beta,\gamma$ all depend on $\sqrt{\log\left(\frac{1}{\delta}\right)}$; these parameters grow as $\delta$ gets very small. Increasing the number of observations $m$ will counteract this behavior for $\alpha$ and $\gamma$, but this does not hold for $\beta$. In fact, even if the vector $y$ is incoherent and $\mu(y)=1$, its minimum value, then $\beta=2$ for $\delta\approx.135$. To get $\beta$ very near zero, $\delta$ must be very near one, but this is not a useful regime.

We can see, however, that in simulations these large constants are somewhat irrelevant; The large deviations analysis needed for the proof is overly conservative in most cases.

This plays out in the simulations shown in Figure 1, where we see that for very incoherent subspaces, $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}$ is always positive for $m>r\mu(S)\log r$. The plots show the minimum, maximum and mean value of $\|v_{\Omega}-P_{S_{\Omega}}v_{\Omega}\|_{2}$ over 100 simulations, for fixed $S$ and fixed $v$ such that $\|v\|_{2}^{2}=1$ and $v\in S^{\perp}$. For each value of the sample size $m$, we sampled 100 different instances of $\Omega$without replacement, giving us a realistic idea of how much energy of $v$ is captured by $m$ samples. Our simulations for the Fourier basis and a basis made of orthogonalized Gaussian random vectors always showed the estimate to be positive for $m>r\mu(S)\log r$, even for the worst-case simulation run. For more coherent subspaces, we often (but not always) see that the norm is positive as long as $m>r\mu(S)\log r$.

V Matched Subspace Detection

We have the following detection set up. Our hypotheses are $\mathcal{H}_{0}:v\in S$ and $\mathcal{H}_{1}:v\notin S$ and the test statistic we will use is

When we introduce noise we have the same hypotheses, but we compute the statistic on $\widetilde{v}_{\Omega}=v_{\Omega}+w$ where $w\sim\mathcal{N}(0,1)$ is Gaussian white noise:

We choose $\eta_{\lambda}$ to fix the probability of false alarm:

We now show why the heuristic approach of zero-filling the incomplete vector $v_{\Omega}$ does not work. As we described in Section II, the zero-filling approach is to fill the vector $v$ with zeros and then project onto the full subspace $S$. We denote the zero-filled vector as $v_{0}$ and then calculate the projection energy only on the observed entries:

Simple algebraic consideration reveals that $t_{0}(v_{\Omega})|\mathcal{H}_{0}$ is positive. In fact, even in the absence of noise, the probability of false alarm can be arbitrarily large as $\|v\|_{2}^{2}$ increases. The value of $t_{0}(v_{\Omega})|\mathcal{H}_{0}$, based on noiseless observations, is plotted as a function of the number of measurements in Figure 2.

We note that for unknown noise power or structured interference, these results can be extended using the GLRT .

VI Conclusion

We have shown that it is possible to detect whether a highly incomplete vector has energy outside a subspace. This is a fundamental result to add to a burgeoning collection of results for incomplete data analysis given a low-rank assumption. Missing data are the norm and not the exception in any massive data collection system, so this result has implications on many other areas of study.

One of our reviewers shared an insight that the process by which we observe some components and observe erasures in other components can be expressed as a projection operator. It may be possible to extend the results of Theorem 1 to a wide class of models of random projection operators beyond the class of deletion operators studied here.

Acknowledgments

The authors would like to thank the reviewers for their thoughtful comments. This work was supported in part by AFOSR grant FA9550-09-1-0140.

Appendix A Useful Inequalities

We will need the following two large deviation bounds in the proofs of our Lemmas below.

Let $X_{1},\dots,X_{n}$ be independent random variables, and assume $f$ is a function for which there exist $t_{i}$, $i=1,\dots,n$ satisfying

where $\hat{x_{i}}$ indicates replacing the sample value $x_{i}$ with any other of its possible values. Call $f(X_{1},\dots,X_{n}):=Y$. Then for any $\epsilon>0$,

Appendix B Supporting Lemmas and Proofs

We now proceed with the proof of our three central Lemmas.

To prove this we use McDiarmid’s inequality from Theorem 2 for the function $f(X_{1},\dots,X_{m})=\sum_{i=1}^{m}X_{i}$. The resulting inequality is more commonly referred to as Hoeffding’s inequality.

We begin with the first inequality. Set $X_{i}=y_{\Omega(i)}^{2}$. We seek a good value for $t_{i}$. Since $y_{\Omega(i)}^{2}\leq\|y\|_{\infty}^{2}$ for all $i$, we have

Plugging into Equation (3), the left hand side is

and letting $\epsilon=\alpha\frac{m}{n}\|y\|_{2}^{2}$, we then have that this probability is bounded by

Substituting our definitions of $\mu(y)$ and $\alpha$ shows that the lower bound holds with probability at least $1-\delta$. The argument for the upper bound is identical after replacing Equation (2) instead of (3). The Lemma now follows by applying the union bound. ∎

We use McDiarmid’s inequality in a very similar fashion to the proof of Lemma 1. Let $X_{i}=y_{\Omega(i)}U_{\Omega(i)}$, where $\Omega(i)$ refers to the $i^{th}$ sample index. Thus $y_{\Omega(i)}$ is a scalar, and the notation $U_{\Omega(i)}$ refers to an $r\times 1$ vector representing the transpose of the $\Omega(i)^{th}$ row of $U$.

Let our function $f(X_{1},\dots,X_{m})=\|\sum_{i=1}^{m}X_{i}\|_{2}=\|U_{\Omega}^{T}y_{\Omega}\|_{2}$. To find the $t_{i}$ of the theorem we first need to bound $\|X_{i}\|$ for all $i$. Observe that $\|U_{\Omega(i)}\|_{2}=\|U^{T}e_{i}\|_{2}=\|P_{S}e_{i}\|_{2}\leq\sqrt{r\mu(S)/n}$ by assumption. Thus,

Then observe $\left|f(X_{1},\dots,X_{m})-f(X_{1},\dots,\hat{X_{k}},\dots,X_{m})\right|$ is

The step (5) follows because the cross terms cancel by orthogonality. The step (6) is because of our assumption that sampling is uniform with replacement.

Substituting our definitions of $\mu(y)$ and $\beta$ shows that the lower bound holds with probability at least $1-\delta$, completing the proof.∎

We use the Noncommutative Bernstein Inequality as follows. Let $X_{k}=U_{\Omega(k)}U_{\Omega(k)}^{T}-\frac{1}{n}I_{r}$, where the notation $U_{\Omega(k)}$ is as before, i.e. is the transpose of the $\Omega(k)^{th}$ row of $U$, and $I_{r}$ is the $r\times r$ identity matrix. Note that this random variable is zero mean.

We must compute $\rho_{k}^{2}$ and $M$. Since $\Omega(k)$ is chosen uniformly with replacement, the $X_{k}$ are identically distributed, and $\rho$ does not depend on $k$. For ease of notation we will denote $U_{\Omega(k)}$ as $U_{k}$.

Using the fact that for positive semi-definite matrices, ${\|A-B\|_{2}\leq\max\{\|A\|_{2},\|B\|_{2}\}}$, and recalling again that $\|U_{k}\|^{2}_{2}=\|U^{T}e_{k}\|^{2}_{2}=\|P_{S}e_{k}\|^{2}_{2}\leq r\mu(S)/n$, we have

Now we can apply the Noncommutative Bernstein Inequality, Theorem 3. First we restrict $\tau$ to be such that $M\tau\leq m\rho^{2}$ to simplify the denominator of the exponent. Then we get that

Now take $\tau=\gamma m/n$ with $\gamma$ defined in the statement of Theorem 1. Since $\gamma<1$ by assumption, $M\tau\leq m\rho^{2}$ holds and we have

We note that $\left\|\sum_{k\in\Omega}U_{k}U_{k}^{T}-\frac{m}{n}I_{r}\right\|_{2}\leq\frac{m}{n}\gamma$ implies that the minimum singular value of $\sum_{k\in\Omega}U_{k}U_{k}^{T}$ is at least $(1-\gamma)\frac{m}{n}$. This in turn implies that

References