  For the problem of multi-class linear classification and feature selection,
we propose approximate message passing approaches to sparse multinomial
logistic regression (MLR). First, we propose two algorithms based on the Hybrid
Generalized Approximate Message Passing (HyGAMP) framework: one finds the
maximum a posteriori (MAP) linear classifier and the other finds an
approximation of the test-error-rate minimizing linear classifier. Then we
design computationally simplified variants of these two algorithms. Next, we
detail methods to tune the hyperparameters of their assumed statistical models
using Stein's unbiased risk estimate (SURE) and expectation-maximization (EM),
respectively. Finally, using both synthetic and real-world datasets, we
demonstrate improved error-rate and runtime performance relative to existing
state-of-the-art approaches to sparse MLR.
