Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models
Published version
Peer-reviewed
Repository URI
Repository DOI
Change log
Authors
Abstract
jats:titleAbstract</jats:title>jats:pWe study the problem of recovering an unknown signal jats:inline-formulajats:alternativesjats:tex-math$${\varvec{x}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mix</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> given measurements obtained from a generalized linear model with a Gaussian sensing matrix. Two popular solutions are based on a linear estimator jats:inline-formulajats:alternativesjats:tex-math$$\hat{\varvec{x}}^\mathrm{L}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:miL</mml:mi> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula> and a spectral estimator jats:inline-formulajats:alternativesjats:tex-math$$\hat{\varvec{x}}^\mathrm{s}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:mis</mml:mi> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>. The former is a data-dependent linear combination of the columns of the measurement matrix, and its analysis is quite simple. The latter is the principal eigenvector of a data-dependent matrix, and a recent line of work has studied its performance. In this paper, we show how to optimally combine jats:inline-formulajats:alternativesjats:tex-math$$\hat{\varvec{x}}^\mathrm{L}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:miL</mml:mi> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula> and jats:inline-formulajats:alternativesjats:tex-math$$\hat{\varvec{x}}^\mathrm{s}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:mis</mml:mi> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>. At the heart of our analysis is the exact characterization of the empirical joint distribution of jats:inline-formulajats:alternativesjats:tex-math$$({\varvec{x}}, \hat{\varvec{x}}^\mathrm{L}, \hat{\varvec{x}}^\mathrm{s})$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mo(</mml:mo> mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo,</mml:mo> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:miL</mml:mi> </mml:msup> mml:mo,</mml:mo> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:mis</mml:mi> </mml:msup> mml:mo)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> in the high-dimensional limit. This allows us to compute the Bayes-optimal combination of jats:inline-formulajats:alternativesjats:tex-math$$\hat{\varvec{x}}^\mathrm{L}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:miL</mml:mi> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula> and jats:inline-formulajats:alternativesjats:tex-math$$\hat{\varvec{x}}^\mathrm{s}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:mis</mml:mi> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>, given the limiting distribution of the signal jats:inline-formulajats:alternativesjats:tex-math$${\varvec{x}}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mix</mml:mi> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>. When the distribution of the signal is Gaussian, then the Bayes-optimal combination has the form jats:inline-formulajats:alternativesjats:tex-math$$\theta \hat{\varvec{x}}^\mathrm{L}+\hat{\varvec{x}}^\mathrm{s}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:miθ</mml:mi> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:miL</mml:mi> </mml:msup> mml:mo+</mml:mo> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:mis</mml:mi> </mml:msup> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula> and we derive the optimal combination coefficient. In order to establish the limiting distribution of jats:inline-formulajats:alternativesjats:tex-math$$({\varvec{x}}, \hat{\varvec{x}}^\mathrm{L}, \hat{\varvec{x}}^\mathrm{s})$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:mrow mml:mo(</mml:mo> mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo,</mml:mo> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:miL</mml:mi> </mml:msup> mml:mo,</mml:mo> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:mis</mml:mi> </mml:msup> mml:mo)</mml:mo> </mml:mrow> </mml:math></jats:alternatives></jats:inline-formula>, we design and analyze an approximate message passing algorithm whose iterates give jats:inline-formulajats:alternativesjats:tex-math$$\hat{\varvec{x}}^\mathrm{L}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:miL</mml:mi> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula> and approach jats:inline-formulajats:alternativesjats:tex-math$$\hat{\varvec{x}}^\mathrm{s}$$</jats:tex-math><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> mml:msup mml:mover mml:mrow mml:mix</mml:mi> </mml:mrow> mml:mo^</mml:mo> </mml:mover> mml:mis</mml:mi> </mml:msup> </mml:math></jats:alternatives></jats:inline-formula>. Numerical simulations demonstrate the improvement of the proposed combination with respect to the two methods considered separately.</jats:p>
Description
Funder: Institute of Science and Technology (IST Austria)
Keywords
Journal Title
Conference Name
Journal ISSN
1615-3383