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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

In many application areas ranging from bioinformatics to imaging, we are faced with the following question: can we recover a sparse vector xo &#x2208; &#x211D;N from its undersampled set of noisy observations y &#x2208; &#x211D;n, y = Axo+w. The last decade has witnessed a surge of algorithms and theoretical results to address this question. One of the most popular schemes is the &#x2113;p-regularized least squares given by the following formulation:x&#x0302;(y, p) &#x2208; arg minx (1/2)&#x2225;y - Ax&#x2225;22 + &#x03B3;&#x2225;x&#x2225;pp, where p &#x2208; [0, 1]. Among these optimization problems, the case p = 1, also known as LASSO, is the best accepted in practice, for the following two reasons. First, thanks to the extensive studies performed in the fields of high-dimensional statistics and compressed sensing, we have a clear picture of LASSO's performance. Second, it is convex and efficient algorithms exist for finding its global minima. Unfortunately, neither of the above two properties hold for 0 &#x2264; p &lt;; 1. However, they are still appealing because of the following folklores in the high-dimensional statistics. First, x&#x0302;(&#x03B3;, p) is closer to xo than x&#x0302;(&#x03B3;, 1). Second, if we employ iterative methods that aim to converge to a local minima of arg minx (1/2)&#x2225;y - Ax&#x2225;22 + &#x03B3;&#x2225;x&#x2225;pp, then under good initialization, these algorithms converge to a solution that is still closer to xo than x&#x0302;(&#x03B3;, 1). In spite of the existence of plenty of empirical results that support these folklore theorems, the theoretical progress to establish them has been very limited. This paper aims to study the above-mentioned folklore theorems and establish their scope of validity. Starting with approximate message passing (AMP) algorithm as a heuristic method for solving &#x2113;p-regularized least squares, we study the following questions. First, what is the impact of initialization on the performance of the algorithm? Second, when does the algorithm recover the sparse signal xo under a &#x201C;good&#x201D; initialization? Third, when does the algorithm converge to the sparse signal regardless of the initialization? Studying these questions will not only shed light on the second folklore theorem, but also lead us to the answer the first one, i.e., the performance of the global optima x&#x0302;(&#x03B3;, p). For that purpose, we employ the replica analysis1 to show the connection between the solution of AMP and x&#x0302;(&#x03B3;, p) in the asymptotic settings. This enables us to compare the accuracy of x&#x0302;(&#x03B3;, p) and x&#x0302;(&#x03B3;, 1). In particular, we will present an accurate characterization of the phase transition and noise sensitivity of &#x2113;p-regularized least squares for every 0 &#x2264; p &lt;; 1. Our results in the noiseless setting confirm that &#x2113;p-regularized least squares (if &#x03B3; is tuned optimally) exhibits the same phase transition for every 0 &#x2264; p &lt;; 1 and this phase transition is much better than that of LASSO. Furthermore, we show that in the noisy setting, there is a major difference between the performance of &#x2113;p-regularized least squares with different values of p. For instance, we will show that for very small and very large measurement noises, p = 0 and p = 1 outperform the other values of p, respectively.

Does $\ell _{p}$ -Minimization Outperform $\ell _{1}$ -Minimization?