Object illumination and color are critical characteristics of a scene and being able to edit them allows artists to achieve powerful effects. Intrinsic image decomposition is the ideal component for this kind of tasks. By separating the illumination from the scene reflectance, it enables key operations such as recoloring and relighting. Significant progress has been done recently for decomposing static images. However, these algorithms rely on sophisticated optimization schemes that are computationally expensive and orders of magnitude too slow to be applied to video sequences. So much that even an optimized implementation would remain unpractical. In this paper, we introduce a user-guided algorithm that runs fast enough to be used in an interactive setting. Our strategy is to rely on an efficient sparse formulation – we also exploit the same kind of information as successful static methods but use it in ways that only have a minor impact on running time. The core of our approach is a gradient-domain `2-`p energy that models a sparse prior on reflectance gradients and a smooth prior on illumination. We show that the produced set of nonlinear equations can be solved very efficiently using look-up tables. Then, we provide scribbles to users to refine the decomposition. Our scribbles introduce local constraints in our optimization that add only a minimal overhead. Further, we extend these constraints to other similar image regions, thereby effectively enabling users to affect large regions with minimal effort. We also leverage multi-threading to precompute solutions a few frames ahead of the current one at a minimal cost. Coupled with the ability of our solver to use an initial guess to speed up convergence, this effectively shortens the computation time and offer a fast feedback to users. We demonstrate our approach on real sequences and show that we can obtain satisfying results with a reasonable amount of user interaction. We illustrate the benefits of our decomposition on video recoloring and shadow compositing.