This paper introduces the Coupled Temporal Deep Belief Network (CTDBN), a novel architecture for financial market prediction with three principal theoretical contributions. First, we develop a sparse coupling learning algorithm with provable recovery guarantees: under a market incoherence condition, our group-lasso formulation recovers the true cross-market dependency structure with high probability. Second, we introduce regime-aware coupling that models time-varying dependency strength through a hidden Markov layer, enabling automatic detection of crisis periods when markets become tightly coupled. We prove that the associated EM algorithm converges to a stationary point of the marginal likelihood. Third, we derive a variational lower bound for inference in coupled temporal models and prove that the mean-field approximation achieves a multiplicative (1-ε) factor of the true likelihood under bounded coupling strength. The framework integrates four data channels: market indices, economic indicators, social media sentiment via convolutional networks over financial word embeddings, and video news features. Experiments on S&P 500, FTSE 100, Nikkei 225, and major currency pairs demonstrate 64.7% directional accuracy (11% improvement over baselines), with the regime-switching component providing additional 3.2% gains during the 2011 European debt crisis period. The sparse coupling algorithm identifies economically meaningful lead-lag relationships, recovering known patterns such as the S&P 500 leading European indices.