Decremental $(1+ϵ)$-Approximate Maximum Eigenvector: Dynamic Power Method

We give an algorithm for the Decremental Approximate Maximum Eigenvalue and Eigenvector Problem that has an amortized update time of $\approx \tilde{O}(nnz({𝒗}_t))\le \tilde{O}(n)$¹¹1$\tilde{O}$ hides polynomials in $\log n$.. In other words, the total time required by our algorithm over $T$ updates is at most $\tilde{O}(nnz({𝑨}_0)+{\sum }_{i=1}^{T}nnz({𝒗}_i))$. Observe that our algorithm only requires time that is $\tilde{O}(1)\times$ (time required to read the input) and can handle any number of decremental updates. Our algorithm works against an oblivious adversary, i.e., the update sequence is fixed from the beginning. This is the first algorithm that can handle a sequence of updates while providing a multiplicative approximation to the eigenvalues and eigenvectors in a total runtime of $\le \tilde{O}(n^2+n\cdot T)$ and an amortized update time faster than previous algorithms by a factor of $n^{\mathrm{\Omega }(1)}$. Formally, we prove the following:

Our algorithm is a novel adaptation of the classical power method (see, e.g., [29]) to the dynamic setting, along with a new analysis that may be of independent interest.

Our work can also be viewed as the first step towards generalizing the dynamic algorithms for solving positive linear programs of [11] to solving dynamic positive semi-definite programs. We discuss this connection in detail in Appendix A.

We also explore the possibility of removing the assumption of an oblivious adversary and working against adaptive adversaries. Recall that update sequences are given by adaptive adversaries when the update sequence can depend on the solution of the algorithm.

We show that if there is an algorithm for Problem 1 with a total running time of at most $\tilde{O}(n^2)$ such that the output ${𝒘}_t$’s satisfy an additional natural property (which is satisfied by the output of the power method, but not by our algorithm), then it contradicts the hardness of a well-known barrier in numerical linear algebra, therefore ruling out such algorithms.

We first state the barrier formally, and then state our result for adaptive adversaries. Recall that, given a matrix $𝑨$, the condition number of $𝑨$ is $\frac{{\max }_{x:\text{unit}}\Vert \mathrm{𝑨𝒙}\Vert }{{\min }_{x:\text{unit}}\Vert \mathrm{𝑨𝒙}\Vert }$.

Recall that $A$ is a psd matrix iff there exists $𝑿$ such that $𝑨={\mathrm{𝑿𝑿}}^{\top }$. The matrix of $𝑿$ is called a vector realization of $𝑨$, and note that $𝑿$ is not unique. The problem above asks to compute a (highly accurate) vector realization of $𝑨$. Both eigendecomposition and Cholesky decomposition of $𝑨$ give a solution for Problem 3.²²2Given an eigendecomposition $𝑨=𝑸\mathrm{\Lambda }{𝑸}^{\top }$ where $\mathrm{\Lambda }$ is a non-negative diagonal matrix and $𝑸$ is an orthogonal matrix, we set $𝑿=𝑸{\mathrm{\Lambda }}^{1/2}$. Given a Cholesky decomposition $𝑨={\mathrm{𝑳𝑳}}^{\top }$ where $𝑳$ is a lower triangular matrix, we set $𝑿=𝑳$. Banks et al [7] showed how to compute with high accuracy an eigendecomposition of a psd matrix in $O(n^{\omega +\eta })$ time for any constant $\eta >0$, where $\omega >2.37$ is the matrix multiplication exponent. Hence, a vector realization of $𝑨$ can be found in the same time. Observe that, when , Problem 3 is at least as hard as certifying that a given matrix $𝐀$ is a psd matrix. It is a notorious open problem whether certifying the psd-ness of a matrix can be done faster than $o(n^{\omega })$ even when the condition number is polynomial in $n$. Therefore, we view Problem 3 as a significant barrier and formalize it as follows.

Our negative result states that, assuming Hypothesis 4, there is no algorithm for Problem 1 against adaptive adversaries with sub-polynomial update time that maintains ${𝒘}_t$ satisfying an additional property stated below.

