Interdisciplinary Applied Mathematics 40 René Vidal Yi Ma S. Shankar Sastry Generalized Principal Component Analysis Generalized Principal Component Analysis Interdisciplinary Applied Mathematics Volume 40 Editors S.S.Antman L.Greengard P.Holmes SeriesAdvisors LeonGlass RobertKohn P.S.Krishnaprasad JamesD.Murray ShankarSastry JamesSneyd Problems in engineering, computational science, and the physical and biological sciences are using increasingly sophisticated mathematical techniques. Thus, the bridgebetweenthemathematicalsciencesandotherdisciplinesisheavilytraveled. The correspondingly increased dialog between the disciplines has led to the establishmentoftheseries:InterdisciplinaryAppliedMathematics. Thepurposeofthisseriesistomeetthecurrentandfutureneedsfortheinteraction betweenvariousscienceandtechnologyareasontheonehandandmathematicson the other. This is done, firstly, by encouragingthe ways that mathematicsmay be applied in traditional areas, as well as point towards new and innovative areas of applications;and,secondly,byencouragingotherscientificdisciplinestoengagein adialogwithmathematiciansoutliningtheirproblemstobothaccessnewmethods andsuggestinnovativedevelopmentswithinmathematicsitself. Theserieswillconsistofmonographsandhigh-leveltextsfromresearchersworking ontheinterplaybetweenmathematicsandotherfieldsofscienceandtechnology. Moreinformationaboutthisseriesathttp://www.springer.com/series/1390 René Vidal • Yi Ma • S. Shankar Sastry Generalized Principal Component Analysis 123 RenéVidal YiMa CenterforImagingScience SchoolofInformationScience DepartmentofBiomedicalEngineering andTechnology JohnsHopkinsUniversity ShanghaiTechUniversity Baltimore,MD,USA Shanghai,China S.ShankarSastry DepartmentofElectricalEngineering andComputerScience UniversityofCaliforniaBerkeley Berkeley,CA,USA ISSN0939-6047 ISSN2196-9973 (electronic) InterdisciplinaryAppliedMathematics ISBN978-0-387-87810-2 ISBN978-0-387-87811-9 (eBook) DOI10.1007/978-0-387-87811-9 LibraryofCongressControlNumber:2015958763 MathematicsSubjectClassification(2010):30C10,30C40,62-XX,62-07,62-08,62B10,62Fxx,62H12, 62H25,62H35,62Jxx,62J05,62J07,14-XX,14N20,15-XX SpringerNewYorkHeidelbergDordrechtLondon ©Springer-VerlagNewYork2016 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade. Printedonacid-freepaper SpringerScience+Business MediaLLCNewYorkispartofSpringerScience+Business Media(www. springer.com) To Camille,Margot,and RomeoVidal(R.V.) To DianaXiaoyuanZhu, Barron,and HenryMa(Y. M.) To ClaireTomlin,Samuel,and LucySastry(S. S.) Preface Wearenotverypleasedwhenweareforcedtoacceptamathematicaltruthbyvirtueofa complicatedchainofformalconclusionsandcomputations,whichwetraverseblindly,link bylink,feelingourwaybytouch.Wewantfirstanoverviewoftheaimandoftheroad;we wanttounderstandtheideaoftheproof,thedeepercontext. —HermannWeyl Classical theory and methods for the analysis of data were established mainly for engineering and scientific problems that arose five or six decades ago. In these classical settings, engineersor scientists usually had full controlof the data acquisitionprocess.Asaresult,thedatatobeprocessedandanalyzedweretypically cleanandcomplete:theycontainedonlymoderateamountsofnoiseandwereoften adequately collected for the specific task or problem of interest. In that regime, manydataanalysismethodswerebasedontheassumptionthatmostdatasetshave fewer effective degrees of freedom than the dimension of the ambient space. For example,the numberofpixelsinanimagecanberatherlarge,yetmostcomputer vision models used only a few parameters to describe the appearance, geometry, anddynamicsofascene.Thisassumptionmotivatedthedevelopmentofanumber oftechniquesforidentifyinglow-dimensionalstructuresinhigh-dimensionaldata, a problemthatis importantnotonlyforunderstandingthedata,butalso formany practicalpurposessuchasdatacompressionandtransmission.Apopulartechnique for discoveringlow-dimensionalstructure in data is principal componentanalysis (PCA), which assumes that the data are drawn from a single low-dimensional affinesubspaceofahigh-dimensionalspace(Jolliffe1986,2002).PCAisarguably the simplest and most popular dimensionality reduction tool, and it has found widespreadapplicationsinmanyfieldssuchascomputervision(TurkandPentland 1991). However, in the past decade or so, there has been a fundamental regime shift in data analysis. Currently, scientists and engineers often must deal with data whose dimension, size, and complexity expand at an explosive rate. Moreover, they have pretty much lost control of the data acquisition process. For instance, in 2012,350millionphotoswereuploadedto Facebookeveryday,and100hours vii viii Preface ofvideowereuploadedtoYouTubeeachminute.Moreover,itisestimatedthat3.8 trillion photoshad been taken by 2012,10% of them in the last 12 months.1 This and other forms of massive amounts of data on the Internet and mobile networks are being producedby billions of independentconsumersand businesses. How to extractusefulinformationfromsuch massive amountsof data for numeroustasks (such as search, advertisement, scientific analysis) has become one of the biggest engineeringendeavorsofmankind.ManycallittheeraofBigData.Obviously,such aregimeshiftdemandsafundamentalparadigmshiftindataanalysis,sinceclassical theoryandmethodsfordataanalysisweresimplynotdesignedtoworkundersuch conditions. The website of Theoretical Foundations of Big Data Analysis2 puts thingsintoperspective: TheBigDataphenomenonpresentsopportunitiesandperils.Ontheoptimisticsideofthe coin,massivedatamayamplifytheinferentialpowerofalgorithmsthathavebeenshown to be successful on modest-sized data sets. The challenge is to develop the theoretical principles needed toscale inference and learning algorithms tomassive, even arbitrary, scale.Onthepessimisticsideofthecoin,massivedatamayamplifytheerrorratesthatare partandparcelofanyinferentialalgorithm.Thechallengeistocontrolsucherrorsevenin thefaceoftheheterogeneityanduncontrolledsamplingprocessesunderlyingmanymassive datasets. Sincethedataacquisitionprocessisnolongerunderthedatagatherer’scontrol, the structure of the data to be processed or analyzedcan no longerbe assumed to be relatively simple or clean: very often, the data contain significant amounts of noise,corruptedentries,andoutliers;orthedatacouldbeincompleteorinadequate forataskthatarisesonlyafterthedatahavebeencollected;orthedatacouldeven have some degree of unknown nonlinearity due to lack of calibration in the data acquisition. In the past decade, these challenges have led to many revolutionary discoveriesandmuchprogressinwhichmanyoftheclassicalmodelsandmethods for data analysis have been systematically generalized or improvedto make them robust to such bad nuisances in the data. In the context of identifying low- dimensional structures in the data, classical PCA is generalized so that it can robustlyfindthecorrectsubspacestructureofthedatadespitesuchnuisances.The forms of progress include entirely new methods for low-rank matrix completion, robustPCA,kernelPCA,andmanifoldlearning. Anotherchallengethatarisesinthenewregimeisthatwecannolongerassume that the data lie on a single low-dimensional subspace or submanifold. This is becausemanymoderndatasetsarenotcollectedforanyspecifictask.Instead,the datamayhavealreadybeencollected,andthetaskemergesonlyafterward.Hence a data set can be mixed with multiple classes of data of differentnatures, and the intrinsic structure of the data set may be inhomogeneous or hybrid. In this case, the data set may be better represented or approximated by not one, but multiple low-dimensionalsubspacesormanifolds.Figure1givesanexampleoffaceimages 1http://www.buzzfeed.com/hunterschwarz/how-many-photos-have-been-taken-ever-6zgv. 2http://simons.berkeley.edu/programs/bigdata2013. Preface ix Fig.1 Face images from multiple individuals can be well approximated by multiple low- dimensionalsubspaces. under varyingillumination conditions, where each affine subspace correspondsto face images of a different individual. This leads to a general problem: Given a set of data pointsfroma mixture of affine subspaces, howdoes one automatically learn or infer those subspaces from the data? A solution to this problem requires one to cluster or segment the data into multiple groups, each belonging to one subspace, and then identify the parameters of each subspace. To model data with suchmixedsubspacestructures,theclassicalPCAmethodneedstobegeneralized sothatitcansimultaneouslyidentifymultiplesubspacesfromthedata.Thisleads totheso-calledsubspaceclusteringproblem,whichhasreceivedgreatattentionin the last decade and has found widespread applications in computer vision, image processing,patternrecognition,andsystemidentification. PurposeofThisBook The purpose of this book is to provide a comprehensive introduction to the latest advances in the mathematical theory and computational tools for modeling high-dimensional data drawn from one or more low-dimensional subspaces (or manifolds)andcorruptedbynoise,missingentries,corruptedentries,andoutliers. This will require the development of new algebraic, geometric, statistical, and computationaltheoryandmethodsforefficientandrobustestimationofoneormore subspaces.TodistinguishthistheoryandthesemethodsfromclassicalPCA,wecall allsuchadvancedapproachesasgeneralizedprincipalcomponentanalysisorGPCA forshort.3 As we will see in this book, in order to generalize classical PCA to the case of corrupted and mixed data, we need to resort to a body of more advanced mathematical tools from estimation theory, algebraic geometry, high-dimensional 3In the literature, the word generalized is sometimes used to indicate any particular extension to classical PCA (Jolliffe 1986, 2002). In our opinion, each of these extensions is a particular generalization rather than the more systematic generalization that we present in this book. In addition,forthecaseinwhichwewantPCAtohandlelargeamountsofcorruptionsoroutliers,we mayusethespecialnamerobustPCA(RPCA);forthenonlinearcaseinwhicheachcomponentis analgebraicvarietyofhigherdegreesuchasaquadraticsurfaceoramorecomplicatedmanifold, wemayusethenamenonlinearPCAormanifoldlearning;forthecaseofmultiplesubspacesor manifolds,namessuchasmixturesofprobabilisticPCA(MPPCA),subspaceclustering(SC)and hybridcomponentanalysis(HCA)havebeensuggestedandwouldalsobeappropriate.