Efficient coordinate-wise leading eigenvector computation
Jialei Wang Weiran Wang Dan Garber Nathan Srebro












 

 

















































































  

















































































































simplelist[1][▹]

#1







#1




















enumthm


















elec-tro-pa-la-tog-ra-phy


acad-e-my acad-e-mies af-ter-thought anom-aly anom-alies
an-ti-deriv-a-tive an-tin-o-my an-tin-o-mies apoth-e-o-ses
apoth-e-o-sis ap-pen-dix ar-che-typ-al as-sign-a-ble as-sist-ant-ship
as-ymp-tot-ic asyn-chro-nous at-trib-uted at-trib-ut-able bank-rupt
bank-rupt-cy bi-dif-fer-en-tial blue-print busier busiest
cat-a-stroph-ic cat-a-stroph-i-cally con-gress cross-hatched data-base
de-fin-i-tive de-riv-a-tive dis-trib-ute dri-ver dri-vers eco-nom-ics
econ-o-mist elit-ist equi-vari-ant ex-quis-ite ex-tra-or-di-nary
flow-chart for-mi-da-ble forth-right friv-o-lous ge-o-des-ic
ge-o-det-ic geo-met-ric griev-ance griev-ous griev-ous-ly
hexa-dec-i-mal ho-lo-no-my ho-mo-thetic ideals idio-syn-crasy
in-fin-ite-ly in-fin-i-tes-i-mal ir-rev-o-ca-ble key-stroke
lam-en-ta-ble light-weight mal-a-prop-ism man-u-script mar-gin-al
meta-bol-ic me-tab-o-lism meta-lan-guage me-trop-o-lis
met-ro-pol-i-tan mi-nut-est mol-e-cule mono-chrome mono-pole
mo-nop-oly mono-spline mo-not-o-nous mul-ti-fac-eted mul-ti-plic-able
non-euclid-ean non-iso-mor-phic non-smooth par-a-digm par-a-bol-ic
pa-rab-o-loid pa-ram-e-trize para-mount pen-ta-gon phe-nom-e-non
post-script pre-am-ble pro-ce-dur-al pro-hib-i-tive pro-hib-i-tive-ly
pseu-do-dif-fer-en-tial pseu-do-fi-nite pseu-do-nym qua-drat-ic
quad-ra-ture qua-si-smooth qua-si-sta-tion-ary qua-si-tri-an-gu-lar
quin-tes-sence quin-tes-sen-tial re-arrange-ment rec-tan-gle
ret-ri-bu-tion retro-fit retro-fit-ted right-eous right-eous-ness
ro-bot ro-bot-ics sched-ul-ing se-mes-ter semi-def-i-nite
semi-ho-mo-thet-ic set-up se-vere-ly side-step sov-er-eign spe-cious
spher-oid spher-oid-al star-tling star-tling-ly sta-tis-tics
sto-chas-tic straight-est strange-ness strat-a-gem strong-hold
sum-ma-ble symp-to-matic syn-chro-nous topo-graph-i-cal tra-vers-a-ble
tra-ver-sal tra-ver-sals treach-ery turn-around un-at-tached
un-err-ing-ly white-space wide-spread wing-spread wretch-ed
wretch-ed-ly Eng-lish Euler-ian Feb-ru-ary Gauss-ian
Hamil-ton-ian Her-mit-ian Jan-u-ary Japan-ese Kor-te-weg
Le-gendre Mar-kov-ian Noe-ther-ian No-vem-ber Rie-mann-ian Sep-tem-ber






































 
   













           
           



















thmTheorem
lem[thm]Lemma














remark
rmk[thm]Remark
*rmk*Remark


















theoremTheorem
lemma[theorem]Lemma


























Efficient coordinate-wise leading eigenvector computation

 

[
Efficient coordinate-wise leading eigenvector computation



















equal*


Jialei Wangequal,uchicago
Weiran Wangequal,ttic
Dan Garberttic
Nathan Srebrottic


uchicagoUniversity of Chicago, 5801 S Ellis Ave, Chicago, IL 60637
tticToyota Technological Insititute at Chicago, 6045 S Kenwood Ave, Chicago, IL 60637

Nathan Srebronati@ttic.edu




eigenvalue problem, power method, shift-and-invert, coordinate descent

0.3in
]










 






