How and why do normalization and feature scaling work? I see that lots of machine learning algorithms work better with mean cancellation and covariance equalization. For example, Neural Networks tend to converge faster, and K-Means generally gives better clustering with pre-processed features. I do not see the intuition behind these pre-processing steps lead to improved performance. Can someone explain this me?
 A: There are two separate issues: 
a) learning the right function
eg k-means: the input scale basically specifies the similarity, so the clusters found depend on the scaling.
regularisation - eg l2 weights regularisation - you assume each weight should be "equally small"- if your data are not scaled "appropriately" this will not be the case
b) optimisation , namely by gradient descent ( eg most neural networks). For gradient descent, you need to choose the learning rate...but a good learning rate ( at least on 1st hidden layer) depends on the input scaling : small [relevant] inputs will typically require larger weights, so you would like larger learning rate for those weight ( to get there faster), and v.v for large inputs... since you only want to use a single learning rate, you rescale your inputs.  ( and whitening ie decorellating is also important for the same reason)
A: It is true that preprocessing in machine learning is somewhat a very black art. It is not written down in papers a lot why several preprocessing steps are essential to make it work. I am also not sure if it is understood in every case. To make things more complicated, it depends heavily on the method you use and also on the  problem domain.
Some methods e.g. are affine transformation invariant. If you have a neural network and just apply an affine transformation to your data, the network does not lose or gain anything in theory. In practice, however, a neural network works best if the inputs are centered and white. That means that their covariance is diagonal and the mean is the zero vector. Why does it improve things? It is only because the optimisation of the neural net works more gracefully, since the hidden activation functions don't saturate that fast and thus do not give you near zero gradients early on in learning.
Other methods, e.g. K-Means, might give you totally different solutions depending on the preprocessing. This is because an affine transformation implies a change in the metric space: the Euclidean distance btw two samples will be different after that transformation.
At the end of the day, you want to understand what you are doing to the data. E.g. whitening in computer vision and sample wise normalization is something that the human brain does as well in its vision pipeline.
A: Why does feature scaling work? I can give you an example (from Quora)

Let me answer this from general ML perspective and not only neural networks. When you collect data and extract features, many times the data is collected on different scales. For example, the age of employees in a company may be between 21-70 years, the size of the house they live is 500-5000 Sq feet and their salaries may range from $30000-$80000. In this situation if you use a simple Euclidean metric, the age feature will not play any role because it is several order smaller than other features. However, it may contain some important information that may be useful for the task. Here, you may want to normalize the features independently to the same scale, say [0,1], so they contribute equally while computing the distance.

A: Pre-processing often works because it does remove features of the data which are not related to the classification problem you are trying solve. Think for instance about classifying sound data from different speakers. Fluctuations in loudness (amplitude) might be irrelevant, whereas the frequency spectrum is the really relevant aspect. So in this case, normalizing amplitude will be really helpful for most ML algorithms, because it removes an aspect of the data that is irrelevant and would cause a neural network to overfit to spurious patterns.  
A: It's simply a case of getting all your data on the same scale: if the scales for different features are wildly different, this can have a knock-on effect on your ability to learn (depending on what methods you're using to do it). Ensuring standardised feature values implicitly weights all features equally in their representation.
A: Some ideas, references and plots on why input normalization can be useful for ANN and k-means:
K-means:

K-means clustering is "isotropic" in all directions of space and
  therefore tends to produce more or less round (rather than elongated)
  clusters. In this situation leaving variances unequal is equivalent to
  putting more weight on variables with smaller variance.

Example in Matlab:
X = [randn(100,2)+ones(100,2);...
     randn(100,2)-ones(100,2)];

% Introduce denormalization
% X(:, 2) = X(:, 2) * 1000 + 500;

opts = statset('Display','final');

[idx,ctrs] = kmeans(X,2,...
                    'Distance','city',...
                    'Replicates',5,...
                    'Options',opts);

plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',12)
hold on
plot(X(idx==2,1),X(idx==2,2),'b.','MarkerSize',12)
plot(ctrs(:,1),ctrs(:,2),'kx',...
     'MarkerSize',12,'LineWidth',2)
plot(ctrs(:,1),ctrs(:,2),'ko',...
     'MarkerSize',12,'LineWidth',2)
legend('Cluster 1','Cluster 2','Centroids',...
       'Location','NW')
title('K-means with normalization')



