Dimension Reduction in Categorical Data with missing values
45% of the data have at least one missing value, you say. This is impressive. I would first look if there is no pattern. You say they are missing at random. Have you tested for MAR ? Have you tested for MAR for sub-groups ? 
Not knowing your data I would first look if there are not cases with many missing values and see if there are theoretical or practical reasons to exclude them. Practical reasons are the production of the data. They might be that they were not well observed, the machine producing the data did not turn all the time, the survey did not cover all countries all the time, etc. For instance, you have survey data on current occupation, but part of the respondents are retired. So they have to be (system-)missing. You can not replace these data with some computed value.
Maybe you can cut slices out of the cases with full and look for the conditions of data production.
I have a regression model in which the dependent variable is continuous but ninety percent of the independent variables are categorical(both ordered and unordered) and around thirty percent of the records have missing values(to make matters worse they are missing randomly without any pattern, that is, more that forty five percent of the data hava at least one missing value). There is no a priori theory to choose the specification of the model so one of the key tasks is dimension reduction before running the regression. While I am aware of several methods for dimension reduction for continuous variables I am not aware of a similar statical literature for categorical data (except, perhaps, as a part of correspondence analysis which is basically a variation of principal component analysis on frequency table). Let me also add that the dataset is of moderate size 500000 observations with 200 variables. I have two questions.

Is there a good statistical reference out there for dimension reduction for categorical data along with robust imputation (I think the first issue is imputation and then dimension reduction)?
This is linked to implementation of above problem. I have used R extensively earlier and tend to use transcan and impute function heavily for continuous variables and use a variation of tree method to impute categorical values. I have a working knowledge of Python so if something is nice out there for this purpose then I will use it. Any implementation pointers in python or R will be of great help.
Thank you.