Abstract Iteratively Re-vikted Least Squares (IRLS) är en metod för att lösa minimeringsproblem som involverar icke-kvadratiska kostnadsfunktioner, kanske icke-konvexa och icke-smooth, som dock kan beskrivas som infimum över en familj av kvadratiska funktioner. Denna omvandling föreslår en algoritmisk schema som löser en sekvens av kvadratiska problem som ska hanteras effektivt med verktyg av numeriska linjär algebra. Dess allmänna räckvidd och dess oftast enkla genomförande, omvandlar den ursprungliga icke-konvexa och icke-smooth minimering problem till en mer bekant och lättlöslig quadratic optimering problem, gör det till en mångsidig algoritm. Men trots dess enkelhet, mångsidighet och eleganta analys beror komplexiteten hos IRLS starkt på hur lösningen av de successiva quadratic optimeringar behandlas. För det viktiga speciella fallet med komprimerad avkänning och glesa återhämtningsproblem vid signalbehandling undersöker vi teoretiskt och numeriskt hur noggrant man behöver lösa de kvadratiska problemen med hjälp av konjugatgradientmetoden (CG) i varje iteration för att garantera konvergens. Användningen av CG-metoden kan avsevärt påskynda den numeriska lösningen av de kvadratiska subproblemen, särskilt när snabb matris-vektor multiplikation (exploitering till exempel FFT) finns tillgänglig för den berörda matrisen. Dessutom studerar vi konvergenstalen. Vår modifierade IRLS metod överträffar toppmoderna första ordningen metoder såsom Iterative Hard Thresholding (IHT) eller Fast Iterative Soft-Thresholding Algorithm (FISTA) i många situationer, särskilt i stora dimensioner. Dessutom kan IRLS ofta återställa glesa vektorer från färre mätningar än vad som krävs för IHT och FISTA.
Ett annat försök att accelerera IRLS algoritm är att använda konjugerad lutning metod för lösning av de minst kvadrater problem som uppstår i varje iteration REF.
Conjugate gradient acceleration of iteratively re-weighted least squares methods
{'venue': None, 'journal': 'arXiv: Numerical Analysis', 'mag_field_of_study': ['Mathematics', 'Computer Science']}