We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product.  We establish global convergence with overall runtime guarantees that are at least as good as Lanczos's method and dominate it for slowly decaying spectrum. Our methods are based on combining a shift-and-invert approach with coordinate-wise algorithms for linear regression. 




§ INTRODUCTION



Extracting the top eigenvalues/eigenvectors of a large symmetric matrix is a fundamental step in various machine learning algorithms. One prominent example of this problem is principal component analysis (PCA), in which we extract the top eigenvectors of the data covariance matrix, and there has been continuous effort in developing efficient stochastic/randomized algorithms for large-scale PCA (e.g., ). 
The more general eigenvalue problems for large matrices without the covariance structure is relatively less studied. The method of choice for this problem has been the power method, or the faster but often less known Lanczos algorithm <cit.>, which are based on iteratively computing matrix-vector multiplications with the input matrix until the component of the vector that lies in the tailing eigenspace vanishes. However, for very large-scale and dense matrices, even computing a single matrix-vector product is expensive. 

An alternative is to consider much cheaper vector-vector products, , instead of updating all the entries in the vector on each iteration by a full matrix-vector product, we consider the possibility of only updating one coordinate, by only computing the inner product of single row of the matrix with the vector. Such operations do not even require to store the entire matrix in memory. Intuitively, this may result in an overall significant speedup, in certain likely scenarios, since certain coordinates in the matrix-vector product are more valuable than others for making local progress towards converging to the leading eigenvector.
Indeed, this is the precise rational behind coordinate-descent methods that were extensively studied and are widely applied to convex optimization problems, see <cit.> for a comprehensive survey. Thus, given the structure of the eigenvalue problem which is extremely suitable for coordinate-wise updates, and the celebrated success of coordinate-descent methods for convex optimization, a natural question is whether such updates can be applied for eigenvector computation with provable global convergence guarantees, despite the inherent non-convexity of the problem.

Recently, <cit.> have proposed two such methods, Coordinate-wise Power Method (CPM) and Symmetric Greedy Coordinate Descent (SGCD). Both methods update on each iteration only k entries in the vector, for some fixed k. CPM updates on each iteration the k coordinates 
that would change the most under one step of power method, 
 while SGCD applies a greedy heuristic for choosing the coordinates to be updated. The authors show that CPM enjoys a global convergence rate, with rate similar to the classical power iterations algorithm provided that k, the number of coordinates to be updated on each iteration, is sufficiently large (or equivalently, the "noise" outside the k selected coordinate is sufficiently small). In principle, this might force k to be as large as the dimension d, and indeed in their experiments they set k to grow linearly with d, which is overall not significantly faster than standard power iterations, and does not truly capture the concept of coordinate updates proved useful to convex problems. The second algorithm proposed in <cit.>, SGCD, is shown to converge locally with a linear rate already for k=1 (i.e., only a single coordinate is updated on each iteration), however this results assume that the method is initialized with a vector that is already sufficiently close (in a non-trivial way) to the leading eigenvector. The dependence of CPM and SGCD on the 
inverse relative eigengap[Defined as σ_1 ()/σ_1 () - σ_2 () for a positive semidefinite matrix , where σ_i () is the i-th largest eigenvalue of .] 
of the input matrix is similar to that of the power iterations algorithm, i.e. linear dependence, which in principal is suboptimal, since square-root dependence can be obtained by methods such as the Lanczos algorithm.


We present globally-convergent coordinate-wise algorithms for the leading eigenvector problem which resolves the abovementioned concerns and significantly improve over previous algorithms. 
Our algorithms update only a single entry at each step and enjoy linear convergence. Furthermore, for a particular variant, the convergence rate depends only on the square-root of the inverse relative eigengap, 
yielding a total runtime that dominates that of the standard power method and competes with that of the Lanczos's method. 
In Section <ref>, we discuss the basis of our algorithm, the shift-and-invert power method <cit.>, which transforms the eigenvalue problem into a series of convex least squares problems. 
In Section <ref>, we show the least squares problems can be solved using efficient coordinate descent methods that are well-studied for convex problems. This allow us to make use of principled coordinate selection rules for each update, all of which have established convergence guarantees.