Let us motivate Property 5 from several aspects below. First, in the static setting, this property can be easily satisfied since the static power method strongly satisfies it (see Lemma 14). Second, the statement of the property itself is a natural property that we might expect from an algorithm. Consider a “bad” eigenvector ${𝒖}_i$ whose corresponding eigenvalue is very small, i.e., less than half of the maximum one. It states that the projection of the output ${𝒘}_t$ along ${𝒖}_i$ should be very small, i.e., a polynomial factor smaller than the projection along the maximum eigenvector. This is intuitively useful because we do not want the output ${𝒘}_t$ to direct to the “bad” direction. It should mainly direct along the approximately maximum eigenvector. Third, we formalize this intuition and crucially exploit Property 5 to prove a reduction in Theorem 6. Specifically, Property 5 allows us to decrease eigenvalues of a psd matrix while maintaining the psd-ness, which is crucial for us. See Section 4 for more details. Lastly, our current algorithm from Theorem 2, a dynamic version of the power method, actually maintains ${𝒘}_t$’s that satisfy this property for certain snapshots, but not at every step. Unfortunately, we do not see how to strengthen our algorithm to satisfy Property 5 nor how to remove it from the requirement of Theorem 6. We leave both possibilities as open problems.

Understanding the power and limitations of dynamic algorithms against an oblivious adversary vs. an adaptive adversary has become one of the main research programs in the area of dynamic algorithms. However, finding a natural dynamic problem that separates oblivious and adaptive adversaries is still a wide-open problem.³³3 Beimel et al. [9] gave the first separations for artificial problems assuming a strong cryptographic assumption. Bateni et al. [8] shows a separation between the adversaries for the $k$-center clustering problem, however, their results are based on the existence of a black box which the adaptive adversary can control. In this paper, we suggest the problem of maintaining approximate maximum eigenvectors as a natural candidate for the separation and give some preliminary evidence for this.

The overall proof of Theorem 2, including the proof of correctness and the runtime depends on the number of executions in Line 4 in Algorithm 3. If the number of executions of Line 4 is bounded by $\mathrm{poly}(\log n/ϵ)$, then the remaining analysis is straightforward. Therefore, the majority of our analysis is dedicated to proving this key lemma, i.e., $\mathrm{poly}(\log n/ϵ)$ bound on the number of calls to the power method:

Given the key lemma, the correctness and runtime analyses are quite straightforward. We now give an overview of the proof of Lemma 16.

Let us consider what happens between two consecutive calls to Line 4, say at $𝑨$ and $\stackrel{\mathbf{~}}{𝑨}=𝑨-{\sum }_{i=1}^k{𝒗}_i{𝒗}_i^{\top }$. We first define the following subspaces of $𝑨$ and $\stackrel{\mathbf{~}}{𝑨}$. Recall Definition 8, which we use to define the following subspaces.

Observe that $T={\sum }_{\nu =0}^{15\log \frac{n}{ϵ}-1}{T}_{\nu }$ and similarly $\tilde{T}={\sum }_{\nu =0}^{15\log \frac{n}{ϵ}-1}{\tilde{T}}_{\nu }$. We next define some indices/levels corresponding to large subspaces, which we call “important levels”.

The main technical lemma that implies Lemma 16 is the following:

We prove this lemma in the full version. Intuitively speaking, it means that, whenever Line 4 of Algorithm 3 is executed, there is some important level $\nu$ such that an $\mathrm{\Omega }(ϵ/\mathrm{poly}\log (n/ϵ))$-fraction of eigenvalues of $𝑨$ at level $\nu$ have decreased in value. This is the crucial place where we exploit an oblivious adversary.

Given Lemma 19, the remaining proof of Lemma 16 follows a potential function analysis which is presented in detail in the full version. We consider potentials ${\mathrm{\Phi }}_j={\sum }_{\nu =0}^j{d}_{\nu }$ for $j=0,\mathrm{\cdots },15\log \frac{n}{ϵ}-1$. The main observation is that ${\mathrm{\Phi }}_j$ is non-increasing over time for all $j$, and whenever there exists ${\nu }_0\in ℐ$ that satisfies the condition of Lemma 19, ${\mathrm{\Phi }}_{{\nu }_0}$ decreases by $\dim (T_{{\nu }_0}-\tilde{T})$. Since $\dim (T_{{\nu }_0}-\tilde{T})\ge \mathrm{\Omega }(ϵ/\mathrm{poly}\log (n/ϵ))d_{{\nu }_0}$ and ${\nu }_0\in ℐ$, i.e., , we can prove that ${\mathrm{\Phi }}_{{\nu }_0}$ decreases by a multiplicative factor of $\mathrm{\Omega }(1-{ϵ}^2/\mathrm{poly}\log (n/ϵ))$. As a result, every time our algorithm executes Line 4, ${\mathrm{\Phi }}_j$ decreases by a multiplicative factor for some $j$, and since we have at most $15\log \frac{n}{ϵ}$ values of $j$, we can only have $\mathrm{poly}(\log n/ϵ)$ executions of Line 4.

