The regular PCA will not help you much here. I can suggest to look into Maximum Variance Unfolding method which is similar to ISOMAP and modify the algorithm so the graph depends not only on distance but also on some other criteria i.e. dependance of  y on particular x.  

Are you looking for feature selection?

http://en.wikipedia.org/wiki/Feature_selection

Matthias

In terms of ML, you definitely want to read about feature selection.

We have been working on something related, which, very roughly, amounts to finding safe association rules over the data set. Depending on how much we squint, we either find sets of variables that have functional relationships among them, or partial functions that describe the different relationships among the variables for the samples.  So far we are only working with binned data, so the generality is not there yet.  Also, the idea requires being willing to detach yourself from linear algebra.

In ML, that is a problem to detect the group of features (interaction).

In my knowledge, you can do 2 steps:

1) Build Random Forests 

2) Use the asso. rules to extract the group of features.

Finally, you can get some x-components as your requirement.

Thank you very much for your answers!

I think the problem is one type of feature selections. As Alexander pointed out, traditional PCA will not help in this case. I think the third type of feature selection method  - Embedded methods may be helpful in this case.

To use this type of method, I may need more assumptions on the underlying model between x and y, so that I can define the objective function (metrics) for selecting the features. 

I really appreciate your help!

Any further comments and/or suggestions are more than welcome!

From what you write it is not clear to me whether y is a continuous or a discrete output (i.e. whether you aim to do time series prediction or classification). If there is reason to assume that y is slowly varying, there is an interesting technique called Slow Feature Analysis (SFA) by Laurenz Wiskott (see http://www.scholarpedia.org/article/Slow_feature_analysis), which might be of interest. SFA is capable of finding nonlinear relationships in the data.  If you aim at doing classification, you might find useful ressources on our project page on SFA (http://lwibs01.gm.fh-koeln.de/blogs/ciop/research/slow-feature-analysis-sfa/)  and in an article of Pietro Berkes listed in the publications..In a sense, we have applied there SFA also to feature selection in the case of gesture recognition.

Another somewhat related technique may be ICA (Independent Component Analysis)

Hope, that helps!

http://lwibs01.gm.fh-koeln.de/blogs/ciop/research/slow-feature-analysis-sfa/

http://www.scholarpedia.org/article/Slow_feature_analysis

There are a number of packages proposed to perform feature selection in R, Matlab... But, I think the simplest way may be to use attribute selection module of Weka software (open source).

In the links below, a description of the GUI for feature selection.

https://www.youtube.com/watch?v=x5wa1w-BpRE

http://safeshare.tv/w/oICsTxOHZG

Although your question clearly regards a feature selection problem, you stated that there exist an underlying functional relation between some of your inputs (which one is unknown) and your output. There is an interesting method (MINE) to assess an existing functional dependency that works much better than the classic "correlation"  and that can be adopted as the basis on which to perform feature selection. In attach the link to the website where to find relevant publications and the software package that implements the technique.  

http://minepy.sourceforge.net/

In terms of statistics, it is the so-called variable importance problem. Many state-of-the-art learning algorithms , such as Lasso and random forests,can output variable importance scores or a subset of important variables.

Dear Huasen,

    I believe that your problem is in the field of feature selection. More specifically, I think you may find use of Wrapper approach the best fit to your problem area. As you may know wrappers operate in two phases one is responsible to select a subset of the feature set and the second phase uses this subset to train the classifier/approximator selected by you in your implementation. It is a well known fact that wrappers provide a better accuracy but longer execution time at the training compared against the filter approach.

In my understanding, your concern about the nonlinear correlation or any correlation between the original features will be indirectly handled in the wrapper approach during the training phase using the selected classifier/approximator. Here a feature subset is selected that may produce the best result (the highest accuracy) at the output. In your problem area, goal is to select a smaller subset of the original feature set such that the execution time is minimized (population of the subset is minimized) while the function accuracy experiences a minimum reduction.

The most important issue here is selection of an appropriate classifier/approximator capable of dealing with non-linearity in your data set.

Good luck

Peyman

Hi all,

Thanks for all of you! I really appreciate for your suggestions, including both theoretic and implementation perspectives. Currently, I focus on the theoretic side and will consider L1-regularized approach (LASSO type policy), since this will be helpful for the sparse scenario.