Suppose I have a (labeled) date, where features have many categories. For example, one can take kaggle's Wallmart dataset https://www.kaggle.com/c/walmart-recruiting-trip-type-classification/data. Usually I make one-hot-encoding and then PCA in order to reduce space dimensionality. However, when number of categories is too high, this seems infeasible. Can anyone suggest please how to deal with such data?
To be more precise, suppose we are given a labeled (0/1) dataset of ~250k observations with 5-10 categorical features each of which has ~10k categories. If I use one hot encoding for all features, the design matrix will have ~2.5 billions of entries, which cannot be allocated in RAM. Although, I can use sparse representation, I do not know whether it is possible to process it in such form.
For example, for kNN approach I can provide a simple metric $d(x,y)=\sum \{x \neq y\}$, which solves the issue. However, how can I apply logistic regression, svm or some other approach here?