It remains to describe how we prove Lemma 19 at a high level. We can write ${𝒘}^{\top }\stackrel{\mathbf{~}}{𝑨}𝒘$ for any $𝒘\in 𝑾$ as

for $𝑽={\sum }_{i=1}^k{𝒗}_i{𝒗}_i^{\top }$. Our strategy is to show that:

Given (3.1) as formalized in the full version, we can conclude Lemma 19 because, from the definition of $𝑨$ and $\stackrel{\mathbf{~}}{𝑨}$, we have that for some $𝒘\in 𝑾$, ${𝒘}^{\top }\mathrm{𝑨𝒘}\ge 1-5ϵ$ by Corollary 15 and . As a result for this $𝒘$, ${𝒘}^{\top }\mathrm{𝑽𝒘}>35ϵ$. Now, by contra-position of (3.1), we have that $\dim (T_{\nu }-\tilde{T})$ is large for some $\nu \in ℐ$.

To prove (3.1), we further decompose ${𝒘}^{\top }\mathrm{𝑽𝒘}$ as

In the above equation, ${𝑽}_{\tilde{T}}={\mathrm{\Pi }}_{\tilde{T}}𝑽{\mathrm{\Pi }}_{\tilde{T}},{𝑽}_{T_{\nu }-\tilde{T}}={\mathrm{\Pi }}_{\nu }𝑽{\mathrm{\Pi }}_{\nu }$, and ${𝑽}_{\overline{T}}={\mathrm{\Pi }}_{\overline{T}}𝑽{\mathrm{\Pi }}_{\overline{T}}$ where ${\mathrm{\Pi }}_{\tilde{T}},{\mathrm{\Pi }}_{\nu },{\mathrm{\Pi }}_{\overline{T}}$ denote the projections matrices that project any vector onto the spaces $\tilde{T}$, $T_{\nu }-\tilde{T}$, and $\overline{T}$ respectively⁴⁴4Suppose a subspace $S$ is spanned by vectors ${𝒖}_1,\mathrm{\dots },{𝒖}_k$. Let $𝑼=[{𝒖}_1,\mathrm{\dots },{𝒖}_k]$. Recall that the projection matrix onto $S$ is $𝑼{({𝑼}^{\top }𝑼)}^{-1}{𝑼}^{\top }$.. Refer to the full version for proof of why such a split is possible. Our proof of (3.1) then bounds the terms on the right-hand side. Let us consider each term separately.

1. 1.

   ${𝒘}^{\top }{𝑽}_{\tilde{T}}𝒘$: We prove that this is always at most $10ϵ(1+ϵ)$. From the definition of $𝑽,$

   $${𝒘}^{\top }{𝑽}_{\tilde{T}}𝒘={𝒘}^{\top }{\mathrm{\Pi }}_{\tilde{T}}𝑨{\mathrm{\Pi }}_{\tilde{T}}𝒘-{𝒘}^{\top }{\mathrm{\Pi }}_{\tilde{T}}\stackrel{\mathbf{~}}{𝑨}{\mathrm{\Pi }}_{\tilde{T}}𝒘.$$

   Since ${\mathrm{\Pi }}_{\tilde{T}}𝒘$ is the projection of $𝒘$ along the large eigenspace of $\stackrel{\mathbf{~}}{𝑨}$, the second term on the right-hand side above is large, i.e. $\ge (1-10ϵ){\lambda }_0{\Vert {\mathrm{\Pi }}_{\tilde{T}}𝒘\Vert }^2$. The first term on the right-hand side can be bounded as, ${𝒘}^{\top }{\mathrm{\Pi }}_{\tilde{T}}𝑨{\mathrm{\Pi }}_{\tilde{T}}𝒘\le \Vert 𝑨\Vert {\Vert {\mathrm{\Pi }}_{\tilde{T}}𝒘\Vert }^2\le {\lambda }_0{\Vert {\mathrm{\Pi }}_{\tilde{T}}𝒘\Vert }^2$. Therefore the difference on the right-hand side is at most $10ϵ{\lambda }_0{\Vert {\mathrm{\Pi }}_{\tilde{T}}𝒘\Vert }^2\le 10ϵ{\lambda }_0{\Vert 𝒘\Vert }^2=10ϵ{\lambda }_0\le 10ϵ(1+ϵ)$.

