ON LEAST SQUARES EUCLIDEAN DISTANCE MATRIX APPROXI

ONLEASTSQUARESEUCLIDEANDISTANCEMATRIXAPPROXIMATIONANDCOMPLETIONDAVIDI.CHU∗,HUNTERC.BROWN†,ANDMOODYT.CHU‡Abstract.TheEuclideandistancematrixapproximationproblemaswellasthecompletionproblemhavereceivedalotofattentioninrecentyearsbecauseoftheirmanyimportantappli-cations.Incontrasttothemanyinterestingbutoftensophisticatedalgorithmsproposedintheliterature,thispaperoffersarelativelystraightforwardprocedurethatcantacklebothproblemsbythesameframework.ThelocationvectorswhoserelativedistancesquaresformtheentriesoftheEuclideandistancematrixareuseddirectlyasparametersintheleastsquaresformulation.ItisshownhowbothgradientandHessianoftheobjectivefunctioncanbecalculatedexplicitlyinblockformand,thus,canbeassembledblockbyblockaccordingtodesignatedlocations.Highlyeffectiveconventionaloptimizationtechniquescanthenutilizedtoobtaintheleastsquaressolu-tion.Theapproachcanbeappliedtoavarietyofproblemsarisinginbiologicalorengineeringapplications,includingmolecularstructureanalysis,proteinfoldingproblem,remoteexplorationandsensing,antennaarrayprocessing,andutilityallocationproblem.Keywords.distancegeometry,leastsquaresapproximation,matrixcompletion,molecularstructure,proteinfolding,utilityallocation,conformationalanalysis.1.Introduction.Theendeavorthat,“giventhedistanceandchiralitycon-strainswhichdefine(ourstateofknowledgeof)amobilemolecule,findoneormoreconformationswhichsatisfythem,orelseprovethatnosuchconformationsexists,”hasbeenreferredtoastheFundamentalProbleminDistanceGeometryin[7].Thenotionofdistancegeometry,initiatedbyMengerandSchoenbenginthe1930’s,hasbeenanareaofactiveresearchbecauseofitsmanyimportantapplications,includ-ingmolecularconformationproblemsinchemistry[7],multidimensionalscalinginbehavioralsciences[10,18],andmultivariateanalysisinstatistics[20].Thearticle[13]isanexcellentreferencethatexpoundstheframeworkofEuclideandistancegeometryingeneral.Moreextensivediscussiononthebackgroundandapplicationsofdistancegeometrycanbefoundin[7].Oneofthemostbasicrequisitionsinthestudyofdistancegeometryistheinformationofinter-pointrelationships.Givennparticlesatlocationsp1,...,pninthespaceRm,thecorrespondingEuclideandistancematrixQ(p1,...,pn)=[qij]isthen×nsymmetricandnonnegativematrixwhoseentryqijisdefinedbyqij=kpi−pjk2,i,j=1,...,n,(1.1)∗DepartmentofBiomedicalEngineering,YaleUniversity,NewHaven,CT06520-8042.email:[e-mail].†DepartmentofMathematics,NorthCarolinaStateUniversity,Raleigh,NC27695-8205.email:[e-mail]‡DepartmentofMathematics,NorthCarolinaStateUniversity,Raleigh,NC27695-8205.email:[e-mail]inpartbytheNationalScienceFoundationundergrantsDMS-9803759andDMS-0073056.1wherek·kdenotestheEuclideannorminRm.Inotherwords,thedistancematrixQ(p1,...,pn)=[qij]containsanexhaustiverecordofrelativespacingbetweenanytwoofthenparticlesinRm.Formostreal-worldapplications,weonlyneedtobeconcernedaboutthecasem=3.Nonetheless,thetheorypresentedhereinaftercanbeextendedtoageneraldimensionm.Beawarethatqijin(1.1)isdefinedtobethedistancesquare.Thecorrespondingproblemtothefollowingdiscussionbutwithoutthesquareshasaverydifferentnatureandanevenlongerhistory.Itperhapsdatesbacktothe17thcenturywhenFermatstudiedtheproblemoffindingtheshortestnetworkinterconnectionpointsonaplane.NowadaystheproblemwithoutthesquaresisbetterknownastheEuclideanfacilitieslocationproblemandtheSteinerminimaltreeproblembothofwhichwillnotbediscussedinthispaper.Euclideandistancematricesenjoysmanyinterestingproperties.Thethesis[8],forexample,summarizesseveralequivalentformsofEuclideandistancematrices.TheEuclideandistancematricesarecloselyconnectedtopositivesemidefinitema-trices[16,17].Severalothertheoreticalresultscanbefoundinarticlessuchas[2,9,11,14].Amongthese,wefindtherankstructureofEuclideandistancema-tricesmostpeculiar.Thatis,regardlessofthesizenofthematrix,anEuclideandistancematrixisalwaysrankdeficient.Thefollowingresultiswellestablishedintheliterature.Theorem1.1.Foranyn≥m+2,therankofQisnogreaterthanm+2andisgenericallym+2.TheEuclideandistancematrixforageometricentityembeddedinR3withatleast5points,forinstance,isgenericallyofrank5regardlessofthenumbernofpointsinvolved.Oncealltheinter-particledistancesareinhand,itisasimpletasktoconstructthe(3-dimensional)geometricstructure.Thefactthatadistancematrixisalwaysrankdeficientstronglysuggeststhatmanyentriesinthematrixprovideredundantinformation.Indeed,notalltheinter-particledistancesareneededfortheconstruction.Tocharacterizewhenandwhatpartialinformationofinter-particledistanceswillbesufficientforthedeterminationoftheentiregeometricstructureisaninterestingandverychallengingopenquestionbyitself.Suchataskisreferredtoacompletionproblemintheliterature.Completionproblemsforspecialcasessuchasn-vertexpolyhedronsarenotdifficulttoanswer.Theoreticalresultsformoregeneralconfigurationsareknownonlyintermsofabstractgraphtheory[2,15]andisNP-hard.Despitethelackofasatisfactorytheory,numericalmethodfortheEuclideandistancematrixcompletionproblemabound[1,15,23].Inthispaper,weseektodelineateasimilarnotiontotacklethisimportantcomplet