I have a large linear regression where all the independent variables are logical (ie TRUE/FALSE) and sparse. The data has roughly 10,000 variables and 10 million observations, on average around 20 true values per observation. I’d like to compress the variables or group them together to make the system less unwieldy. For instance, I can combine several variables by logical OR into a new grouped variable. Then I can run a new linear regression on the grouped variables.

I have one grouping based on the interpretation of the variables, and the $R^2$ of its regression is much better than random but also clearly not optimal. My goal is to group the 10.000 original variables into roughly 100 grouped variables with roughly 100 of the original variables in each.

Question: How do I decide which variables to group so that the loss of predictive power (measured as $R^2$ of the models) is minimal? Or how can I improve a grouping?

The number of ways to group the variables is finite, but too big to search through, so I'm looking for an algorithm that is significantly better than random. Even the number of ways to alter a grouping by moving a single variable into another group is too big to try all of them.

Edit in response to comment: the dependent variable is numeric.

Edit in response to PCA: The data is of medical origin, the independent variables are diagnoses, the observations are patients and the dependent variable is treatment cost (in some part of the health industry). In particular, the dependent variable is always positive and the vast majority of model coefficients in the big model is positive as well. Hence using only a subset of the variables would produce a significiant bias for underestimating the dependent variable.