Abstrakt. Nedbrytningen av CADECOMP/PARAFAC (CP) är en ledande metod för analys av multiwaydata. Standarden alternerande minst kvadrater algoritm för CP nedbrytning (CP-ALS) innebär en serie av mycket överbestämda linjära minst kvadrater problem. Vi utökar randomiserade minsta kvadrat metoder till tensors och visar arbetsbelastningen av CP-ALS kan drastiskt minskas utan en uppoffring i kvalitet. Vi introducerar tekniker för effektiv förbearbetning, provtagning, och beräkning randomiserade minst kvadrater på en tät tensor av godtycklig ordning, samt en effektiv provtagning-baserad teknik för att kontrollera stopptillståndet. Vi visar också mer allmänt att Khatri-Rao produkten (används inom CP-ALS iteration) producerar villkor gynnsamma för direkt provtagning. I numeriska resultat, ser vi förbättringar i hastighet, minskningar i minne krav, och robusthet med avseende på initiering. Nyckelord. Kanonisk polyadic tensor nedbrytning, CANDECOMP/PARAFAC (CP), multilinjär algebra, randomiserade algoritmer, randomiserade minst kvadrater AMS ämnesklassificeringar. 15A69, 68W20, och många andra. Vi anser att problemet med att accelerera den alternerande minst kvadrater (CP-ALS) algoritm med hjälp av randomisering. Eftersom randomiserade metoder har använts framgångsrikt för att lösa linjära minst kvadrater problem [16, 3, 42], Det är naturligt att de kan visa sig vara fördelaktigt för CP-ALS eftersom dess nyckelkärna är lösningen på en minst kvadrat problem. CP-ALS minst kvadrater underproblem har dock en särskild struktur som redan avsevärt minskar sin kostnad, så det är oklart om skissning skulle vara fördelaktigt eller inte. Trots detta finner vi att våra randomiserade algoritmer avsevärt minskar minnet och de beräknade omkostnaderna för CP-ALS-processen för täta tensorer och dessutom positivt påverkar algoritmisk robusthet. Såvitt vi vet är detta den första framgångsrika tillämpningen av matrisskissningsmetoder inom ramen för CP. Bidragen från detta papper är följande: • Minsta kvadratkoefficientmatris i CP-ALS underproblem är en KhatriRao produkt av faktormatriser. Vår randomiserade algoritm föredrar inkonsekventa matriser. Vi bevisar att koherensen av Khatri-Rao-produkten begränsas ovan av produkten av koherensen av dess faktorer. • Vi introducerar CPRAND algoritmen som använder en randomiserad minst kvadratlösare för subproblemen i CP-ALS och aldrig uttryckligen bildar den fullständiga Khatri-Rao matriser som används i subproblemen. Vi introducerar också den kompletterande CPRAND-MIX-algoritmen som använder effektiv blandning för att främja inkonsekvens och därmed förbättra metodens robusthet.
En randomiserad minst kvadratalgoritm för CP nedbrytning föreslås av REF, som är betydligt snabbare än traditionell CP nedbrytning.
A Practical Randomized CP Tensor Decomposition
{'venue': 'SIAM Journal on Matrix Analysis and Applications, Vol. 39, No. 2, pp. 876-901, 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}