% ==== Document Class & Packages =====


\documentclass[12pt,hidelinks]{article}
\usepackage[explicit]{titlesec}
\usepackage{titletoc}
\usepackage{tocloft}
\usepackage{charter}
\usepackage[many]{tcolorbox}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{tikz,lipsum,lmodern}
\usetikzlibrary{calc}
\usepackage[english]{babel}
\usepackage{fancyhdr}
\usepackage{mathrsfs}
\usepackage{empheq}
\usepackage{fourier}% change to lmodern if fourier is no available
\usepackage{wrapfig}
\usepackage{fancyref}
\usepackage{hyperref}
\usepackage{cleveref}
\usepackage{listings}
\usepackage{varwidth}
\usepackage{longfbox}
\usepackage{geometry}
\usepackage{marginnote}
\usepackage{pifont}

\usepackage[font=footnotesize]{caption}
\usepackage{multicol}

\usepackage{minted}
\makeatletter
\renewcommand{\MintedPygmentize}{/usr/bin/pygmentize}
% The path "/opt/homebrew/bin/pygmentize" is an example and should be replaced with the actual path to the 'pygmentize' executable on your system. The 'pygmentize' command is part of the Pygments package, which is required by the 'minted' package for syntax highlighting in LaTeX documents. On macOS, Pygments can be installed using Homebrew with the command: 'brew install pygments'. After installing Pygments, you can determine the path to 'pygmentize' by executing 'which pygmentize' in the terminal.
\makeatother

\hypersetup{
	colorlinks,
	linkcolor={red},
	citecolor={red},
	urlcolor ={cyan},
linktoc=none% <- no links in ToC
}



\begin{filecontents}{locref.bib}

