Thousands of features and only 70 samples I am working on a regression problem where I have around 5-10 thousand features and have only 65 samples. I am training my algorithm on 55 samples and testing on 10 samples. I am using both Pearson correlation and feature importance using the random forest to remove irrelevant features. In testing data, the random forest algorithm is predicting the average of the training samples.
I have a few questions:
(1) Which ML algorithm should I use when I have very few samples for training (55 samples in my case)?
(2) The Best way of feature selection when we have much more features than samples?

I think the answer to this question is highly data and problem dependent. Some people have reasonably suggested fitting a simple model with regularization, like ridge regression or Lasso, using all features. I also think this is a good idea, and you should try it. But see here: Is ridge regression useless in high dimensions ($n \ll p$)? How can OLS fail to overfit?
In this question, the original poster had a real world data set with approximately as many data as you and the same order of magnitude of features. They found that regularization didn't help, and another user pointed out that for some data sets with many more features than data, regularization is moving in the wrong direction from the min-norm solution.
So the point is, even very general suggestions like "use regularization" might end up being wrong in your specific case, depending on the data.
If I were you, I would start by checking if there is some domain dependent reason to include some variables. If not, check for variables that seem different than the others, different ranges, missing values, etc. Try to figure out what about the reason is for those differences and see if that gives any insight into the data.
Univariate screening like you've tried with Pearson correlation is probably only going to be useful if you find some variables with very high correlation. Use your training set, and just check if you have a situation where most of your variables have correlation between -0.5 and 0.5 (consistent with random noise in your case) but a few of your variables have correlation like 0.65 (unlikely even if you have 100 000 random features). Don't take the top 5% or 10% of features, or auto-exclude features below some correlation. Just check if there is some obviously important feature that you should already know about for domain reasons, but either you forgot something important or someone forgot to tell you something.
Failing something obvious like that, I think you're back to data/problem dependent answers. It matters how you ended up in a situation where 10000 features were created from 65 data. If all or most of your features are pairwise correlated with similar scales, maybe they are all somehow noisy measurements of the same thing. In that case, averaging all the predictors and using the result as a single feature regression might do very well.
