Can you run clustering algorithms on perfectly collinear data? Let's say I have the data set $x_i,y_i,z_i$, where $z_i=y_i-x_i$ or $z_i=f(x_i,y_i)$.
Can I run clustering algorithms on this data set? I wanted to add non-linear or linear combinations of variables because they may have information that is useful for clustering. I'm not sure the clustering algorithms can detect these relationships themselves. 
As an extreme case, I want to consider a perfect collinearity. If these algos can be applied to perfectly collinear data, then they surely can be applied to nonlinear relationships.
There's a similar question on k-means clustering, but it's not satisfactory for two reasons. 
It's about k-means specifically, and my question is more general clustering. Second, it doesn't have an accepted answer, because the answers are not complete.
 A: You can always apply the algorithms to any data sets. You can also always pre-whiten (or drop the columns that cause collinearity) from 
your data matrix. The question, IMO, is therefore not whether these algorithms can be computed on (nearly) collinear data matrices $\pmb X$ but whether the estimates you obtain from these clustering algorithms are affected by the covariance structure of the data.

(The argument below can be slightly modified to also account for soft clustering algorithms, but that would make the explanation more complex because it will require the introduction of a weight function, so for simplicity's sake I will stick to hard clustering algorithms.)
Given $\pmb X$ an $n$ by $p$ dataset with rows $\{\pmb x_i\}_{i=1}^n$, a hard clustering algorithm realizes a partition of $\{1:n\}$ into $J>1$ non overlapping subsets $\{C_j\}_{j=1}^J$. 
Consider the results of such a partition. The argument below could be made of other estimates derived from the partitions $\{C_j\}_{j=1}^J$ (see paper linked below) but for simplicity's sake I will  keep the focus on the estimated cluster centres $\{\pmb t(\pmb X,C_j)\}_{j=1}^J$: each $\pmb t(\pmb X,C_j)$ is a $p$-vector and gives a location estimate for the corresponding cluster. For example, $\pmb t(\pmb X,C_j)$ could be the intra cluster mean:
$$\pmb t(\pmb X,C_j)=\mbox{ave}_{i\in C_j} \pmb x_i$$

A location estimator $\pmb t(\pmb X,C_j)$ for which it holds that: 
$$(1)\quad \pmb t(\pmb A\pmb X,C_j)=\pmb A \pmb t(\pmb X,C_j)$$ 
for any non singular $p$ by $p$ matrix $\pmb A$ is said to be affine equivariant. 
From a statistical point of view, affine equivariant location estimates are not affected by the covariance structure of the data matrix $\pmb X$. This is because when a non singular transformation is applied to the data, these estimates transforms like the data. Therefore, they yield statistically equivalent estimates whether they are ran on $\pmb X$ or on a whitened copy of $\pmb X$. This definition can be extended to also hold even if some columns of $\pmb X$ are nearly collinear (a related but stronger property called exact fit insures that the location estimates also transform like the data when  $\pmb X$ contains exactly collinear columns or when $\pmb A$ is singular). 

My understanding is that the OP is essentially asking (at the minimum) for clustering methods that yield affine equivariant estimates (from a statistical point of view, such estimates would not be affected by the covariance structure of the data). At the maximum, the OP is asking for clustering methods that yield estimates having the exact fit property. 
A well known result [0] (ungated copy) is that $(1)$ (and the exact fit property) holds only if $\#\{C_j\}/n>1/2$. This condition excludes all clustering methods as defined in the intro to this answer.    



*

*(0) H. P. Lopuhaa and P. J. Rousseeuw (1991). Breakdown Points of Affine Equivariant Estimators of Multivariate Location and Covariance Matrices.     Ann. Statist. Volume 19, Number 1, 229-248.

A: The following is not an attempt to comprehensively answer your interesting (+1) question, but rather conveniently store and share with you and others some relevant, in my opinion, papers:


*

*"A practitioner's guide to cluster-robust inference" - a 2013 working paper (almost final pre-print version) by A. Colin Cameron and Douglas L. Miller;

*"Cluster analysis gets complicated" - a 2003 paper by Rajan Sambandam (published in Marketing Research journal);

*"Using cluster analysis to improve marketing experiments" - a 1971 paper by George S. Day and Roger M. Heeler (published in Journal of Marketing Research).
A: If you can define a good distance function, then distance based algorithms will work just fine on the transformed data.
If your preprocessing was not good, then the results are likely to suffer even more.
Plus, you will be bitten by the curse of dimensionality earlier. The more features you add, the more even the relative distances get - everything is similar/disssimilar the same way.
