Anyone is aware of any proofs that "perfect feature extraction doesn't exist" (on any domain, language, vision, etc).
Either philosophical or mathematical, are fine.
Update: or the inverse problem. I.e. proof of existence for perfect feature extraction, under non-trivial assumption (example of trivial: exponential family of distributions)
Not necessarily related, but still might be interesting if you're trying to think of machine learning in the broadest way possible. The "no free lunch theorem" states that overall, all machine learning models may be worse than random, as the relation between input and output may be pathologically complicated. You can read about it here.
I think this is very closely related to your question, since the most important part of machine learning is feature selection & generation (and indeed most state of the art machine learning solutions stand out in their ability to "correctly" select the right feature representation).
So my 2 cents on your question, which is vague as others have pointed out.
Hope that helped a bit.
In feature extraction, you are generally starting with a high dimensional set of data, with the intent of finding the (hopefully) important, lower dimensional set of factors in your data. As such, you are throwing away some information in your data (assuming you don't have a trivial problem, i.e. one variable is a perfect linear combination of the other variables). There is no way to definitively known that some aspect is unimportant; if you knew exactly what was important, you wouldn't need a statistical model in the first place!
To give a concrete example, consider Principal Components Analysis (PCA). Each component is a linear combination of the original covariate space. These components are usually presented as ordered, where the first component explains more of the total variance in your data than the next, all the way down to the last principal component, which explains the least of your variance.
It is a very common assumption that the first few components are the most important, as they contain the information that explains the most amount of the total variance in data. As such, the feature extraction is to keep the first $k$ components, and this is usually justified with something like "Well, the first 3 components contain 95% of the variance, so we will only consider these variables".
However, it's also quite possible that the last set of principal components are really important: these are the linear combinations that are the most reliable (i.e. lowest variance). It's not hard to imagine that throwing away information about a set of variables that almost always are consistent, except in a few rare cases, might be a very bad idea in certain situations!
In summary: feature extraction is typically concerned with taking high dimensional data and representing it in a lower dimensional space. This means removing some of the information in your data. In general, you can't know exactly a priori what information is important and what is not, so you naturally will lose some information during the feature extraction process.
What if I told you perfect feature extraction is possible? Sufficient statistics are a great example. Say you have samples from a normal $\mathcal{N}(\mu, \sigma^2 )$ of unknown mean and variance. Then, regardless of the number if observations you have, you only need to keep track of two numbers ("features"): sample mean $\frac{1}{n} \sum_{k=1}^{n} x_i$ and sample squared mean $\frac{1}{n} \sum_{k=1}^{n} x_i^2$. These tell you all you need for estimating the true distribution - they contain as much information (from a rigorous information theoretic perspective! see Thomas and Cover for detailed discussion) as the entire sample!!!
So perfect features may exist. Don't be so pessimistic.
