Recent developments in sensor technology, robotics, communications, signal, and semantic processing and computation have enabled the emergence of new information and inference systems (IIS) within the Information and Communications Technologies umbrella of the Seventh Network Program that accomplish automatic reasoning tasks using a potentially large network of coordinated stationary and mobile platforms carrying sensors of diverse modalities. The promise of IIS lies in their ability to continuously and robustly optimize their performance by intelligently exploiting massive amounts of sensor data in addition to their ability to effectively navigate and coordinate their sensing and computational assets.To date, the core issues underlying IIS have been studied largely in isolation in different communities. It is our belief that real progress on IIS requires a coordinated effort based on a unified mathematical and algorithmic foundation that supports not only efficient sensing, processing, data fusion, and decision making, but also direct performance analysis and prediction.This Marie Curie project will develop a principled theory of IIS that provides predictable, optimal performance for a range of different IIS problems through the effective utilization of the available network of resources. The mathematical foundation of our approach represents a profound re-thinking of the sensor data models and representations based on sparsity and combinatorial optimization algorithms based on submodularity. By unifying concepts from statistical signal processing, geometrical modeling and combinatorial optimization, we develop novel theories and rigorous algorithms towards the fundamental intellectual problem of automated scientific discovery. We will apply and evaluate our approaches on natural image understanding and environmental monitoring to provide a broad scaffold for framing numerous signal processing and machine learning problems encountered in diverse data modalities.