In head and neck squamous cell carcinoma (HNSCC), mutations of p53 usually coexist with aberrant activation of NF-kappaB (NF-κB), other transcription factors and microRNAs, which promote tumor pathogenesis. However, how these factors and microRNAs interact to globally modulate gene expression and mediate oncogenesis is not fully understood. We devised a novel bioinformatics method to uncover interactive relationships between transcription factors or microRNAs and genes. This approach is based on matrix decomposition modeling under the joint constraints of sparseness and regulator-target connectivity, and able to integrate gene expression profiling and binding data of regulators. We employed this method to infer the gene regulatory networks in HNSCC. We found that the majority of the predicted p53 targets overlapped with those for NF-κB, suggesting that the two transcription factors exert a concerted modulation on regulatory programs in tumor cells. We further investigated the interrelationships of p53 and NF-κB with five additional transcription factors, AP1, CEBPB, EGR1, SP1 and STAT3, and microRNAs mir21 and mir34ac. The resulting gene networks indicate that interactions among NF-κB, p53, and the two miRNAs likely regulate progression of HNSCC. We experimentally validated our findings by determining expression of the predicted NF-κB and p53 target genes by siRNA knock down, and by examining p53 binding activity on promoters of predicted target genes in the tumor cell lines. Our results elucidating the cross-regulations among NF-κB, p53, and microRNAs provide insights into the complex regulatory mechanisms underlying HNSCC, and shows an efficient approach to inferring gene regulatory programs in biological complex systems.