@inproceedings{QUIC,
 author = {Hsieh, Cho-Jui and Dhillon, Inderjit and Ravikumar, Pradeep and Sustik, M\'{a}ty\'{a}s},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {J. Shawe-Taylor and R. Zemel and P. Bartlett and F. Pereira and K. Q. Weinberger},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Sparse Inverse Covariance Matrix Estimation Using Quadratic Approximation},
 note = {URL: \url{https://proceedings.neurips.cc/paper/2011/hash/2ba8698b79439589fdd2b0f7218d8b07-Abstract.html}},
 volume = {24},
 year = {2011}
}

@article{SQUIC_BLOCK,
title = {Block-Enhanced Precision Matrix Estimation for Large-Scale Datasets},
journal = {Journal of Computational Science},
pages = {101389},
year = {2021},
issn = {1877-7503},
note = {URL: \url{https://doi.org/10.1016/j.jocs.2021.101389}},
url_ignore = {https://www.sciencedirect.com/science/article/pii/S1877750321000776},
author = {Aryan Eftekhari and Dimosthenis Pasadakis and Matthias Bollh\"{o}fer and Simon Scheidegger and Olaf Schenk},
keywords = {Covariance matrices, Graphical model, optimization, Gaussian Markov random field, machine learning application}
}

@inproceedings{SQUIC_PRL,
author = {Eftekhari, Aryan and Bollh\"{o}fer, Matthias and Schenk, Olaf},
title = {{Distributed Memory Sparse Inverse Covariance Matrix Estimation on High-Performance Computing Architectures}},
year = {2018},
publisher = {IEEE Press},
booktitle = {Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis},
articleno = {20},
numpages = {12},
keywords = {sparse matrices, high-performance computing, inverse covariance matrix, approximate matrix inverse},
location = {Dallas, Texas},
series = {SC '18},
note={URL: \url{http://doi.org/10.1109/SC.2018.00023}}
}

@manual{SQUIC_MAN,
 author = {Aryan Eftekhari and Lisa Gaedke-Merzh\"{a}user and Dimosthenis Pasadakis and Matthias Bollh\"{o}fer and Simon Scheidegger and Olaf Schenk},
 month = {November},
 title = {SQUIC:Software Package for Sparse Precision Matrix Estimation, User Guide},
 edition = {1.0},
 url = {URL: \url{https://www.gitlab.ci.inf.usi.ch/SQUIC/gitlab-profile/-/raw/main/SQUIC_User_Manual.pdf}},
 year = 2023
}

@article{SQUIC_TOMS,
 author = {Aryan Eftekhari and Lisa Gaedke-Merzh\"{a}user and Dimosthenis Pasadakis and Matthias Bollh\"{o}fer and Simon Scheidegger and Olaf Schenk},
 title   ={Sparse Precision Matrix Estimation With {SQUIC}},
 journal ={Under Review},
 year    =2023
}

@article{SQUIC_BASE,
author={Bollh\"{o}fer, Matthias and Eftekhari, Aryan and Scheidegger, Simon and Schenk, Olaf},
title = {Large-Scale {S}parse {I}nverse {C}ovariance {M}atrix {E}stimation},
journal = {SIAM Journal on Scientific Computing},
volume = 41,
number = 1,
pages = {A380-A401},
year = 2019,
doi_ignore = {10.1137/17M1147615},
note= {URL: \url{https://doi.org/10.1137/17M1147615}}
} 
\end{filecontents} 


\definecolor{bg}{RGB}{240, 240, 235}
\setminted[bash]{
    breaklines=true,
    mathescape=true,
    fontsize=\footnotesize,
    numberblanklines=false,
    frame=leftline,
    framerule=0.8pt,
    style=tango,
    bgcolor=bg
    }

\setminted[python]{
    breaklines=true,
    mathescape=true,
    fontsize=\footnotesize,
    numberblanklines=false,
    frame=leftline,
    framerule=0.8pt,
    style=tango,
    bgcolor=bg
    }

\setminted[R]{
    breaklines=true,
    mathescape=true,
    fontsize=\footnotesize,
    numberblanklines=false,
    frame=leftline,
    framerule=0.8pt,
    style=tango,
    bgcolor=bg
    }

\setminted[text]{
    breaklines=true,
    mathescape=true,
    fontsize=\footnotesize,
    numberblanklines=false,
    frame=leftline,
    framerule=0.8pt,
    style=tango,
    bgcolor=bg
    }

\geometry{a4paper,left=28mm, right=28mm, top=28mm, bottom=28mm}

\setlength{\parindent}{0pt}
\addto{\captionsenglish}{\renewcommand*{\contentsname}{Table of Contents}}
\linespread{1.2}

\newcommand{\code}[1]{\texttt{#1}}
\newcommand{\expnum}[2]{
\ifnum#1=1 
  10^{#2} 
\else 
  #1 \! \cdot \! 10^{#2}
\fi
}

\newcommand{\bb}[1]{\boldsymbol{\mathbf{#1}}}
\newcommand{\bbh}[1]{\widehat{\boldsymbol{\mathbf{#1}}}}
\newcommand{\argmin}[1]{\underset{#1}{\text{argmin}} }
\newcommand{\argmax}[2]{\underset{#1}{\text{arg~max}} \; #2 }


\begin{document}
\begin{titlepage}
% ===================
%	Title Section 	
% ===================
\vspace*{1.5\baselineskip}
\Huge{\textsc{SQUIC}}\\
\normalsize{\textsc{Software for Sparse Precision Matrix Estimation}}\\
\rule{\textwidth}{0.5em}\vspace{1em} % Thick horizontal rule
%
\Large{\textbf{User Manual}}\\
\normalsize{Version 1.0 }\\
\normalsize{November 20, 2023}\\
% =================
%	Information	
% =================
\vfill
\centering 
\textsc{\small 
Aryan Eftekhari |
Lisa Gaedke-Merzh\"{a}user |
Dimosthenis Pasadakis \newline
Matthias Bollh\"{o}fer |
Simon Scheidegger |
Olaf Schenk 
}
\end{titlepage}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\tableofcontents
\vfill
\small{\noindent \textbf{About this document} \vspace{-3mm}\\
\noindent \rule{4.2cm}{0.5pt} \\
This file is intended as a user manual for the ACM TOMS software package submission.
}
\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}\label{sec:1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
\begin{figure}[b!]
	\center
    \includegraphics[width=.99\linewidth]{f1.pdf}
    \caption{
A visualization of the SQUIC package which includes the main inputs $\bb{Y}$ and $\bb{\Lambda}$, as well as the outputs $\bbh{\Theta}$ and $\bbh{\Theta}^{\text{inv}}$, corresponding to the data matrix, matrix tuning parameter, estimated precision matrix and its sparse approximate inverse, respectively.
%
Note that we can set $\bb{\Lambda}_{ij} = \lambda$ for all its entries, where $\lambda$ is the scalar tuning parameter; see \eqref{eq:Matrix_sparsity} for details.
%
Also shown are the main computational components, which include the upfront sparse sample covariance matrix computation (blue), alongside the Newton iteration (red), which includes block coordinating descent, supernodal Cholesky factorization, and block approximate matrix inversion.
%
Shared-memory parallel components are marked with an ``*''.
}
\label{fig:1} 
\end{figure}%
%
This software is an implementation of the \textbf{S}parse~\textbf{QU}adratic approximation~of~\textbf{I}nverse \textbf{C}ovariance matrix (SQUIC) algorithm~\cite{SQUIC_TOMS}, a second-order method designed for the solving $\ell_1$-regularized Gaussian maximum likelihood problem. 
%
Based on the foundational work of~\cite{QUIC}, this algorithm is developed for large-scale, and performance-oriented sparse inverse covariance or precision matrix estimation.
%
This user manual serves as a resource for the~SQUIC package and its interfaces.

\vspace{1em}
For the dataset $\bb{Y} \in \mathbb{R}^{p \times n}$, consisting of $p$ random variables and $n$ samples, SQUIC computes a sparse estimate of the precision matrix and its sparse approximate inverse, denoted as $\bbh{\Theta}$ and $\bbh{\Theta}^{\text{inv}}$, respectively.
%
The estimation process employs a \emph{matrix tuning parameter} $\bb{\Lambda} \in \mathbb{R}^{p \times p}$, which is indirectly defined using $\bb{M} \in \mathbb{R}^{p \times p}$ and a \emph{scalar tuning parameter} $\lambda > 0$.
%
This relationship is summarized as follows:
%
\begin{align} \label{eq:Matrix_sparsity}
	\bb{\Lambda}_{ij} : =  
	\left\{ 
	\begin{array}{rcl}
		\bb{M}_{ij}, & \mbox{if \; $\bb{M}_{ij} \neq 0$,}  \\ 
		\lambda      & \mbox{otherwise.}\\
	\end{array}
	\right.
\end{align}
% 
In many cases, it is appropriate to define the nonzero entries of $\bb{M}$ as constants, such that, for example, for $\eta \in (0,\lambda]$, $\bb{M}_{ij}=\eta$ for all its nonzero entries.
%
The larger the value of $\bb{\Lambda}_{ij}$, the more the corresponding value $\bbh{\Theta}_{ij}$ is penalized for being nonzero.
%
If $\bb{M}$ is not specified and only the scalar tuning parameter $\lambda$ is specified, we set $\bb{\Lambda}_{ij}=\lambda$ for all its entries.
%
In Figure~\ref{fig:1}, we visualize the main inputs and outputs of SQUIC, alongside its primary computational components.

\vspace{1em}
The source code for the software described in this manuscript is available under general public licenses (GPL $3$). % at~\href{http://www.gitlab.ci.inf.usi.ch/SQUIC}{www.gitlab.ci.inf.usi.ch/SQUIC}. 
%
The software is packaged as~\code{libSQUIC} and intended for use on Linux and Mac systems (both X86 and ARM architectures).
%
It is written in {C++}, parallelized with {OpenMP}, and features interface packages for {R} and {Python}.
%
This codebase incorporates the SQUIC algorithm from~\cite{SQUIC_BASE}, along with parallel and blocking components in~\cite{SQUIC_PRL} and~\cite{SQUIC_BLOCK}, respectively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
\section{Compiling and Installation} \label{sec:2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
The source code for the SQUIC library is located in \code{Src/lib}. 
%
This section provides instructions for compiling and installing the \code{libSQUIC} shared library, along with its R and Python interfaces.
%
The necessary external packages for compilation include:
%
\begin{multicols}{2} 
\begin{itemize}
    \item \textcolor{black}{BLAS, LAPACK,} and OpenMP
    \item C/C++/Fortran compilers and \textcolor{black}{Cmake}
\end{itemize}
\end{multicols}
%
\textcolor{black}{
Mac users are recommended to use Homebrew to install the GNU Fortran compilers, OpenMP, and Cmake by running \mintinline{bash}{brew install gcc libomp cmake}.
%
The default Mac distribution includes both the C/C++ compilers and the BLAS/LAPACK libraries.
%
Linux users can install necessary packages with their system's package manager. 
%
For example, on Ubuntu, this is done using the command \mintinline{bash}{sudo apt-get install build-essential libblas-dev liblapack-dev cmake}.}~\footnote{\textcolor{black}{If different types of BLAS or LAPACK are used, the \code{LDFLAGS} in \code{Src/lib/makefile} must be adjusted accordingly.}
%
To use Intel Math Kernel Library (MKL), set the \code{\$MKLROOT} environment variable by executing \mintinline{bash}{source /opt/intel/oneapi/mkl/latest/env/vars.sh intel64} (note: this command may vary based on your MKL version). 
%
Then, adjust your compiler and linker flags according to your system. For specific flag details, refer to the \href{https://www.intel.com/content/www/us/en/developer/tools/oneapi/onemkl-link-line-advisor.html}{Intel MKL Link Line Advisor}.
} 
%} 
%

\vspace{1em}
\textcolor{black}{The R interface library dependencies include ~\code{Matrix},~\code{Rcpp} and \code{RcppArmadillo}, and the Python interface dependencies include the~\code{pip3} package manager,~\code{NumPy} and~\code{SciPy}. 
%
Note that, with the exception of \code{pip3}, which is included with Python version 3, all dependencies for both R and Python are automatically installed as part of the setup process described below.
}
%

\begin{itemize}
    \itemsep0em 
    \item[\ding{182}] Navigate to the \code{Src/lib} directory within the source code to compile \code{CHOLMOD}, its dependencies, and \code{libSQUIC}.
    %
    To complete the process, execute the following commands:
%    
    \begin{minted}{bash}
cd Src/lib
make
    \end{minted}
    \item[\ding{183}] Install \code{libSQUIC} in the default \code{\textasciitilde/} directory.
    \begin{minted}{bash}
make install   
    \end{minted}
%
    \item[\ding{184}] Install the {R} and {Python} interface packages (discussed in further detail in Sections~\ref{sec:3} and~\ref{sec:4}), and run a simple test for each.
    %
    \textcolor{black}{By default, the interface packages are installed in a local user directory. 
    %
    For R, this is \code{\textasciitilde/R}, and for Python, it's the platform-specific user install directory (see, \mintinline{bash}{pip3 help} 
    \code{-{}-user} flag for details).}\footnote{\textcolor{black}{If you wish to perform a global installation of the R and Python packages (which may require root access), use, e.g., the command  \mintinline{bash}{make install_r R_PYTHON_INTERFACE_GLOBAL_INSTALL=true}.}}
    \begin{minted}{bash}
make install_r   
make install_py
    \end{minted}
\end{itemize}
% Install to the Python user install directory for your platform.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\section{SQUIC for {R}}\label{sec:3}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The {R} interface is located at \code{Src/r}. 
%
\textcolor{black}{The installation procedure of \code{libSQUIC}, as outlined in Section~\ref{sec:2}, automatically installs R interface package and required dependencies.}
%
The user can manually install or reinstall the interface package by following these steps:
%
\begin{itemize}
    \itemsep0em 
    \item[\ding{182}] Install~\code{libSQUIC} in the recommended home directory, i.e., \code{\textasciitilde/}. 
    \item[\ding{183}] \textcolor{black}{Install dependencies ~\code{Matrix},~\code{Rcpp} and \code{RcppArmadillo} from the R command-line using}
            \begin{minted}{R}
install.packages(c('Matrix','Rcpp', 'RcppArmadillo'))
        \end{minted}
        \vspace{-3em}
    \item[\ding{184}] Install the library from the R command-line using
        \begin{minted}{R}
install.packages('Src/r', repos = NULL, type = 'source')
        \end{minted}
                \vspace{-3em}
\end{itemize}
%
The environment variable \code{SQUIC\_LIB\_PATH} defines the location of \code{libSQUIC}. 
%
If this variable is not set, then the default location of \code{libSQUIC} is \code{\textasciitilde/}.
%
To change the default location, in {R} use the command \mintinline{R}{Sys.setenv(SQUIC_LIB_PATH="/path/to/squic/")}, replacing \code{/path/to/squic} with the path of where \code{libSQUIC} can be found.
%
\textcolor{black}{If you do not have root access you will be prompted for a local installation of SQUIC, along with any required dependencies}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{List of variables}\label{sec:3.1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The \mintinline{R}{SQUIC()} function call serves as the interface function for \texttt{libSQUIC}, invoking the SQUIC algorithm for sparse precision matrix estimation.
%
The list of input and output variables is shown below and can also be viewed via the help command \mintinline{R}{help(SQUIC)}.
%
\begin{minted}{R}
out1 <- SQUIC(Y,lambda,max_iter,tol,tol_inv,verbose,M,X0,W0);
out2 <- SQUIC(Y,lambda,max_iter = 0,tol,verbose,M)
\end{minted}
%
All sparse matrix formats utilize the standard \code{Matrix} package.
%
        \vspace{-1em}
\paragraph{Inputs}
\begin{itemize}
\itemsep-0.5em 
	\item[-] \mintinline{R}{Y}         : Input data matrix ($p \times n$ dense matrix).
	\item[-] \mintinline{R}{lambda}    : Scalar tuning parameter a nonzero positive number.
	\item[-] \mintinline{R}{max_iter}   [default $100$]: Maximum number of Newton iterations\footnote{\label{fn:max_iter}Setting \mintinline{R}{max_iter=0} will return the \emph{sparse (thresholded) sample covariance matrix}.}
	\item[-] \mintinline{R}{tol}        [default $\expnum{1}{-3}$]: Tolerance for convergence.
 	\item[-] \mintinline{R}{tol_inv}    [default $\expnum{1}{-4}$]: Tolerance for approximate matrix inversion.
	\item[-] \mintinline{R}{verbose}    [default $1$]: Verbosity level as $0$ or $1$. 
	\item[-] \mintinline{R}{M}          [default \mintinline{R}{NULL}]: Symmetric sparse matrix ($ p \times p$ sparse matrix).\footnote{\label{fn:M}
    We define $\bb{\Lambda}_{ij}=\bb{M}_{ij}$ if $\bb{M}_{ij} \neq 0$ and $\bb{\Lambda}_{ij}=\lambda$, if otherwise.
    %
    When \mintinline{R}{M=NULL} (or \mintinline{python}{None} in {Python}), we default to the, so called, ``scalar-tuning parameter'' for which $\bb{\Lambda}_{ij}=\lambda$.	
    } 
	\item[-] \mintinline{R}{X0}        [default \mintinline{R}{NULL}]: Initial value of precision matrix ($ p \times p$ sparse matrix).\footnote{ \label{fn:X0}If either \mintinline{R}{X0} or \mintinline{R}{W0} is set to \mintinline{R}{NULL} (or \mintinline{python}{None} in {Python}), both \mintinline{R}{X0} and \mintinline{R}{W0} are set to identity.}
	\item[-] \mintinline{R}{W0}        [default \mintinline{R}{NULL}]: Initial value of inverse precision matrix ($ p \times p$ sparse matrix).\footref{fn:X0}
\end{itemize}

\paragraph{Outputs}
\begin{itemize}
\itemsep-0.5em 
	\item[-] \mintinline{R}{out1$X}: Estimated precision matrix ($ p \times p$ sparse matrix).
	\item[-] \mintinline{R}{out1$W}: Sparse approximate inverse of the precision matrix ($ p \times p$ sparse matrix).
	\item[-] \mintinline{R}{out1$info_time_total}: Total runtime. 
	\item[-] \mintinline{R}{out1$info_time_sample_cov}: Runtime of the sample covariance matrix. 
	\item[-] \mintinline{R}{out1$info_time_optimize}: Runtime of the Newton steps.
	\item[-] \mintinline{R}{out1$info_time_factor} : Runtime of matrix factorization.
	\item[-] \mintinline{R}{out1$info_time_approximate_inv}: Runtime of approximate matrix inversion.
	\item[-] \mintinline{R}{out1$info_time_coordinate_upd}: Runtime of coordinate descent update.
	\item[-] \mintinline{R}{out1$info_objective}: Objective value at each Newton iteration.
	\item[-] \mintinline{R}{out1$info_logdetX}: Log determinant of the estimated precision matrix.
	\item[-] \mintinline{R}{out1$info_trSX}: Trace of sample cov. times the estimated precision matrix.
    \item[]
	\item[-] \mintinline{R}{out2$S}: Sparse sample covariance matrix ($ p \times p$  sparse matrix).
	\item[-] \mintinline{R}{out2$info_time_total}: Total runtime.  	
	\item[-] \mintinline{R}{out2$info_time_sample_cov}: Runtime of the sample covariance matrix. 
\end{itemize}


% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \subsection{Installation}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Usage} \label{sec:2.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In the basic example outlined below, we will use SQUIC to estimate the precision matrix of a synthetically generated dataset with correlated random variables, where the true precision matrix is tridiagonal.
%
\footnote{\label{fn:round_off}
There may be slight variations in the results across different machines due to \emph{round-off errors}
%
These differences are visible in the sparse approximation of the estimated inverse of the precision matrix \code{W} and are associated with the specific permutation used by the underlying matrix factorization routine, which are not related to the random seed for data generation.
}
%
\begin{minted}{R}
library(Matrix)
library(SQUIC)
    
# basic test parameters
p       <- 1024
n       <- 100
lambda  <- .4

# generate a tridiagonal matrix &  dataset
set.seed(1)
iC_star <- Matrix::bandSparse(p, p, (-1):1, list(rep(-.5, p-1), rep(1.25, p), rep(-.5, p-1)));
z       <- replicate(n,rnorm(p))
iC_L    <- chol(iC_star)
Y       <- matrix(solve(iC_L,z),p,n)

# run SQUIC
out <- SQUIC(Y,lambda)   
\end{minted}

With the default verbosity level the output is as shown below.\footnote{
In {R} notebooks the verbose output may not be visible from within the notebook (see, e.g., \href{https://github.com/IRkernel/IRkernel/issues/416}{here}). 
%
This issue is not present when using the terminal or RStudio, and it does not affect the results.}
%
\begin{minted}{text}
----------------------------------------------------------------
                     SQUIC Version 1.0                         
----------------------------------------------------------------
Input Matrices
 nnz(X0)/p:   1.000000e+00
 nnz(W0)/p:   1.000000e+00
 nnz(M)/p:    ignored
 Y:           1024 x 100 
Runtime Configs   
 Sample Cov.:   Deterministic
 CordDec Vers:  Collective coordinate descent update 
 Inversion:     Approx. block Neumann series
 Fact. Routine: CHOLMOD
Parameters       
 verbose:     1 
 lambda:      4.000000e-01 
 max_iter:    100 
 term_tol:    1.000000e-03 
 inv_tol:     1.000000e-04 
 threads:     12 
#SQUIC Started 
* sample covariance matrix S: time=2.36e-03 nnz(S)/p=6.91e+00
* iter=1 time=4.89e-03 obj=1.60e+03 |delta(obj)|/obj=1.56e-01 nnz(X,L,W)/p=
    [6.91e+00 7.54e+01 1.69e+00] lns_iter=3 
* iter=2 time=7.23e-03 obj=1.56e+03 |delta(obj)|/obj=3.13e-02 nnz(X,L,W)/p=
    [6.91e+00 7.54e+01 5.75e+01] lns_iter=2 
* iter=3 time=3.19e-02 obj=1.55e+03 |delta(obj)|/obj=6.62e-03 nnz(X,L,W)/p=
    [6.91e+00 7.54e+01 5.78e+01] lns_iter=1 
* iter=4 time=3.06e-02 obj=1.54e+03 |delta(obj)|/obj=2.71e-04 nnz(X,L,W)/p=
    [6.91e+00 7.54e+01 9.01e+01] lns_iter=1 
#SQUIC Finished: time=8.60e-02 nnz(X,W)/p=[6.91e+00 9.01e+01] 
\end{minted}
%
Input details are provided under ``Input Matrices'', where \code{X0} and \code{W0} denote the initial values of the precision matrix and its inverse (defaulting to identity matrices). 
%
The absence of \code{M} is noted, and the size of the input data \code{Y} is specified as $p=1024$, $n=100$.
%
In the ``Runtime Configs'' section, key computational operations are summarized. 
%
The ``Parameters'' section lists parameters used in the overall optimization procedure, where the maximum number of threads available on the system is automatically utilized.
%
Here \code{iter}, \code{nnz}, and \code{lns\_iter} represent the Newton iteration index, number of nonzeros, and the number of line-search iterations, respectively.
%
For instance, \code{nnz(X,L,W)/p} indicates the number of nonzeros per row for the precision matrix, its Cholesky factor, and the sparse approximate inverse, respectively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{SQUIC for {Python}} \label{sec:4}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The {Python} (V3) interface for SQUIC is located at \code{Src/python}. 
%
\textcolor{black}{The installation of \code{libSQUIC} detailed in Section~\ref{sec:2}, automatically installs the Python interface package and required dependencies using the \code{pip3} package manager, which is bundled with Python.}
%
The user can manually install or reinstall the interface package by following these steps:
%
\begin{itemize}
    \item[\ding{182}] Install~\code{libSQUIC} in the recommended home directory, i.e., \code{\textasciitilde/}.
    \item[\ding{183}] \textcolor{black}{Install dependencies ~\code{NumPy},and \code{SciPy} using \code{pip3} form the command-line}
        \begin{minted}{bash}
pip3 install numpy scipy --user
        \end{minted}
        \vspace{-3em}
    \item[\ding{184}] Install the interface package using \code{pip3} form the command-line. 
        \begin{minted}{bash}
pip3 install Src/python --user
        \end{minted}
            \vspace{-3em}
\end{itemize}
%
Use \mintinline{bash}{export SQUIC_LIB_PATH=/path/to/squic/}, replacing \code{/path/to/squic/} with the path of where \code{libSQUIC} can be found.
%
If this variable is not set, the default location of~\code{libSQUIC} is \code{\textasciitilde/}.
%
\textcolor{black}{Use \mintinline{bash}{pip3 install Src/python} for a global installation of the Python interface}. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{List of variables}\label{sec:4.1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
The \mintinline{python}{squic.run()} function call serves as the {Python} interface function for the \texttt{libSQUIC}, invoking the SQUIC algorithm for sparse precision matrix estimation.
%
The list of input and output variables is shown below and can also be viewed via the help command \mintinline{python}{help(squic)}.
%
The description of the function here is exactly the same as the {R} interface discussed in Section~\ref{sec:3}.
%
The sole difference between the input variable of the {R} and {Python} interface is that \code{lambda} is a reserved keyword in {Python}, so \code{l} is used instead.
%
For completeness, the input and output variable descriptions are provided below.

\begin{minted}{python}
out1 = squic.run(Y,l,max_iter,tol,tol_inv,verbose,M,X0,W0);
out2 = squic.run(Y,l,max_iter = 0,tol,verbose,M);
\end{minted}
%
All sparse matrix formats utilize the \code{scipy} package.
%
\paragraph{Inputs}
\begin{itemize}
\itemsep-0.5em 
	\item[-] \mintinline{python}{Y}        :Input data matrix ($p \times n$ dense matrix).
	\item[-] \mintinline{python}{l}        : Scalar tuning parameter a nonzero positive number.
	\item[-] \mintinline{python}{max_iter}  [default $100$]: Maximum number of Newton iterations.\footref{fn:max_iter}
	\item[-] \mintinline{python}{tol}       [default $\expnum{1}{-3}$]: Tolerance for convergence.
 	\item[-] \mintinline{python}{tol_inv}    [default $\expnum{1}{-4}$]: Tolerance for approximate matrix inversion.
	\item[-] \mintinline{python}{verbose}   [default $1$]: Verbosity level as $0$ or $1$. 
	\item[-] \mintinline{python}{M}         [default \mintinline{python}{None}]: Symmetric sparse matrix ($ p \times p$ sparse matrix)..\footref{fn:M}
	\item[-] \mintinline{python}{X0}        [default \mintinline{python}{None}]: Initial value of precision matrix ($ p \times p$ sparse matrix).\footref{fn:X0}
	\item[-] \mintinline{python}{W0}        [default \mintinline{python}{None}]: Initial value of inverse precision matrix ($ p \times p$ sparse matrix).\footref{fn:X0}
\end{itemize}


\paragraph{Outputs}
\begin{itemize}
\itemsep-0.5em 
	\item[-] \mintinline{python}{out1[0]} : Estimated precision matrix ($ p \times p$  sparse matrix) .
	\item[-] \mintinline{python}{out1[1]} : Sparse approximate inverse of the precision matrix ($ p \times p$ sparse matrix).
	\item[-] \mintinline{python}{out1[2]} : List of different component runtimes.
	\begin{itemize}
        \itemsep-0.5em
    	\item[-] \mintinline{python}{out1[2][0]} : Total runtime. 
    	\item[-] \mintinline{python}{out1[2][1]} : Runtime of the sample covariance matrix. 
    	\item[-] \mintinline{python}{out1[2][2]} : Runtime of the Newton steps.
    	\item[-] \mintinline{python}{out1[2][3]} : Runtime of matrix factorization.
    	\item[-] \mintinline{python}{out1[2][4]} : Runtime of approximate matrix inversion.
    	\item[-] \mintinline{python}{out1[2][5]} : Runtime of coordinate descent update.
    \end{itemize}
	\item[-] \mintinline{python}{out1[3]}: Objective value at each Newton iteration.
	\item[-] \mintinline{python}{out1[4]} : Log determinant of the estimated precision matrix..
	\item[-] \mintinline{python}{out1[5]} : Trace of sample covariance matrix times the estimated precision matrix.		
    \item[] 
	\item[-] \mintinline{python}{out2[1]}   : Sparse sample covariance matrix ($ p \times p$  sparse matrix) .
	\item[-] \mintinline{python}{out2[2]} : List of different compute times.
	\begin{itemize}
        \itemsep-0.5em
    	\item[-] \mintinline{python}{out2[2][0]} : Total runtime. 
    	\item[-] \mintinline{python}{out2[2][1]} : Runtime of the sample covariance matrix. 
    \end{itemize}	
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Usage} \label{sec:3.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In the basic example outlined below, we will use SQUIC to estimate the precision matrix of a synthetically generated dataset with correlated random variables, where the true precision matrix is tridiagonal.\footref{fn:round_off}
%
\begin{minted}{python}
import numpy as np
import squic

# basic test parameters
p = 1024
n = 100
l = .4
# generate a tridiagonal matrix &  dataset
np.random.seed(1)
a = -0.5 * np.ones(p-1)
b = 1.25 * np.ones(p)
iC_star = np.diag(a,-1) + np.diag(b,0) + np.diag(a,1)
L = np.linalg.cholesky(iC_star)
Y = np.linalg.solve(L.T,np.random.randn(p,n))
# run SQUIC
[X,W,info_times,info_objective,info_logdetX,info_trSX] = squic.run(Y,l)
\end{minted}

Using the default verbosity level the output is as shown below.
%
This output differs compared to the {R} example in Section~\ref{sec:3}, as the generated random data differs.
%
With this said, reruns of the same script, using the same random seed, will result in the same results.
%
\begin{minted}{text}
----------------------------------------------------------------
                     SQUIC Version 1.0                         
----------------------------------------------------------------
Input Matrices
 nnz(X0)/p:   1.000000e+00
 nnz(W0)/p:   1.000000e+00
 nnz(M)/p:    ignored
 Y:           1024 x 100 
Runtime Configs   
 Sample Cov.:   Deterministic
 CordDec Vers:  Collective coordinate descent update 
 Inversion:     Approx. block Neumann series
 Fact. Routine: CHOLMOD
Parameters       
 verbose:     1 
 lambda:      4.000000e-01 
 max_iter:    100 
 term_tol:    1.000000e-03 
 inv_tol:     1.000000e-04 
 threads:     12 

#SQUIC Started 
* sample covariance matrix S: time=1.91e-02 nnz(S)/p=6.49e+00
* iter=1 time=4.34e-02 obj=1.60e+03 |delta(obj)|/obj=1.60e-01 nnz(X,L,W)/p=
    [6.49e+00 6.61e+01 1.67e+00] lns_iter=3 
* iter=2 time=6.63e-02 obj=1.55e+03 |delta(obj)|/obj=3.11e-02 nnz(X,L,W)/p=
    [6.49e+00 6.61e+01 5.30e+01] lns_iter=2 
* iter=3 time=4.80e-02 obj=1.54e+03 |delta(obj)|/obj=6.42e-03 nnz(X,L,W)/p=
    [6.49e+00 6.61e+01 5.29e+01] lns_iter=1 
* iter=4 time=4.44e-02 obj=1.54e+03 |delta(obj)|/obj=2.53e-04 nnz(X,L,W)/p=
    [6.49e+00 6.61e+01 8.24e+01] lns_iter=1 
#SQUIC Finished: time=2.39e-01 nnz(X,W)/p=[6.49e+00 8.24e+01] 
\end{minted}
%
Note that the verbose output of~\code{libSQUIC} is not visible in notebooks; but it does not affect the results.\footnote{This is a known issue; see, e.g., \href{https://pypi.org/project/wurlitzer}{pypi.org/project/wurlitzer} for details.}
%
This issue does not occur when using~{Python} in a non-notebook environment.
%
By using the \code{wurlitzer} package, we can sidestep this issue with the following lines of code before the \mintinline{python}{squic.run} notebook function call.
%
\begin{minted}{python}
!pip install wurlitzer
%load_ext wurlitzer
\end{minted}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Numerical Tests}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Experiments validating the performance and accuracy of the SQUIC algorithm, as well as its comparison with similar packages, are located in \code{/Replication}.
%
The five experiments include assessments of the sparse approximate matrix inversion routine (\code{test\_inv.R}), evaluations of accuracy using the scalar tuning parameter (\code{test\_scal\_acc.R}), matrix tuning parameter (\code{test\_mat\_acc.R}), performance analyses (\code{test\_perf.R}), and a microarray classification case study (\code{test\_lda.R}).
%
The experiments, implemented in R, can be run by following the steps below:
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{\ding{182}} Download the synthetic datasets (\textcolor{black}{ total size 20GB}) by executing the following command in the terminal within the~\code{/Replication} directory.
%
\begin{minted}{bash}
curl -o temp.zip https://drive.switch.ch/index.php/s/Avxc8ugzHXvW5jN/download
unzip temp.zip -d squic_test_db/
\end{minted}
Note that the default location of the datasets should be \code{Replication/squic\_test\_db/}.
%
If this is changed the file \code{Replication/load\_data.R} must be modified accordingly.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{\ding{183}} Install the {R} libraries required for the experiments. \textcolor{black}{These packages are not dependencies
of SQUIC, but are used in the numerical experiments.}
%
\begin{minted}{bash}
Rscript install_dependencies.R
\end{minted}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\paragraph{\ding{184}} The test scripts for the five experiments can now be run individually.
%
They all start with ``\code{test\_}'' and can be run from the terminal; for example, to execute the test concerning the matrix inversion experiments, use the following command:
%
\begin{minted}{bash}
Rscript test_inv.R
\end{minted}
%
{MATLAB} scripts, as opposed to {R}, are utilized for the testing of the \code{SNETCH} algorithm.
%
Experiments evaluating the accuracy of the scalar tuning parameter and the performance of the \code{SNETCH} package can be found in \code{/Replication/test\_SNETCH} and can be executed using the scripts \code{test\_scal\_acc\_SNETCH.m} and \code{test\_perf\_SNETCH.m}, respectively.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Microarray Classification Case Study}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
This section describes the microarray classification test (\code{test\_lda.R}), using SQUIC for high-dimensional gene expression classification via inear discriminant analysis (LDA).
%
This complements Section 4.2 in~\cite{SQUIC_TOMS}, which discusses results and test timings. 
%
The collection of datasets used for our test are available from the~\code{datamicroarray} package.\footnote{
%
The \code{datamicroarray} package is available at \href{https://github.com/ramhiser/datamicroarray}{github.com/ramhiser/datamicroarray}.
}
%
We provide R code snippets for key steps and use the transcription of the variable name like $\eta$ and $\bb{M}$ as \mintinline{R}{eta} and \mintinline{R}{M} in the code.

We begin by loading the datasets and employ a stratified approach to split them into training and testing sets.
%
Using the \code{caret} package,\footnote{
The \texttt{caret} package is a collection of functions for training and plotting classification and regression models, and is available at~\href{https://cran.r-project.org/package=caret}{cran.r-project.org/package=caret}.
%
} we select $70\%$ of the samples, comprising of the feature values and their corresponding labels from each class, to form the training set.
%
This data is referred to as \mintinline{R}{data_train} and \mintinline{R}{labels_train}.
%
The remainder of the dataset is used for testing, for which we follow the same naming standard.
%
To simplify the selection of the tuning parameter, matrix or its scalar form (see, e.g., Section~\ref{sec:1} for further details), we normalized the data using the diagonal matrix \mintinline{R}{D} as shown below.
%
We later undo this scaling once the precision matrix estimation procedure is completed.
%
\begin{minted}{R}
n_train <- dim(data_train)[2]
a <- (apply(data_train,1,var))*(n_train-1)/n_train
D <- Diagonal(x=1/sqrt(a))
data_train_scaled <- D%*%data_train
\end{minted}
%
In this study, we define two versions of the tests: one using the matrix tuning parameter $\bb{\Lambda}$, and the other using just the scalar tuning parameter $\lambda$.
%
To define $\bb{\Lambda}$, we need to first specify $\bb{M}$, which we now describe.
%
In the first step, we generate a complete graph with edge weights represented by the Euclidean distance.
%
Subsequently, we compute the adjacency matrix, denote here as $\mintinline{R}{G}$, corresponding to the Minimal Spanning Tree (MST). 
%
The MST is a sparsely connected graph with the minimum sum of edge weights required for connectivity.
%
The nonzero pattern of $\mintinline{R}{G}$ corresponds to pairs of nodes with low Euclidean distances between them, indicating high similarity.
%
By using the \texttt{emstreeR} package,\footnote{
The \texttt{emstreeR} package computes an Euclidean MST from data, and is available at \href{https://cran.r-project.org/package=emstreeR}{cran.r-project.org/package=emstreeR}.
} $\mintinline{R}{G}$ can be efficiently computed as follows.
%
\begin{minted}{R}
mst <- ComputeMST(as.matrix(data_train))
G <- sparseMatrix(dims=c(p,p), i=mst$to, j=mst$from, x=rep(1, p))
G <- forceSymmetric(G,uplo="L") + Diagonal(nrow(G))
\end{minted}
%
The last operation enforces symmetry and adds diagonal entries to $\mintinline{R}{G}$, as the adjacency matrix of the MST will not have diagonal entries or self-links.
%
Note that the diagonal entries of $\mintinline{R}{G}$ are added simply so that they are reflected in $\mintinline{R}{M}$---the adjacency matrix of a MST will have zero for its diagonal entries.
%
We can now define \mintinline{R}{M<-G*eta}, where for this study we fix \mintinline{R}{eta <- 0.1}.


\vspace{1em}
Using SQUIC, we now compute the required precision matrices, for which an appropriate $\lambda$ must be selected.
%
In this example, we set $\lambda=0.8$, but this choice depends on the dataset. 
%
For further details on the selection of $\lambda$ for the different datasets, please refer to~\cite{SQUIC_TOMS} or the replication script.
%
For the estimation procedure using the matrix tuning parameter, we fix $\lambda=0.95$ across all dataset tests.
%
The respective function calls for using just the scalar tuning parameter, and the case where the matrix tuning parameter is used, are as follows:
%
\begin{minted}{R}
squic_out   <- SQUIC(Y=data_train,lambda=0.80,M=NULL,tol=1e-3,tol_inv=1e-3)
squic_out_M <- SQUIC(Y=data_train,lambda=0.95,M=eta*G,tol=1e-3,tol_inv=1e-3)
\end{minted}
%
After computing $\bbh{\Theta}$, we \emph{undo} the normalization operation; for example, for the scalar tuning estimate, we would rescale the matrix as follows: \mintinline{R}{D%*%squic_out$X%*%D}.


\vspace{1em}
The LDA method is subsequently applied to classify the samples in the testing dataset. 
%
For each class $k=1,\ldots, K$, where $K$ is the number of classes in the given dataset (i.e., the labels), we compute the sample means using \mintinline{R}{data_train}.
%
Denoting the estimated precision matrices as \mintinline{R}{theta_est}, we compute the LDA score, \mintinline{R}{lda_score}, for each class and assign a predicted class based on the one with the highest LDA score.
%
\begin{minted}{R}
for (k in 1:K) {
  # prior probability for class k
  prior <- length(which(labels_train == k)) / n_train
  # sample mean for class k
  mu <- rowMeans(data_train[, which(labels_train == k)])
  mu_matrix <- matrix(mu, nrow = nrow(data_test), ncol = ncol(data_test), byrow = FALSE)
  # x - 0.5*\mu
  adjusted_data <- data_test - 0.5 * mu_matrix
  # Linear Discriminant function
  lda_score <- diag(t(adjusted_data) %*% theta_est %*% mu_matrix + log(prior))
  rho[, k] <- lda_score
}
predicted <- apply(rho, 1, which.max)
\end{minted}
%
Notice that, \code{prior} is a scalar value, \code{mu} is a one dimensional array of length $p$, and \code{mu\_matrix} is an array of size $p$ by $n$ which contains repeated columns of \code{mu}.
%
In addition, \code{rho} is an array containing the LDA scores for all samples for each class. 
%
For comparative purposes, this computation will be performed twice: once for each estimate of the precision matrix. 
%
Further details on the parameters used and the results attained in this experiment see~\cite{SQUIC_TOMS}.

\newpage
\bibliographystyle{acm}
\bibliography{locref}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
