Simplicity of linear representations (of images) makes them a popular tool in imaging analysis applications such as object recognition and image classification. Although several linear representations, namely PCA, ICA, and FDA, have frequently been used, these representations are generally far from optimal in terms of actual application performance. We argue that representations should be chosen with respect to the application and the databases involved. Fixing an application, say object recognition, and assuming that recognition performance is computable for any linear basis (given a classifier and a database), we propose a Monte Carlo simulated annealing method that leads to optimal linear representations by maximizing the recognition performance over all fixed-rank subspaces. We illustrate this method on two popular databases.