2. 2.

   ${𝒘}^{\top }{𝑽}_{\overline{T}}𝒘$: Observe that this term corresponds to the projection of $𝒘$ along the space spanned by the eigenvalues of $𝑨$ of size at most $1-3ϵ$. Let ${𝒖}_i$ and ${\lambda }_i$ denote an eigenvector and eigenvalue pair with . Since the power method can guarantee that ${𝒘}^{\top }{𝒖}_i\approx {\lambda }_i^{2K}$, we have ${\lambda }_i^{2K}\le {(1-3ϵ)}^{2K}\le \mathrm{poly}(\frac{ϵ}{n})$ is tiny. So we have that ${𝒘}^{\top }{𝑽}_{\overline{T}}𝒘\le ϵ$.

   
   
   

   Before we look at the final case, we define a basis for the space $T_{\nu }$.

   Definition 20 (Basis for $T_{\nu }$).

   Let $T_{\nu }$ be as defined in Definition 17. Define indices $a_{\nu }$ and $b_{\nu }$ with $b_{\nu }-a_{\nu }+1=d_{\nu }$ such that the basis of $T_{\nu }$ is given by ${𝐮}_{a_{\nu }},\mathrm{\cdots },{𝐮}_{b_{\nu }}$, where ${𝐮}_1,{𝐮}_2,\mathrm{\cdots },{𝐮}_n$ are the eigenvectors of $𝐀$ in decreasing order of eigenvalues.

