Lågrangmatriskomplettering: En jämförelse av två algoritmer

Abstract

Lågrangmatriskomplettering innefattar algoritmer som fyller ut saknade värden i en matris under antagandet att den kompletta matrisen är av låg rang. Rapporten har undersökt två olika algoritmer för långrangmatriskomplettering, singular value thresholding (SVT) och nor malized iterative hard thresholding (NIHT), på slumpmässigt genererad data och ett urval av databasen Netflix prize data. Rapportens syfte är att bestämma vilken av dessa två algoritmer som lämpar sig bättre för komplettering av Netflix-datan och slumpmässigt genererad data. För att mäta detta undersöktes hur nära algoritmerna konvergerar till de kompletta matriser na i termer av bland annat RMSE samt hur lång tid det tar för de olika algoritmerna att köra givet olika parameterval. Eftersom både NIHT och SVT använder sig av singulärvärdesdekom position som steg i algoritmen undersöktes även hur olika numeriska metoder för att beräkna dessa påverkar precisionen och tiden det tar att köra algoritmerna. Rapporten visade att SVT var snabbare och gav högre precision än NIHT när det kommer till att komplettera Netflix-databasen. Däremot visar NIHT god precision att komplettera slumpmässigt genererad data och kan även göra det snabbare än SVT om en tillräckligt god uppskattning av rangen anges i förväg. Testerna visade även att NIHT kan ge bättre resultat om vissa parametrar i algoritmen justeras, vilket kan vara av intresse för vidare forskning. Nyckelord - Lågrangmatriskomplettering, normalized iterative hard thresholding, singular va lue thresholding, singulärvärdesdekomposition.