Feature Engineering for Sparse Data

Scenario

You're working on a supervised learning task where most features come from high-cardinality categorical fields and text-like signals, so the design matrix is very high-dimensional and mostly zeros. You need a practical way to create useful features without overfitting or making training too expensive.

Question

How do you approach feature engineering for high-dimensional, sparse datasets?