We provide a summary of the time complexities of different globally-convergent methods in Table <ref>. In particular, it is observable that in cases where either the spectrum of the input matrix or the magnitude of its diagonal entries is slowly decaying, 
our methods can yield provable and significant improvements over previous methods. 
For example, for a spiked covariance model whose eigenvalues are 
ρ_1 > ρ_1 - Δ = ρ_2=ρ_3=…, our algorithm (SI-GSL) can have a runtime independent of the eigengap Δ, while the runtime of Lanczos's method depends on 1/√(Δ). 
We also verify this intuition empirically via numerical experiments.











  
Notations We use boldface uppercase letters (, ) to denote matrices, and boldface lowercase letters (, ) to denote vectors. For a positive definite matrix , the vector norm ·_ is defined as _ = √(^⊤) = ^1/2 for any . We use [ij] to denote the element in row i and column j of the matrix , and use [i] to denote the i-th element of the vector  unless stated otherwise. Additionally, [i:] and [:j] denote the i-th row and j-th column of the matrix  respectively.



  
Problem formulation 
We consider the task of extracting the top eigenvector of a symmetric positive definite matrix ∈^d (extensions to other setting are discussed in Section <ref>). Let the complete set of eigenvalues of  be ρ_1 ≥ρ_2 ≥…≥ρ_d ≥ 0, with corresponding eigenvectors _1, …, _d which form an orthonormal basis of ^d. Without loss of generality, we assume ρ_1 ≤ 1 (which can always be obtained by rescaling the matrix). Furthermore, we assume the existence of a positive eigenvalue gap Δ:= ρ_1 - ρ_2 > 0 so that the top eigenvector is unique.


§ SHIFT-AND-INVERT POWER METHOD



In this section, we introduce the shift-and-invert approach to the eigenvalue problem and review its analysis, which will be the basis for our algorithms.

The most popular iterative algorithm for the leading eigenvalue problem is the power method, which iteratively performs the following matrix-vector multiplications and normalization steps

    _t←_t-1,     _t←_t/_t,     for   t=1,….

It can be shown that the iterates become increasingly aligned with the eigenvector corresponding to the largest eigenvalue in magnitude, and the number of iterations needed to achieve 
ϵ-suboptimality in alignment is ( ρ_1/Δlog|_0^⊤_1|/ϵ) <cit.>[We can always guarantee that |_0^⊤_1| = Ω(1/√(d)) by taking _0 to be a random unit vector.]. We see that the computational complexity depends linearly on 1/Δ, and thus power method converges slowly if the gap is small.

Shift-and-invert <cit.> can be viewed as a pre-conditioning approach which improves the dependence of the time complexity on the eigenvalue gap. 
The main idea behind this approach is that, instead of running power method on  directly, we can equivalently run power method on the matrix (λ - )^-1 where λ > ρ_1 is a shifting parameter. Observe that (λ - )^-1 has exactly the same set of eigenvectors as , and its eigenvalues are

    β_1 ≥β_2 ≥…≥β_d > 0,     where  β_i = 1/λ - ρ_i.

If we have access to a λ that is slightly larger than ρ_1, and in particular if λ-ρ_1 =  (1) ·Δ, then the inverse relative eigengap of (λ - )^-1 is β_1/β_1-β_2 = O(1), which means that the power method, applied to this shift and inverted matrix, will converge to the top eigenvector in only a poly-logarithmic number of iterations, in particular, without linear dependence on 1/Δ.

In shift-and-invert power method, the matrix-vector multiplications have the form 
_t← (λ - )^-1_t-1, which is equivalent to solving the convex least squares problem 

    _t←_ 1/2^⊤ (λ - )  - _t-1^⊤.

Solving such least squares problems exactly could be costly itself if d is large. 
Fortunately, power method with approximate matrix-vector multiplications still converges, provided that the errors in each step is controlled; analysis of inexact power method together with applications to PCA and CCA can be found in <cit.>.


