TY - GEN
T1 - Sparse Linear Regression with Constraints
T2 - 2024 European Control Conference, ECC 2024
AU - Srivastava, Amber
AU - Bayati, Alisina
AU - Salapaka, Srinivasa M.
N1 - Publisher Copyright:
© 2024 EUCA.
PY - 2024
Y1 - 2024
N2 - This work presents a new approach to solve the sparse linear regression problem, i.e., to determine a k - sparse vector w ∈ ℝd that minimizes the cost || y-Aw||22. In contrast to the existing methods, our proposed approach splits this k - sparse vector into two parts - (a) a column stochastic binary matrix V, and (b) a vector x ∈ ℝk. Here, the binary matrix V encodes the location of the k non-zero entries in w. Equivalently, it encodes the subset of k columns in the matrix A that map w to y. We demonstrate that this enables modeling several non-trivial application specific structural constraints on w as constraints on V. The vector x comprises of the actual non-zero values in w. We use Maximum Entropy Principle (MEP) to solve the resulting optimization problem. In particular, we ascribe a probability distribution to the set of all feasible binary matrices V, and iteratively determine this distribution and the vector x such that the associated Shannon entropy gets minimized, and the regression cost attains a pre-specified value. The resulting algorithm employs homotopy from the convex entropy function to the non-convex cost function to avoid poor local minimum. We demonstrate the efficacy and flexibility of our proposed approach in incorporating a variety of practical constraints, that are otherwise difficult to model using the existing benchmark methods.
AB - This work presents a new approach to solve the sparse linear regression problem, i.e., to determine a k - sparse vector w ∈ ℝd that minimizes the cost || y-Aw||22. In contrast to the existing methods, our proposed approach splits this k - sparse vector into two parts - (a) a column stochastic binary matrix V, and (b) a vector x ∈ ℝk. Here, the binary matrix V encodes the location of the k non-zero entries in w. Equivalently, it encodes the subset of k columns in the matrix A that map w to y. We demonstrate that this enables modeling several non-trivial application specific structural constraints on w as constraints on V. The vector x comprises of the actual non-zero values in w. We use Maximum Entropy Principle (MEP) to solve the resulting optimization problem. In particular, we ascribe a probability distribution to the set of all feasible binary matrices V, and iteratively determine this distribution and the vector x such that the associated Shannon entropy gets minimized, and the regression cost attains a pre-specified value. The resulting algorithm employs homotopy from the convex entropy function to the non-convex cost function to avoid poor local minimum. We demonstrate the efficacy and flexibility of our proposed approach in incorporating a variety of practical constraints, that are otherwise difficult to model using the existing benchmark methods.
UR - http://www.scopus.com/inward/record.url?scp=85200600732&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85200600732&partnerID=8YFLogxK
U2 - 10.23919/ECC64448.2024.10591241
DO - 10.23919/ECC64448.2024.10591241
M3 - Conference contribution
AN - SCOPUS:85200600732
T3 - 2024 European Control Conference, ECC 2024
SP - 2105
EP - 2110
BT - 2024 European Control Conference, ECC 2024
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 25 June 2024 through 28 June 2024
ER -