Accurate tracking of cyclic human motion in video data helps in developing computer-aided applications such as gait analysis, visual surveillance, patient rehabilitation, etc. This paper presents a novel technique for tracking cyclic human motion based on decomposing complex cyclic motion into components and maintaining coupling between components. The decomposition reduces the demensionality of the problem and enables a graphical modeling of the articulated human body. The coupling between components is modeled by their phase relationship and represented as directed edges in Bayesian networks and undirected edges in Markov random fields. Such coupling is maintained in tracking through Ancestral Simulation (AS) and Markov potentials in a Sequential Monte Carlo tracking framework. We show that the approach handles severe self-occlusion and foreign body occlusion with improved accuracy and efficiency.