(FYI: How can I detect if my dataset is clustered or unclustered (i.e. forming one single cluster)
Distributed clustering:

The comparative analysis shows that the distributed clustering results
  depend on the type of normalization procedure.

Artificial neural network (inputs):

If the input variables are combined linearly, as in an MLP, then it is
  rarely strictly necessary to standardize the inputs, at least in
  theory. The reason is that any rescaling of an input vector can be
  effectively undone by changing the corresponding weights and biases,
  leaving you with the exact same outputs as you had before. However,
  there are a variety of practical reasons why standardizing the inputs
  can make training faster and reduce the chances of getting stuck in
  local optima. Also, weight decay and Bayesian estimation can be done
  more conveniently with standardized inputs.

Artificial neural network (inputs/outputs)

Should you do any of these things to your data? The answer is, it
  depends.
Standardizing either input or target variables tends to make the training
  process better behaved by improving the numerical condition (see 
  ftp://ftp.sas.com/pub/neural/illcond/illcond.html) of the optimization
  problem and ensuring that various default values involved in
  initialization and termination are appropriate. Standardizing targets
  can also affect the objective function. 
Standardization of cases should be approached with caution because it
  discards information. If that information is irrelevant, then
  standardizing cases can be quite helpful. If that information is
  important, then standardizing cases can be disastrous.


Interestingly, changing the measurement units may even lead one to see a very different clustering structure: Kaufman, Leonard, and Peter J. Rousseeuw.. "Finding groups in data: An introduction to cluster analysis." (2005).

In some applications, changing the measurement units may even lead one
  to see a very different clustering structure. For example, the age (in
  years) and height (in centimeters) of four imaginary people are given
  in Table 3 and plotted in Figure 3. It appears that {A, B ) and { C,
  0) are two well-separated clusters. On the other hand, when height is
  expressed in feet one obtains Table 4 and Figure 4, where the obvious
  clusters are now {A, C} and { B, D}. This partition is completely
  different from the first because each subject has received another
  companion. (Figure 4 would have been flattened even more if age had
  been measured in days.)
To avoid this dependence on the choice of measurement units, one has
  the option of  standardizing the data. This converts the original
  measurements to unitless variables.



Kaufman et al. continues with some interesting considerations (page 11):

From a philosophical point of view, standardization does not really
  solve the problem. Indeed, the choice of measurement units gives rise
  to relative weights of the variables. Expressing a variable in smaller
  units will lead to a larger range for that variable, which will then
  have a large effect on the resulting structure. On the other hand, by
  standardizing one attempts to give all variables an equal weight, in
  the hope of achieving objectivity. As such, it may be used by a
  practitioner who possesses no prior knowledge. However, it may well be
  that some variables are intrinsically more important than others in a
  particular application, and then the assignment of weights should be
  based on subject-matter knowledge (see, e.g., Abrahamowicz, 1985). On
  the other hand, there have been attempts to devise clustering
  techniques that are independent of the scale of the variables
  (Friedman and Rubin, 1967). The proposal of Hardy and Rasson (1982) is
  to search for a partition that minimizes the total volume of the
  convex hulls of the clusters. In principle such a method is invariant
  with respect to linear transformations of the data, but unfortunately
  no algorithm exists for its implementation (except for an
  approximation that is restricted to two dimensions). Therefore, the
  dilemma of standardization appears unavoidable at present and the
  programs described in this book leave the choice up to the user.

A: This paper is talks only about k-means, but it explains and proves the requirement of data preprocessing quite nicely. 

Standardization is the central
  preprocessing step in data mining, to standardize values of features or attributes from different dynamic range into a
  specific range. In this paper, we have analyzed the performances of the three standardization methods on
  conventional K-means algorithm. By comparing the results on infectious diseases datasets, it was found that the
  result obtained by the z-score standardization method is more effective and efficient than min-max and decimal
  scaling standardization methods.

.

... if there
  are some features, with a large size or great variability,
  these kind of features will strongly affect the clustering
  result. In this case, data standardization would be an
  important preprocessing task to scale or control the
  variability of the datasets.

.

... the features need to be dimensionless
  since the numerical values of the ranges of dimensional
  features rely upon the units of measurements and,
  hence, a selection of the units of measurements may
  significantly alter the outcomes of clustering.
  Therefore, one should not employ distance measures
  like the Euclidean distance without having
  normalization of the data sets

Source: http://maxwellsci.com/print/rjaset/v6-3299-3303.pdf
A: I think that this is done simply so that the feature with a larger value does not overshadow the effects of the feature with a smaller value when learning a classifier . This becomes particularly important if the feature with smaller values actually contributes to class separability .The classifiers like logistic regression would have difficulty learning the decision boundary, for example if it exists at micro level of a feature and we have other features of the order of millions .Also helps the algorithm to converge better . Therefore we don't take any chances when coding these into our algorithms. Its much easier for a classifier, to learn the contributions (weights) of features this way. Also true for K means when using euclidean norms (confusion because of scale). Some algorithms can work without normalizing also.
