English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

In this work, we study the performance of sub-gradient method (SubGM) on anatural nonconvex and nonsmooth formulation of low-rank matrix recovery with$\ell_1$-loss, where the goal is to recover a low-rank matrix from a limitednumber of measurements, a subset of which may be grossly corrupted with noise.We study a scenario where the rank of the true solution is unknown andover-estimated instead. The over-estimation of the rank gives rise to anover-parameterized model in which there are more degrees of freedom thanneeded. Such over-parameterization may lead to overfitting, or adversely affectthe performance of the algorithm. We prove that a simple SubGM with smallinitialization is agnostic to both over-parameterization and noise in themeasurements. In particular, we show that small initialization nullifies theeffect of over-parameterization on the performance of SubGM, leading to anexponential improvement in its convergence rate. Moreover, we provide the firstunifying framework for analyzing the behavior of SubGM under both outlier andGaussian noise models, showing that SubGM converges to the true solution, evenunder arbitrarily large and arbitrarily dense noise values, and--perhapssurprisingly--even if the globally optimal solutions do not correspond to theground truth. At the core of our results is a robust variant of restrictedisometry property, called Sign-RIP, which controls the deviation of thesub-differential of the $\ell_1$-loss from that of an ideal, expected loss. Asa byproduct of our results, we consider a subclass of robust low-rank matrixrecovery with Gaussian measurements, and show that the number of requiredsamples to guarantee the global convergence of SubGM is independent of theover-parameterized rank.

Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization