How to handle missing data in a small $n$ large $k$ machine learning scenario? I have a sample size $N=130$ and $1000$ variables. I am using machine learning techniques (SVM) for analysing the data.
Some variables in the dataset have values that are so huge that they must be errors (so, kind of missing values).
Because the sample size is relatively small, I am using nested ten-fold cross-validation and a grid search for deciding the hyperparameters. Thus, the computational load is already very heavy.
Now, how should I go about handling the missing data? Clearly, I cannot delete any samples. Excluding variables might work, though I would like to still avoid it, since there is typically one to three bad values per variable, if any. I read that multiple imputation is nowadays widely used, but I might not afford the extra computational load.
So I am looking for a one-time imputation method, that is considered good enough to be used in scientific research.
Overall, the number of bad values is probably less than 0.1% of the dataset. Anyway, the classifiers will surely fail if some values are 100000x larger than is even theoretically possible considering what they represent.
 A: Missing data is always a delicate area in analyses.  Unfortunately there is no 'gold standard' and many times researchers simply exclude samples with missing values (which you are trying to avoid and also has its own implications).  There are many methods that are acceptable but the most important part is that you document and report whatever method you implement.  The first thing you should ask is ‘Why are my data missing?’  There are generally considered 3 different scenarios.


*

*Missing Completely at Random (MCAR) – Ideal situation, nothing can explain what certain values are missing.

*Missing at Random (MAR) – Data is missing conditionally at random, that the data ‘may’ depend on an observed measurement.

*Missing not at Random (NMAR) – Data is missing conditionally, that the data depends on an unobserved measurement.  Worst scenario, must be very careful about your missing value imputation.
If your data fit either MCAR or MAR you can jump in to the next stage.  If NMAR, then you should be very cautious and explore specific methods for this scenario.
Next, naturally it depends on your data.  There are several simple methods that may work very well if you are missing only a few data points.  These include mean, median, and minimum imputation.  Here is already a place to apply your knowledge of your dataset.  Let's look at an example:
Let's say I have run a mass spectrometry experiment I measured many variables (100’s to 1000’s) but not every variable was seen in each sample.  Now, I could explore this dataset and see that the variables which are missing are only seen at low levels or very high levels.  In this scenario, it may be best to impute the ‘minimum’ (either of measured value or machine detection limit) as it is probable that the variable levels are below detection levels.  An oversimplification of a complex experiment but should demonstrate the idea.
Of course, there are far more advanced techniques you can also apply.  I am not sure about your programming background but I primarily use R for this type of analysis.  There are many methods available in R.  These can include using k-nearest neighbors (KNN) and bagged trees which are included the caret R package, which I may add is wonderfully documented here and you may find useful for your model training (including parallelism to speed things up).   There is also the missMDA package for PCA, MFA, MCA, FAMD imputation.  There are also packages that are strictly for the purpose of missing value imputation such as mice and Amelia.  Amelia is nice that it allows parallelism but I have read that it may cross if you have highly collinear variables.  The mice package is nice for exploring your missing data.  There is an example of implementing it here, however I have also heard that mice may take a long time (feel free to experiment).
Regarding your very high values, if you are certain that they are impossible you can still apply the above techniques where you have specified a cutoff for 'too high therefore missing value'.  Again you must decide whether a simple or advanced method is most appropriate.  Even with all the computers and mathematical advancements, there still is 'no free lunch' but this information should help get you started.
