Low-dimensional structure from high-dimensional data is described for example, in the context of video foreground/background segmentation, speech signal background identification, document clustering and other applications where distortions in the observed data may exist. In various embodiments a first convex optimization process is used to find low dimensional structure from observations such as video frames in a manner which is robust to distortions in the observations; a second convex optimization process is used for incremental observations so bringing computational efficiency whilst retaining robustness. In various embodiments error checks are made to decide when to move between the first and second optimization processes. In various examples, the second convex optimization process encourages similarity between the solution it produces and the solution of the first convex optimization process, for example, by using an objective function which is suitable for convex optimization.