A New Look at the Power Method for Fast Subspace Tracking
Identifieur interne : 001A66 ( Istex/Corpus ); précédent : 001A65; suivant : 001A67A New Look at the Power Method for Fast Subspace Tracking
Auteurs : Yingbo Hua ; Yong Xiang ; Tianping Chen ; Karim Abed-Meraim ; Yongfeng MiaoSource :
- Digital Signal Processing [ 1051-2004 ] ; 1999.
English descriptors
- KwdEn :
- Algorithm, Arbitrary initializations, Asymmetric square root, Convergence, Convergent, Converges, Covariance, Covariance matrix, Eigenvalue, Eigenvector, Exponential convergence property, Ieee, Ieee trans, Initial matrix, Iteration, Leakage factor, Malase, Matrix, Mild condition, Natural power method, Neural networks, Novel information criterion, Orthogonality, Orthonormal, Other methods, Past method, Performance comparison, Power method, Previous estimate, Principal component, Principal components, Principal eigenvector, Principal subspace, Projection approximation, Projection approximation subspace, Random vectors, Right side, Second term, Signal process, Signal processing, Small step size, Step size, Subspace, Trans, Unitary, Unitary matrix, Unitary rotation, Vector sequence, Weight matrix, Weight vector.
- Teeft :
- Algorithm, Arbitrary initializations, Asymmetric square root, Convergence, Convergent, Converges, Covariance, Covariance matrix, Eigenvalue, Eigenvector, Exponential convergence property, Ieee, Ieee trans, Initial matrix, Iteration, Leakage factor, Malase, Matrix, Mild condition, Natural power method, Neural networks, Novel information criterion, Orthogonality, Orthonormal, Other methods, Past method, Performance comparison, Power method, Previous estimate, Principal component, Principal components, Principal eigenvector, Principal subspace, Projection approximation, Projection approximation subspace, Random vectors, Right side, Second term, Signal process, Signal processing, Small step size, Step size, Subspace, Trans, Unitary, Unitary matrix, Unitary rotation, Vector sequence, Weight matrix, Weight vector.
Abstract
Abstract: A class of fast subspace tracking methods such as the Oja method, the projection approximation subspace tracking (PAST) method, and the novel information criterion (NIC) method can be viewed as power-based methods. Unlike many non-power-based methods such as the Given's rotation based URV updating method and the operator restriction algorithm, the power-based methods with arbitrary initial conditions are convergent to the principal subspace of a vector sequence under a mild assumption. This paper elaborates on a natural version of the power method. The natural power method is shown to have the fastest convergence rate among the power-based methods. Three types of implementations of the natural power method are presented in detail, which require respectively O(n2p), O(np2), and O(np) flops of computation at each iteration (update), where n is the dimension of the vector sequence and p is the dimension of the principal subspace. All of the three implementations are shown to be globally convergent under a mild assumption. The O(np) implementation of the natural power method is shown to be superior to the O(np) equivalent of the Oja, PAST, and NIC methods. Like all power-based methods, the natural power method can be easily modified via subspace deflation to track the principal components and, hence, the rank of the principal subspace.
Url:
DOI: 10.1006/dspr.1999.0348
Links to Exploration step
ISTEX:8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">A New Look at the Power Method for Fast Subspace Tracking</title><author><name sortKey="Hua, Yingbo" sort="Hua, Yingbo" uniqKey="Hua Y" first="Yingbo" last="Hua">Yingbo Hua</name><affiliation><mods:affiliation>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</mods:affiliation></affiliation></author><author><name sortKey="Xiang, Yong" sort="Xiang, Yong" uniqKey="Xiang Y" first="Yong" last="Xiang">Yong Xiang</name><affiliation><mods:affiliation>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</mods:affiliation></affiliation></author><author><name sortKey="Chen, Tianping" sort="Chen, Tianping" uniqKey="Chen T" first="Tianping" last="Chen">Tianping Chen</name><affiliation><mods:affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Department of Mathematics, Fudan University, China, Paris, France, California , USA</mods:affiliation></affiliation></author><author><name sortKey="Abed Meraim, Karim" sort="Abed Meraim, Karim" uniqKey="Abed Meraim K" first="Karim" last="Abed-Meraim">Karim Abed-Meraim</name><affiliation><mods:affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Telecom, Paris, France, California , USA</mods:affiliation></affiliation></author><author><name sortKey="Miao, Yongfeng" sort="Miao, Yongfeng" uniqKey="Miao Y" first="Yongfeng" last="Miao">Yongfeng Miao</name><affiliation><mods:affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, U.S. Wireless Corp. California , USA</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508</idno><date when="1999" year="1999">1999</date><idno type="doi">10.1006/dspr.1999.0348</idno><idno type="url">https://api.istex.fr/document/8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001A66</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001A66</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">A New Look at the Power Method for Fast Subspace Tracking</title><author><name sortKey="Hua, Yingbo" sort="Hua, Yingbo" uniqKey="Hua Y" first="Yingbo" last="Hua">Yingbo Hua</name><affiliation><mods:affiliation>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</mods:affiliation></affiliation></author><author><name sortKey="Xiang, Yong" sort="Xiang, Yong" uniqKey="Xiang Y" first="Yong" last="Xiang">Yong Xiang</name><affiliation><mods:affiliation>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</mods:affiliation></affiliation></author><author><name sortKey="Chen, Tianping" sort="Chen, Tianping" uniqKey="Chen T" first="Tianping" last="Chen">Tianping Chen</name><affiliation><mods:affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Department of Mathematics, Fudan University, China, Paris, France, California , USA</mods:affiliation></affiliation></author><author><name sortKey="Abed Meraim, Karim" sort="Abed Meraim, Karim" uniqKey="Abed Meraim K" first="Karim" last="Abed-Meraim">Karim Abed-Meraim</name><affiliation><mods:affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Telecom, Paris, France, California , USA</mods:affiliation></affiliation></author><author><name sortKey="Miao, Yongfeng" sort="Miao, Yongfeng" uniqKey="Miao Y" first="Yongfeng" last="Miao">Yongfeng Miao</name><affiliation><mods:affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, U.S. Wireless Corp. California , USA</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Digital Signal Processing</title><title level="j" type="abbrev">YDSPR</title><idno type="ISSN">1051-2004</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999">1999</date><biblScope unit="volume">9</biblScope><biblScope unit="issue">4</biblScope><biblScope unit="page" from="297">297</biblScope><biblScope unit="page" to="314">314</biblScope></imprint><idno type="ISSN">1051-2004</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">1051-2004</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Arbitrary initializations</term><term>Asymmetric square root</term><term>Convergence</term><term>Convergent</term><term>Converges</term><term>Covariance</term><term>Covariance matrix</term><term>Eigenvalue</term><term>Eigenvector</term><term>Exponential convergence property</term><term>Ieee</term><term>Ieee trans</term><term>Initial matrix</term><term>Iteration</term><term>Leakage factor</term><term>Malase</term><term>Matrix</term><term>Mild condition</term><term>Natural power method</term><term>Neural networks</term><term>Novel information criterion</term><term>Orthogonality</term><term>Orthonormal</term><term>Other methods</term><term>Past method</term><term>Performance comparison</term><term>Power method</term><term>Previous estimate</term><term>Principal component</term><term>Principal components</term><term>Principal eigenvector</term><term>Principal subspace</term><term>Projection approximation</term><term>Projection approximation subspace</term><term>Random vectors</term><term>Right side</term><term>Second term</term><term>Signal process</term><term>Signal processing</term><term>Small step size</term><term>Step size</term><term>Subspace</term><term>Trans</term><term>Unitary</term><term>Unitary matrix</term><term>Unitary rotation</term><term>Vector sequence</term><term>Weight matrix</term><term>Weight vector</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Arbitrary initializations</term><term>Asymmetric square root</term><term>Convergence</term><term>Convergent</term><term>Converges</term><term>Covariance</term><term>Covariance matrix</term><term>Eigenvalue</term><term>Eigenvector</term><term>Exponential convergence property</term><term>Ieee</term><term>Ieee trans</term><term>Initial matrix</term><term>Iteration</term><term>Leakage factor</term><term>Malase</term><term>Matrix</term><term>Mild condition</term><term>Natural power method</term><term>Neural networks</term><term>Novel information criterion</term><term>Orthogonality</term><term>Orthonormal</term><term>Other methods</term><term>Past method</term><term>Performance comparison</term><term>Power method</term><term>Previous estimate</term><term>Principal component</term><term>Principal components</term><term>Principal eigenvector</term><term>Principal subspace</term><term>Projection approximation</term><term>Projection approximation subspace</term><term>Random vectors</term><term>Right side</term><term>Second term</term><term>Signal process</term><term>Signal processing</term><term>Small step size</term><term>Step size</term><term>Subspace</term><term>Trans</term><term>Unitary</term><term>Unitary matrix</term><term>Unitary rotation</term><term>Vector sequence</term><term>Weight matrix</term><term>Weight vector</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: A class of fast subspace tracking methods such as the Oja method, the projection approximation subspace tracking (PAST) method, and the novel information criterion (NIC) method can be viewed as power-based methods. Unlike many non-power-based methods such as the Given's rotation based URV updating method and the operator restriction algorithm, the power-based methods with arbitrary initial conditions are convergent to the principal subspace of a vector sequence under a mild assumption. This paper elaborates on a natural version of the power method. The natural power method is shown to have the fastest convergence rate among the power-based methods. Three types of implementations of the natural power method are presented in detail, which require respectively O(n2p), O(np2), and O(np) flops of computation at each iteration (update), where n is the dimension of the vector sequence and p is the dimension of the principal subspace. All of the three implementations are shown to be globally convergent under a mild assumption. The O(np) implementation of the natural power method is shown to be superior to the O(np) equivalent of the Oja, PAST, and NIC methods. Like all power-based methods, the natural power method can be easily modified via subspace deflation to track the principal components and, hence, the rank of the principal subspace.</div></front></TEI><istex><corpusName>elsevier</corpusName><keywords><teeft><json:string>natural power method</json:string><json:string>matrix</json:string><json:string>iteration</json:string><json:string>principal subspace</json:string><json:string>ieee</json:string><json:string>power method</json:string><json:string>converges</json:string><json:string>convergence</json:string><json:string>unitary</json:string><json:string>ieee trans</json:string><json:string>trans</json:string><json:string>covariance</json:string><json:string>weight matrix</json:string><json:string>eigenvalue</json:string><json:string>covariance matrix</json:string><json:string>malase</json:string><json:string>signal process</json:string><json:string>algorithm</json:string><json:string>convergent</json:string><json:string>orthogonality</json:string><json:string>step size</json:string><json:string>weight vector</json:string><json:string>past method</json:string><json:string>orthonormal</json:string><json:string>unitary matrix</json:string><json:string>principal components</json:string><json:string>eigenvector</json:string><json:string>neural networks</json:string><json:string>projection approximation</json:string><json:string>other methods</json:string><json:string>asymmetric square root</json:string><json:string>principal eigenvector</json:string><json:string>vector sequence</json:string><json:string>previous estimate</json:string><json:string>unitary rotation</json:string><json:string>subspace</json:string><json:string>arbitrary initializations</json:string><json:string>random vectors</json:string><json:string>second term</json:string><json:string>mild condition</json:string><json:string>initial matrix</json:string><json:string>small step size</json:string><json:string>signal processing</json:string><json:string>performance comparison</json:string><json:string>principal component</json:string><json:string>leakage factor</json:string><json:string>projection approximation subspace</json:string><json:string>exponential convergence property</json:string><json:string>novel information criterion</json:string><json:string>right side</json:string></teeft></keywords><author><json:item><name>Yingbo Hua</name><affiliations><json:string>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</json:string></affiliations></json:item><json:item><name>Yong Xiang</name><affiliations><json:string>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</json:string></affiliations></json:item><json:item><name>Tianping Chen</name><affiliations><json:string>University of Melbourne, Parkville, Victoria, 3052, Australia, Department of Mathematics, Fudan University, China, Paris, France, California , USA</json:string></affiliations></json:item><json:item><name>Karim Abed-Meraim</name><affiliations><json:string>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Telecom, Paris, France, California , USA</json:string></affiliations></json:item><json:item><name>Yongfeng Miao</name><affiliations><json:string>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, U.S. Wireless Corp. California , USA</json:string></affiliations></json:item></author><arkIstex>ark:/67375/6H6-4BNJSH43-9</arkIstex><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><abstract>Abstract: A class of fast subspace tracking methods such as the Oja method, the projection approximation subspace tracking (PAST) method, and the novel information criterion (NIC) method can be viewed as power-based methods. Unlike many non-power-based methods such as the Given's rotation based URV updating method and the operator restriction algorithm, the power-based methods with arbitrary initial conditions are convergent to the principal subspace of a vector sequence under a mild assumption. This paper elaborates on a natural version of the power method. The natural power method is shown to have the fastest convergence rate among the power-based methods. Three types of implementations of the natural power method are presented in detail, which require respectively O(n2p), O(np2), and O(np) flops of computation at each iteration (update), where n is the dimension of the vector sequence and p is the dimension of the principal subspace. All of the three implementations are shown to be globally convergent under a mild assumption. The O(np) implementation of the natural power method is shown to be superior to the O(np) equivalent of the Oja, PAST, and NIC methods. Like all power-based methods, the natural power method can be easily modified via subspace deflation to track the principal components and, hence, the rank of the principal subspace.</abstract><qualityIndicators><score>9.532</score><pdfWordCount>5460</pdfWordCount><pdfCharCount>29453</pdfCharCount><pdfVersion>1.2</pdfVersion><pdfPageCount>18</pdfPageCount><pdfPageSize>554 x 742 pts</pdfPageSize><refBibsNative>true</refBibsNative><abstractWordCount>211</abstractWordCount><abstractCharCount>1363</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>A New Look at the Power Method for Fast Subspace Tracking</title><pii><json:string>S1051-2004(99)90348-2</json:string></pii><genre><json:string>research-article</json:string></genre><host><title>Digital Signal Processing</title><language><json:string>unknown</json:string></language><publicationDate>1999</publicationDate><issn><json:string>1051-2004</json:string></issn><pii><json:string>S1051-2004(00)X0014-0</json:string></pii><volume>9</volume><issue>4</issue><pages><first>297</first><last>314</last></pages><genre><json:string>journal</json:string></genre></host><namedEntities><unitex><date><json:string>1990s</json:string><json:string>1999</json:string><json:string>1990</json:string></date><geogName></geogName><orgName><json:string>Wireless Corp.</json:string><json:string>University of Melbourne</json:string><json:string>Department of Mathematics, Fudan University, China</json:string></orgName><orgName_funder></orgName_funder><orgName_provider></orgName_provider><persName><json:string>C. MacInnes</json:string><json:string>By</json:string></persName><placeName><json:string>Paris</json:string><json:string>France</json:string></placeName><ref_url><json:string>http://www.idealibrary.com</json:string></ref_url><ref_bibl><json:string>[4]</json:string><json:string>[7,8]</json:string><json:string>[23]</json:string><json:string>[22]</json:string><json:string>[8]</json:string><json:string>[1]</json:string><json:string>[21]</json:string><json:string>[3]</json:string><json:string>[20]</json:string><json:string>[15]</json:string><json:string>[12,13]</json:string><json:string>[14]</json:string><json:string>[9]</json:string><json:string>[2]</json:string><json:string>[13]</json:string></ref_bibl><bibl></bibl></unitex></namedEntities><ark><json:string>ark:/67375/6H6-4BNJSH43-9</json:string></ark><categories><wos><json:string>1 - science</json:string><json:string>2 - engineering, electrical & electronic</json:string></wos><scienceMetrix><json:string>1 - applied sciences</json:string><json:string>2 - information & communication technologies</json:string><json:string>3 - networking & telecommunications</json:string></scienceMetrix><scopus><json:string>1 - Physical Sciences</json:string><json:string>2 - Engineering</json:string><json:string>3 - Electrical and Electronic Engineering</json:string><json:string>1 - Physical Sciences</json:string><json:string>2 - Computer Science</json:string><json:string>3 - Signal Processing</json:string></scopus><inist><json:string>1 - sciences appliquees, technologies et medecines</json:string><json:string>2 - sciences exactes et technologie</json:string><json:string>3 - sciences et techniques communes</json:string><json:string>4 - mathematiques</json:string></inist></categories><publicationDate>1999</publicationDate><copyrightDate>1999</copyrightDate><doi><json:string>10.1006/dspr.1999.0348</json:string></doi><id>8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">A New Look at the Power Method for Fast Subspace Tracking</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>©1999 Academic Press</p></availability><date>1999</date></publicationStmt><notesStmt><note type="content">Section title: Regular Article</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">A New Look at the Power Method for Fast Subspace Tracking</title><author xml:id="author-0000"><persName><forename type="first">Yingbo</forename><surname>Hua</surname></persName><note type="biography">E-mail: yhua@ee.mu.oz.au</note><affiliation>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</affiliation></author><author xml:id="author-0001"><persName><forename type="first">Yong</forename><surname>Xiang</surname></persName><affiliation>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</affiliation></author><author xml:id="author-0002"><persName><forename type="first">Tianping</forename><surname>Chen</surname></persName><affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Department of Mathematics, Fudan University, China, Paris, France, California , USA</affiliation></author><author xml:id="author-0003"><persName><forename type="first">Karim</forename><surname>Abed-Meraim</surname></persName><affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Telecom, Paris, France, California , USA</affiliation></author><author xml:id="author-0004"><persName><forename type="first">Yongfeng</forename><surname>Miao</surname></persName><affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, U.S. Wireless Corp. California , USA</affiliation></author><idno type="istex">8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508</idno><idno type="DOI">10.1006/dspr.1999.0348</idno><idno type="PII">S1051-2004(99)90348-2</idno></analytic><monogr><title level="j">Digital Signal Processing</title><title level="j" type="abbrev">YDSPR</title><idno type="pISSN">1051-2004</idno><idno type="PII">S1051-2004(00)X0014-0</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1999"></date><biblScope unit="volume">9</biblScope><biblScope unit="issue">4</biblScope><biblScope unit="page" from="297">297</biblScope><biblScope unit="page" to="314">314</biblScope></imprint></monogr></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1999</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>A class of fast subspace tracking methods such as the Oja method, the projection approximation subspace tracking (PAST) method, and the novel information criterion (NIC) method can be viewed as power-based methods. Unlike many non-power-based methods such as the Given's rotation based URV updating method and the operator restriction algorithm, the power-based methods with arbitrary initial conditions are convergent to the principal subspace of a vector sequence under a mild assumption. This paper elaborates on a natural version of the power method. The natural power method is shown to have the fastest convergence rate among the power-based methods. Three types of implementations of the natural power method are presented in detail, which require respectively O(n2p), O(np2), and O(np) flops of computation at each iteration (update), where n is the dimension of the vector sequence and p is the dimension of the principal subspace. All of the three implementations are shown to be globally convergent under a mild assumption. The O(np) implementation of the natural power method is shown to be superior to the O(np) equivalent of the Oja, PAST, and NIC methods. Like all power-based methods, the natural power method can be easily modified via subspace deflation to track the principal components and, hence, the rank of the principal subspace.</p></abstract></profileDesc><revisionDesc><change when="1999">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla" xml:lang="en"><item-info><jid>YDSPR</jid><aid>90348</aid><ce:pii>S1051-2004(99)90348-2</ce:pii><ce:doi>10.1006/dspr.1999.0348</ce:doi><ce:copyright type="full-transfer" year="1999">Academic Press</ce:copyright></item-info><head><ce:dochead><ce:textfn>Regular Article</ce:textfn></ce:dochead><ce:title>A New Look at the Power Method for Fast Subspace Tracking</ce:title><ce:author-group><ce:author><ce:given-name>Yingbo</ce:given-name><ce:surname>Hua</ce:surname><ce:cross-ref refid="A1"><ce:sup>a</ce:sup></ce:cross-ref><ce:cross-ref refid="FNUN"><ce:sup>f1</ce:sup><ce:footnote id="FNUN"><ce:label>f1</ce:label><ce:note-para>E-mail: yhua@ee.mu.oz.au</ce:note-para></ce:footnote></ce:cross-ref></ce:author><ce:author><ce:given-name>Yong</ce:given-name><ce:surname>Xiang</ce:surname><ce:cross-ref refid="A1"><ce:sup>a</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>Tianping</ce:given-name><ce:surname>Chen</ce:surname><ce:cross-ref refid="A2"><ce:sup>b</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>Karim</ce:given-name><ce:surname>Abed-Meraim</ce:surname><ce:cross-ref refid="A3"><ce:sup>c</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>Yongfeng</ce:given-name><ce:surname>Miao</ce:surname><ce:cross-ref refid="A4"><ce:sup>d</ce:sup></ce:cross-ref></ce:author><ce:affiliation id="A1"><ce:label>a</ce:label><ce:textfn>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</ce:textfn></ce:affiliation><ce:affiliation id="A2"><ce:label>b</ce:label><ce:textfn>University of Melbourne, Parkville, Victoria, 3052, Australia, Department of Mathematics, Fudan University, China, Paris, France, California , USA</ce:textfn></ce:affiliation><ce:affiliation id="A3"><ce:label>c</ce:label><ce:textfn>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Telecom, Paris, France, California , USA</ce:textfn></ce:affiliation><ce:affiliation id="A4"><ce:label>d</ce:label><ce:textfn>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, U.S. Wireless Corp. California , USA</ce:textfn></ce:affiliation></ce:author-group><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>A class of fast subspace tracking methods such as the Oja method, the projection approximation subspace tracking (PAST) method, and the novel information criterion (NIC) method can be viewed as power-based methods. Unlike many non-power-based methods such as the Given's rotation based URV updating method and the operator restriction algorithm, the power-based methods with arbitrary initial conditions are convergent to the principal subspace of a vector sequence under a mild assumption. This paper elaborates on a natural version of the power method. The natural power method is shown to have the fastest convergence rate among the power-based methods. Three types of implementations of the natural power method are presented in detail, which require respectively <ce:italic>O</ce:italic>(<ce:italic>n</ce:italic><ce:sup>2</ce:sup><ce:italic>p</ce:italic>), <ce:italic>O</ce:italic>(<ce:italic>np</ce:italic><ce:sup>2</ce:sup>), and <ce:italic>O</ce:italic>(<ce:italic>np</ce:italic>) flops of computation at each iteration (update), where <ce:italic>n</ce:italic> is the dimension of the vector sequence and <ce:italic>p</ce:italic> is the dimension of the principal subspace. All of the three implementations are shown to be globally convergent under a mild assumption. The <ce:italic>O</ce:italic>(<ce:italic>np</ce:italic>) implementation of the natural power method is shown to be superior to the <ce:italic>O</ce:italic>(<ce:italic>np</ce:italic>) equivalent of the Oja, PAST, and NIC methods. Like all power-based methods, the natural power method can be easily modified via subspace deflation to track the principal components and, hence, the rank of the principal subspace.</ce:simple-para></ce:abstract-sec></ce:abstract></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>A New Look at the Power Method for Fast Subspace Tracking</title></titleInfo><titleInfo type="alternative" lang="en" contentType="CDATA"><title>A New Look at the Power Method for Fast Subspace Tracking</title></titleInfo><name type="personal"><namePart type="given">Yingbo</namePart><namePart type="family">Hua</namePart><affiliation>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</affiliation><description>E-mail: yhua@ee.mu.oz.au</description><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Yong</namePart><namePart type="family">Xiang</namePart><affiliation>Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, California , USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Tianping</namePart><namePart type="family">Chen</namePart><affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Department of Mathematics, Fudan University, China, Paris, France, California , USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Karim</namePart><namePart type="family">Abed-Meraim</namePart><affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Telecom, Paris, France, California , USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Yongfeng</namePart><namePart type="family">Miao</namePart><affiliation>University of Melbourne, Parkville, Victoria, 3052, Australia, Fudan University, China, Paris, France, U.S. Wireless Corp. California , USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article" authority="ISTEX" authorityURI="https://content-type.data.istex.fr" valueURI="https://content-type.data.istex.fr/ark:/67375/XTP-1JC4F85T-7">research-article</genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1999</dateIssued><copyrightDate encoding="w3cdtf">1999</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><abstract lang="en">Abstract: A class of fast subspace tracking methods such as the Oja method, the projection approximation subspace tracking (PAST) method, and the novel information criterion (NIC) method can be viewed as power-based methods. Unlike many non-power-based methods such as the Given's rotation based URV updating method and the operator restriction algorithm, the power-based methods with arbitrary initial conditions are convergent to the principal subspace of a vector sequence under a mild assumption. This paper elaborates on a natural version of the power method. The natural power method is shown to have the fastest convergence rate among the power-based methods. Three types of implementations of the natural power method are presented in detail, which require respectively O(n2p), O(np2), and O(np) flops of computation at each iteration (update), where n is the dimension of the vector sequence and p is the dimension of the principal subspace. All of the three implementations are shown to be globally convergent under a mild assumption. The O(np) implementation of the natural power method is shown to be superior to the O(np) equivalent of the Oja, PAST, and NIC methods. Like all power-based methods, the natural power method can be easily modified via subspace deflation to track the principal components and, hence, the rank of the principal subspace.</abstract><note type="content">Section title: Regular Article</note><relatedItem type="host"><titleInfo><title>Digital Signal Processing</title></titleInfo><titleInfo type="abbreviated"><title>YDSPR</title></titleInfo><genre type="journal" authority="ISTEX" authorityURI="https://publication-type.data.istex.fr" valueURI="https://publication-type.data.istex.fr/ark:/67375/JMC-0GLKJH51-B">journal</genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">199910</dateIssued></originInfo><identifier type="ISSN">1051-2004</identifier><identifier type="PII">S1051-2004(00)X0014-0</identifier><part><date>199910</date><detail type="volume"><number>9</number><caption>vol.</caption></detail><detail type="issue"><number>4</number><caption>no.</caption></detail><extent unit="issue-pages"><start>223</start><end>329</end></extent><extent unit="pages"><start>297</start><end>314</end></extent></part></relatedItem><identifier type="istex">8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508</identifier><identifier type="ark">ark:/67375/6H6-4BNJSH43-9</identifier><identifier type="DOI">10.1006/dspr.1999.0348</identifier><identifier type="PII">S1051-2004(99)90348-2</identifier><accessCondition type="use and reproduction" contentType="copyright">©1999 Academic Press</accessCondition><recordInfo><recordContentSource authority="ISTEX" authorityURI="https://loaded-corpus.data.istex.fr" valueURI="https://loaded-corpus.data.istex.fr/ark:/67375/XBH-HKKZVM7B-M">elsevier</recordContentSource><recordOrigin>Academic Press, ©1999</recordOrigin></recordInfo></mods><json:item><extension>json</extension><original>false</original><mimetype>application/json</mimetype><uri>https://api.istex.fr/document/8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508/metadata/json</uri></json:item></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001A66 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001A66 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:8D466ECAD72E743D9FE3DA85A7B0FD04D49B3508
|texte= A New Look at the Power Method for Fast Subspace Tracking
}}
| This area was generated with Dilib version V0.6.33. |  |