A goal of single-cell genome-wide profiling is to reconstruct dynamic transitions during cell differentiation, disease onset and drug response. Single-cell assays have recently been integrated with lineage tracing, a set of methods that identify cells of common ancestry to establish bona fide dynamic relationships between cell states. These integrated methods have revealed unappreciated cell dynamics, but their analysis faces recurrent challenges arising from noisy, dispersed lineage data. In this study, we developed coherent, sparse optimization (CoSpar) as a robust computational approach to infer cell dynamics from single-cell transcriptomics integrated with lineage tracing. Our method is related to the idea of compressed sensing in applied math. Built on assumptions of coherence and sparsity of transition maps, CoSpar is robust to severe downsampling and dispersion of lineage data, which enables simpler experimental designs and requires less calibration. In datasets representing hematopoiesis, reprogramming and directed differentiation, CoSpar identifies early fate biases not previously detected, predicting transcription factors and receptors implicated in fate choice.