\relax 
\citation{AllenTib10}
\citation{YL07}
\citation{ModelSel}
\citation{EstCovMatKron}
\citation{YL07}
\citation{ModelSel}
\citation{EstCovMatKron}
\citation{AllenTib10}
\citation{EstCovMatKron}
\@writefile{toc}{\contentsline {section}{\numberline {I}Introduction}{1}}
\citation{EstCovMatKron}
\citation{MIMOWerner}
\citation{AllenTib10}
\citation{LuZimmerman2}
\citation{LuZimmerman2}
\citation{EstCovMatKron}
\citation{YL07}
\citation{ModelSel}
\citation{ModelSel}
\citation{Glasso}
\citation{TimeVaryingGraphs}
\citation{Rothman}
\citation{RWRY08}
\newlabel{factorize}{{1}{2}}
\citation{Rothman}
\citation{TimeVaryingGraphs}
\citation{EstCovMatKron}
\citation{ConvexOpt}
\citation{ModelSel}
\citation{Glasso}
\citation{RWRY08}
\@writefile{toc}{\contentsline {section}{\numberline {II}Notation}{4}}
\newlabel{sec: notation}{{II}{4}}
\@writefile{toc}{\contentsline {section}{\numberline {III}Graphical Lasso Framework}{4}}
\newlabel{sec: glasso}{{III}{4}}
\newlabel{log_likelihood}{{2}{4}}
\citation{Glasso}
\citation{Rothman}
\citation{TimeVaryingGraphs}
\citation{EstCovMatKron}
\citation{EstCovMatKron}
\newlabel{opt_prob}{{3}{5}}
\newlabel{Glasso_rate}{{4}{5}}
\newlabel{naive_SCM_rate}{{5}{5}}
\@writefile{toc}{\contentsline {section}{\numberline {IV}Kronecker Graphical Lasso}{5}}
\newlabel{sec: algorithm}{{IV}{5}}
\newlabel{J_func_2}{{6}{5}}
\newlabel{A_update}{{7}{5}}
\newlabel{B_update}{{8}{5}}
\citation{AllenTib10}
\newlabel{J_lambda_func}{{9}{6}}
\@writefile{loa}{\contentsline {algorithm}{\numberline {1}{\ignorespaces Kronecker Graphical Lasso (KGlasso) }}{6}}
\newlabel{alg: algKGL}{{1}{6}}
\newlabel{G_operator}{{10}{6}}
\@writefile{toc}{\contentsline {section}{\numberline {V}Convergence of KGlasso Iterations}{6}}
\newlabel{sec: convergence_analysis_KGL}{{V}{6}}
\citation{ModelSel}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {V-A}}Block-Coordinate Reformulation of KGlasso}{7}}
\newlabel{dual_lemma}{{1}{7}}
\newlabel{dualY}{{11}{7}}
\newlabel{dualX}{{12}{7}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {V-B}}Limit Point Characterization of KGlasso}{7}}
\newlabel{convergence_theorem_critical}{{1}{7}}
\citation{TsiligkaridisTSP}
\citation{AllenTib10}
\citation{TsiligkaridisTSP}
\citation{EstCovMatKron}
\citation{EstCovMatKron}
\@writefile{toc}{\contentsline {section}{\numberline {VI}High Dimensional Consistency of FF}{8}}
\newlabel{sec: FF_rate}{{VI}{8}}
\newlabel{assumption_posdef_unif}{{1}{8}}
\newlabel{thm: FF_optimal_rate}{{2}{8}}
\newlabel{FF_rate_2}{{13}{8}}
\citation{Rothman}
\citation{ModelSel}
\citation{Rothman}
\citation{Rothman}
\citation{EstCovMatKron}
\@writefile{toc}{\contentsline {section}{\numberline {VII}High Dimensional Consistency of KGlasso}{9}}
\newlabel{sec: consistency}{{VII}{9}}
\newlabel{thm: KGL_optimal_rate}{{3}{9}}
\newlabel{KGL_perfect_rate}{{14}{9}}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces Regions of convergence for KGlasso (below upper curve), FF (below second highest curve), Glasso (below third highest curve), and standard sample covariance matrix estimator (SCM) (bottom curve). These regions are obtained from the analytical expressions in equations (14\hbox {}), (13\hbox {}), (4\hbox {}) and (5\hbox {}), respectively. The simulation shown in Fig. 6\hbox {} establishes that the FF algorithm indeed diverges when the parameters $p$ and $n$ fall inbetween the KGlasso and FF curves in the above figure.}}{10}}
\newlabel{fig: visRate}{{1}{10}}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {VII-A}}Discussion}{10}}
\citation{HsiehNIPS11}
\citation{HsiehNIPS11}
\@writefile{toc}{\contentsline {section}{\numberline {VIII}Simulation Results}{11}}
\newlabel{sec: simulations}{{VIII}{11}}
\citation{Rothman}
\citation{ModelSel}
\citation{EstCovMatKron}
\citation{ConvexOpt}
\citation{ConvexOpt}
\@writefile{toc}{\contentsline {subsection}{\numberline {\unhbox \voidb@x \hbox {VIII-A}}Empirical Rate Comparison}{12}}
\@writefile{toc}{\contentsline {section}{\numberline {IX}Conclusion}{12}}
\@writefile{toc}{\contentsline {section}{Appendix\nobreakspace  {}A: Proof of Lemma 1\hbox {}}{12}}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces Sparse Kronecker matrix representation. Left panel: left Kronecker factor. Right panel: right Kronecker factor. As the Kronecker-product covariance matrix is of dimension $10,000 \times 10,000$ standard Glasso is not practically implementable for this example.}}{13}}
\newlabel{fig: sim4_matrices}{{2}{13}}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces Normalized RMSE performance for precision matrix as a function of sample size $n$. KGlasso (Kronecker graphical lasso) uniformly outperforms FF (flip-flop) algorithm for all $n$. Here, $p=f=100$ and $N_{MC}=50$. The error bars are centered around the mean with $\pm $ one standard deviation. For $n=10$, there is a $72 \%$ RMSE reduction. }}{13}}
\newlabel{fig: sim4_frob_inv}{{3}{13}}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces Normalized RMSE performance for covariance matrix as a function of sample size $n$. KGlasso (Kronecker graphical lasso) uniformly outperforms FF (flip-flop) algorithm for all $n$. Here, $p=f=100$ and $N_{MC}=50$. The error bars are centered around the mean with $\pm $ one standard deviation. For $n=10$, there is a $49 \%$ RMSE reduction. }}{13}}
\newlabel{fig: sim4_frob_cov}{{4}{13}}
\@writefile{lof}{\contentsline {figure}{\numberline {5}{\ignorespaces  Precision Matrix MSE convergence as a function of sample size $n$ for FF and KGlasso. The dimensions of the Kronecker factor matrices grow as a function of $n$ as: $p(n)=f(n)=\delimiter "4264306 8 \cdot n^\alpha \delimiter "5265307 $. The true Kronecker factors were set to identity (so their inverses are fully sparse). The predicted MSE curves according to Thm. 2\hbox {} and Thm. 3\hbox {} are also shown. For both KGlasso and FF, the predicted MSE matches the empirical MSE well, thus verifying the rate expressions (13\hbox {}) and (14\hbox {}). }}{14}}
\newlabel{fig: KGlasso_FF_curves}{{5}{14}}
\@writefile{lof}{\contentsline {figure}{\numberline {6}{\ignorespaces  Precision Matrix MSE as a function of sample size $n$ for FF and KGlasso. The dimensions of the Kronecker factor matrices grow as a function of $n$ as: $p(n)=f(n)=\delimiter "4264306 n^{0.6} \delimiter "5265307 $. The true Kronecker factors were set to identity (so their inverses are fully sparse). The predicted MSE curves according to Thm. 2\hbox {} and Thm. 3\hbox {} are also shown. As predicted by our theory, and by the predicted convergent regions of $(n,p)$ for FF and KGlasso in Fig. 1\hbox {}, the MSE of the FF diverges while the MSE of the KGlasso converges as $n$ increases. }}{14}}
\newlabel{fig: KGlasso_FF_div_conv}{{6}{14}}
\citation{ConvexOpt}
\citation{ConvexOpt}
\citation{EstCovMatKron}
\citation{ModelSel}
\newlabel{saddle_ptY}{{15}{15}}
\newlabel{dualY_full}{{16}{15}}
\@writefile{toc}{\contentsline {section}{Appendix\nobreakspace  {}B: Lemma 2\hbox {}}{16}}
\newlabel{lemma: large_dev_Ted}{{2}{16}}
\newlabel{eq2}{{17}{17}}
\newlabel{eq_temp}{{18}{17}}
\citation{TsiligkaridisTSP}
\citation{IntroRealAnalysis}
\citation{TsiligkaridisTSP}
\newlabel{eq3}{{19}{18}}
\newlabel{sum_bound}{{20}{18}}
\newlabel{exp_bound}{{21}{18}}
\newlabel{upper_tail_2}{{22}{18}}
\citation{Rothman}
\citation{TimeVaryingGraphs}
\citation{EstCovMatKron}
\@writefile{toc}{\contentsline {section}{Appendix\nobreakspace  {}C: Proposition 1\hbox {}}{19}}
\newlabel{prop: Glasso_optimal_rate}{{1}{19}}
\@writefile{toc}{\contentsline {section}{Appendix\nobreakspace  {}D: Proof of Theorem 2\hbox {}}{19}}
\newlabel{FF_sufficient_condition}{{23}{19}}
\citation{LuZimmerman}
\citation{EstCovMatKron}
\citation{EstCovMatKron}
\newlabel{cond_0}{{24}{20}}
\newlabel{B_0_Frob1}{{25}{20}}
\newlabel{cond_1}{{26}{20}}
\newlabel{bound_Frob_spec}{{27}{20}}
\citation{EstCovMatKron}
\citation{TsiligkaridisTSP}
\citation{EstCovMatKron}
\citation{EstCovMatKron}
\newlabel{cond_2}{{28}{21}}
\newlabel{bound_mixed_norm2}{{29}{21}}
\newlabel{A_1_error2}{{30}{21}}
\newlabel{tilde_A_1_Frob_bound}{{31}{21}}
\newlabel{cond_3}{{32}{21}}
\newlabel{tilde_A_1_Frob2}{{33}{21}}
\newlabel{error_FF_2iter}{{34}{21}}
\citation{TsiligkaridisTSP}
\newlabel{tilde_R_FF_2}{{35}{22}}
\newlabel{X_2_Frob_error}{{36}{22}}
\newlabel{bound_Theta}{{37}{22}}
\citation{EstCovMatKron}
\citation{HornJohnson}
\@writefile{toc}{\contentsline {section}{Appendix\nobreakspace  {}E: Proof of Theorem 3\hbox {}}{23}}
\newlabel{condition_0}{{38}{23}}
\newlabel{tilde_B_0_rate}{{39}{23}}
\newlabel{Y_Frob_error}{{40}{23}}
\newlabel{grave_A_1}{{41}{23}}
\newlabel{mixed_norm_def}{{42}{23}}
\citation{TsiligkaridisTSP}
\newlabel{bound_infty}{{43}{24}}
\newlabel{grave_A_1_bound}{{44}{24}}
\newlabel{grave_A_1_ub}{{45}{24}}
\newlabel{X_Frob_error}{{46}{24}}
\citation{TsiligkaridisTSP}
\newlabel{Theta_bound}{{47}{25}}
\newlabel{B1_Frob_error}{{48}{25}}
\citation{TsiligkaridisTSP}
\bibstyle{IEEEtran}
\bibdata{myRefs}
\bibcite{AllenTib10}{1}
\bibcite{YL07}{2}
\bibcite{ModelSel}{3}
\bibcite{EstCovMatKron}{4}
\bibcite{MIMOWerner}{5}
\bibcite{LuZimmerman2}{6}
\bibcite{Glasso}{7}
\bibcite{TimeVaryingGraphs}{8}
\newlabel{A1_Frob_error}{{49}{26}}
\newlabel{Sigma_KGL_error}{{50}{26}}
\@writefile{toc}{\contentsline {section}{References}{26}}
\bibcite{Rothman}{9}
\bibcite{RWRY08}{10}
\bibcite{ConvexOpt}{11}
\bibcite{TsiligkaridisTSP}{12}
\bibcite{HsiehNIPS11}{13}
\bibcite{IntroRealAnalysis}{14}
\bibcite{LuZimmerman}{15}
\bibcite{HornJohnson}{16}