3. 3.

   ${𝒘}^{\top }{𝑽}_{T_{\nu }-\tilde{T}}𝒘$: For this discussion, we will ignore the constant factors and assume that the high probability events hold. Let ${\mathrm{\Pi }}_{\nu }$ denote the projection matrix for the space $T_{\nu }-\tilde{T}$. Observe that ${𝒘}^{\top }{𝑽}_{T_{\nu }-\tilde{T}}𝒘={𝒘}^{\top }{\mathrm{\Pi }}_{\nu }𝑽{\mathrm{\Pi }}_{\nu }𝒘\le \Vert 𝑽\Vert {\Vert {\mathrm{\Pi }}_{\nu }𝒘\Vert }^2\le (1+ϵ){\Vert {\mathrm{\Pi }}_{\nu }𝒘\Vert }^2$, where the last inequality is because $\stackrel{\mathbf{~}}{𝑨}=𝑨-𝑽⪰0$, and therefore, $\Vert 𝑽\Vert \le \Vert 𝑨\Vert \le (1+ϵ)$. Hence, it suffices to bound ${\Vert {\mathrm{\Pi }}_{\nu }𝒘\Vert }^2=O(ϵ)$.

   We can write $𝒘=\frac{{\sum }_{i=1}^n{\lambda }_i^K{\alpha }_i{𝒖}_i}{\sqrt{{\sum }_{i=1}^n{\lambda }_i^{2K}{\alpha }_i^2}}$ where ${\lambda }_i,{𝒖}_i$’s are the eigenvalues and eigenvectors of $𝑨$ and ${\alpha }_i\sim N(0,1)$. Define $𝒛={\sum }_{i=1}^n{z}_i{𝒖}_i$ where $z_i={\lambda }_i^K{\alpha }_i$. That is, $𝒘=\frac{𝒛}{\Vert 𝒛\Vert }$. Since $\Vert {\mathrm{\Pi }}_{\nu }𝒘\Vert =\Vert {\mathrm{\Pi }}_{\nu }𝒛\Vert /\Vert 𝒛\Vert$, it suffices to show that ${\Vert {\mathrm{\Pi }}_{\nu }𝒛\Vert }^2\le O(ϵ){\Vert 𝒛\Vert }^2$. We show this in two separate cases. In both cases, we start with the following bound

   $${\Vert {\mathrm{\Pi }}_{\nu }𝒛\Vert }^2\le {\lambda }_{a_{\nu }}^{2K}\cdot \dim (T_{\nu }-\tilde{T}),$$

   which holds with high probability. To see this, let ${𝒈}_{\nu }\sim N(0,1)$ be a gaussian vector in the space $T_{\nu }-\tilde{T}$. We can couple ${\text{g}}_{\nu }$ with ${\mathrm{\Pi }}_{\nu }𝒛$ so that ${\mathrm{\Pi }}_{\nu }𝒛$ is dominated by ${\lambda }_{a_{\nu }}^K\cdot {𝒈}_{\nu }$. So ${\Vert {\mathrm{\Pi }}_{\nu }𝒛\Vert }^2\le {\lambda }_{a_{\nu }}^{2K}{\Vert {𝒈}_{\nu }\Vert }^2$. By Lemma 10, the norm square of gaussian vector is concentrated to its dimension so ${\Vert {𝒈}_{\nu }\Vert }^2\le \dim (T_{\nu }-\tilde{T})$ with high probability, thus proving the inequality. Next, we will bound $\dim (T_{\nu }-\tilde{T})$ in terms of $\Vert 𝒛\Vert$ in two cases.

   When $𝝂\mathbf{\notin }𝓘$

   From the definition of the important levels, we have

   Now, we have because ${\alpha }_i\sim N(0,1)$ is gaussian and the norm square of gaussian vector is concentrated to its dimension (Lemma 10). Since ${\alpha }_i=z_i/{\lambda }_i^K$, we have that

   Therefore, we have

   $$\parallel {\mathrm{\Pi }}_{\nu }𝒛{\parallel }^2\le {\lambda }_{a_{\nu }}^{2K}\dim (T_{\nu }-\tilde{T})\le (\frac{{\lambda }_{a_{\nu }}}{{\lambda }_{{}_{b_{\nu -1}}}}){}^{2K}\frac{O(ϵ)}{{\log }^3\frac{n}{ϵ}}\parallel 𝒛\parallel {}^2\le O(ϵ)\parallel 𝒛\parallel {}^2$$

   where the last inequality is trivial because ${\lambda }_{b_{\nu -1}}\ge {\lambda }_{a_{\nu }}$ by definition.

   When $𝝂\mathbf{\in }𝓘$

   In this case, according to (3.1), we can assume

   $$\dim (T_{\nu }-\tilde{T})\lesssim ϵd_{\nu }.$$

   Again, by Lemma 10, we have that $d_{\nu }\approx {\sum }_{i=a_{\nu }}^{b_{\nu }}{\alpha }_i^2$ because ${\alpha }_i\sim N(0,1)$ is gaussian. Since ${\alpha }_i=z_i/{\lambda }_i^K$, we have

   $$d_{\nu }\approx \sum _{i=a_{\nu }}^{b_{\nu }}{\alpha }_i^2=\sum _{i=a_{\nu }}^{b_{\nu }}\frac{z_i^2}{{\lambda }_i^{2K}}\le {\Vert 𝒛\Vert }^2/{\lambda }_{b_{\nu }}^{2K}.$$

   Therefore,

   $$\parallel {\mathrm{\Pi }}_{\nu }𝒛{\parallel }^2\le {\lambda }_{a_{\nu }}^{2K}\dim (T_{\nu }-\tilde{T})\le (\frac{{\lambda }_{a_{\nu }}}{{\lambda }_{{}_{b_{\nu }}}}){}^{2K}ϵ\parallel 𝒛\parallel {}^2\le O(ϵ)\parallel z\parallel {}^2$$

   where the last inequality is because ${{(\frac{{\lambda }_{a_{\nu }}}{{\lambda }_{b_{\nu }}})}^{2K}\le (\frac{1-\frac{\nu ϵ}{5\log \frac{n}{ϵ}}}{1-\frac{(\nu +1)ϵ}{5\log \frac{n}{ϵ}}})}^{2K}\approx (1+\frac{ϵ}{2\log \frac{n}{ϵ}}){}^{2K}\approx O(1).$

From these three cases, we can conclude that if $\dim (T_{\nu }-\tilde{T})$ is small for all $\nu \in ℐ$, then ${𝒘}^{\top }\mathrm{𝑽𝒘}\le 35ϵ$, proving our claim.

We defer the formal proofs of the claims made in this section to the full version.