%\VignetteIndexEntry{sdpt3r}
% JSS Article Template
\documentclass{article}


%%% Additional Packages %%%

% Algorithms
% http://tex.stackexchange.com/questions/229355/algorithm-algorithmic-algorithmicx-algorithm2e-algpseudocode-confused
\usepackage{algorithm}% http://ctan.org/pkg/algorithms
\usepackage{algpseudocode}% http://ctan.org/pkg/algorithmicx


% Font stuff
\usepackage[T1]{fontenc}% for correct hyphenation and T1 encoding
%\usepackage{lmodern}% latin modern font
\usepackage[american]{babel}% for American English

% Math fonts/symbols
\usepackage{amsmath}% sophisticated mathematical formulas with amstex (includes \text{})
\usepackage{mathtools}% fix amsmath deficiencies
\usepackage{amssymb}% sophisticated mathematical symbols with amstex
\usepackage{amstext}% ams mathematical fonts
\usepackage{amsfonts}% ams mathematical fonts

% Figures
\usepackage{graphicx}% for including figures

%%% Commands %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% vetors
\newcommand{\ve}[1]{\mathbf{#1}}           % for vetors
\newcommand{\sv}[1]{\boldsymbol{#1}}   % for greek letters
\newcommand{\m}[1]{\mathbf{#1}}               % for matrices
\newcommand{\sm}[1]{\boldsymbol{#1}}   % for greek letters
\newcommand{\tr}[1]{{#1}^{\mkern-1.5mu\mathsf{T}}}              % for transpose
\newcommand{\norm}[1]{||{#1}||}              % for transpose
\newcommand*{\mve}{\operatorname{ve}}
\newcommand*{\trace}{\operatorname{trace}}
\newcommand*{\rank}{\operatorname{rank}}
\newcommand*{\diag}{\operatorname{diag}}
\newcommand*{\vspan}{\operatorname{span}}
\newcommand*{\rowsp}{\operatorname{rowsp}}
\newcommand*{\colsp}{\operatorname{colsp}}
\newcommand*{\svd}{\operatorname{svd}}
\newcommand*{\edm}{\operatorname{edm}}  % euclidean distance matrix (D * D)


% statistical
\newcommand{\widebar}[1]{\overline{#1}}  

% 
% operators
\newcommand{\Had}{\circ}
\DeclareMathOperator*{\lmin}{Minimize}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\arginf}{arg\,inf}
\DeclareMathOperator*{\argsup}{arg\,sup}
%\newcommand*{\arginf}{\operatorname*{arginf}}
%\newcommand*{\argsup}{\operatorname*{argsup}}

% Sets
\newcommand*{\intersect}{\cap}
\newcommand*{\union}{\cup}
\let\oldemptyset\emptyset
\let\emptyset\varnothing

% Fields, Reals, etc. etc
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\Reals}{\field{R}}
\newcommand{\Integers}{\field{Z}}
\newcommand{\Naturals}{\field{N}}
\newcommand{\Complex}{\field{C}}
\newcommand{\Rationals}{\field{Q}}

% Hyphenation
\hyphenation{Ar-chi-me-dean}

% Editorial
\newcommand*{\TODO}[1]{\textcolor{red}{TODO: #1}}
\newcommand*{\NOTE}[1]{\textcolor{blue}{Note: #1}}
\newtheorem{theorem}{Theorem}
\newtheorem{Proof}{Proof}

\usepackage[total={6.5in,8.75in}, top=0.9in, left=0.7in, right=0.7in, includefoot]{geometry}

% Misc
%\makeatletter
%\newcommand\myisodate{\number\year-\ifcase\month\or 01\or 02\or 03\or 04\or 05\or 06\or 07\or 08\or 09\or 10\or 11\or 12\fi-\ifcase\day\or 01\or 02\or 03\or 04\or 05\or 06\or 07\or 08\or 09\or 10\or 11\or 12\or 13\or 14\or 15\or 16\or 17\or 18\or 19\or 20\or 21\or 22\or 23\or 24\or 25\or 26\or 27\or 28\or 29\or 30\or 31\fi}% create iso date
\makeatother
%\newcommand*{\abstractnoindent}{}% define abstract such that it has no indent
%\let\abstractnoindent\abstract
%\renewcommand*{\abstract}{\let\quotation\quote\let\endquotation\endquote
%  \abstractnoindent}
%\deffootnote[1em]{1em}{1em}{\textsuperscript{\thefootnotemark}}% setting for footnote

\author{Adam Rahman}
\title{Toeplitz Approximation}


%% need no \usepackage{Sweave.sty}

\begin{document}
\SweaveOpts{concordance=FALSE}

\maketitle

Given a symmetric matrix $\m{F}$, the Toeplitz approximation problem seeks to find the nearest symmetric positive definite Toeplitz matrix. In general, a Toeplitz matrix is one with constant descending diagonals, i.e.

\[
\m{T} = \left[
\begin{array}{ccccc}
a & b & c & d & e \\
f & a & b & c & d \\
g & f & a & b & c \\
h & g & f & a & b \\
i & h & g & f & a
\end{array}
\right]
\]

is a general Toeplitz matrix. For our specific problem, we seek a \emph{symmetric} Toeplitz matrix, i.e.,

\[
\m{T}^{\ast} = \left[
\begin{array}{ccccc}
a & b & c & d & e \\
b & a & b & c & d \\
c & b & a & b & c \\
d & c & b & a & b \\
e & d & f & b & a
\end{array}
\right]
\]

The problem is formulated as the following optimization problem 

\[
\begin{array}{ll}
\underset{\m{X}}{\text{maximize}} & -y_{n+1} \\
\text{subject to} & \\
&
\begin{array}{rl}
\left[\begin{array}{cc}
\m{I} & \m{0} \\
\m{0} & -\beta
\end{array}\right] ~~+~~ \sum_{k=1}^{n}y_{k}
\left[\begin{array}{cc}
\m{0} & \gamma_{k}\ve{e}_{k} \\
\gamma_{k}\ve{e}_{k}^{T} & -2q_{k}
\end{array}\right] ~~+~~y_{n+1}\m{B} &\geq~~ \m{0} \\
\tr{[y_{1},...,y_{n}]} + y_{n+1}\m{B} & \geq~~ \ve{0}
\end{array}
\end{array}
\]

\noindent where $\m{B}$ is an $(n+1)\times(n+1)$ matrix of zeros, and $\m{B}_{(n+1)(n+1)} = 1$, $q_{1} = -tr(\m{F})$, $q_{k} =$ sum of $k^{th}$ diagonal upper and lower triangular matrix, $\gamma_{1} = \sqrt{n}$, $\gamma_{k} = \sqrt{2*(n-k+1)},~k=2,...,n$, and $\beta = ||\m{F}||_{F}^{2}$. 

The function \verb!toep! takes as input a symmetric matrix \verb!F! for which we would like to find the nearest Toeplitz matrix, and returns the input variables required to solve the problem using \verb!sqlp!.

\begin{verbatim}
R> out <- toep(F)
R> blk <- out$blk
R> At <- out$At
R> C <- out$C
R> b <- out$b

R> sqlp(blk,At,C,b)
\end{verbatim}

\section*{Numerical Example}

Consider the following symmetric matrix for which we would like to find the nearest Toeplitz matrix

\begin{verbatim}
R> data(Ftoep)

          V1     V2     V3     V4     V5     V6     V7     V8     V9    V10
 [1,]  0.170  0.127  0.652 -0.490  0.963  0.372 -0.707 -0.250 -0.022  1.087
 [2,]  0.127 -1.637  0.031  1.276 -1.475 -1.842 -0.529  1.534 -2.810  0.923
 [3,]  0.652  0.031  3.339 -0.246  0.249 -2.367  4.327  0.876 -1.832  0.507
 [4,] -0.490  1.276 -0.246 -1.556 -1.415 -0.022 -0.052  1.564 -1.140 -0.982
 [5,]  0.963 -1.475  0.249 -1.415 -0.656 -0.059 -3.101  0.337 -1.526 -0.737
 [6,]  0.372 -1.842 -2.367 -0.022 -0.059  2.617 -0.919  0.869  2.574  0.669
 [7,] -0.707 -0.529  4.327 -0.052 -3.101 -0.919  0.936  1.458 -0.622  1.632
 [8,] -0.250  1.534  0.876  1.564  0.337  0.869  1.458  0.013  1.348  1.736
 [9,] -0.022 -2.810 -1.832 -1.140 -1.526  2.574 -0.622  1.348 -3.817  0.925
[10,]  1.087  0.923  0.507 -0.982 -0.737  0.669  1.632  1.736  0.925  0.527
\end{verbatim}

Using \verb!sqlp!, we are interested in the output \verb!Z!, the optimal solution to the dual problem, which will be the nearest symmetric Toeplitz matrix. Note that the final row/column should be removed.

\begin{verbatim}
R> out <- toep(Ftoep)
R> blk <- out$blk
R> At <- out$At
R> C <- out$C
R> b <- out$b

R> out <- sqlp(blk,At,C,b)
R> F <- out$Z[[1]]
R> F <- F[-nrow(F),]
R> F <- F[,-ncol(F)]

       [,1]   [,2]   [,3]   [,4]   [,5]   [,6]   [,7]   [,8]   [,9]  [,10]
 [1,]  0.563  0.098 -0.038 -0.113  0.343 -0.054 -0.237 -0.369  0.228  0.077
 [2,]  0.098  0.563  0.098 -0.038 -0.113  0.343 -0.054 -0.237 -0.369  0.228
 [3,] -0.038  0.098  0.563  0.098 -0.038 -0.113  0.343 -0.054 -0.237 -0.369
 [4,] -0.113 -0.038  0.098  0.563  0.098 -0.038 -0.113  0.343 -0.054 -0.237
 [5,]  0.343 -0.113 -0.038  0.098  0.563  0.098 -0.038 -0.113  0.343 -0.054
 [6,] -0.054  0.343 -0.113 -0.038  0.098  0.563  0.098 -0.038 -0.113  0.343
 [7,] -0.237 -0.054  0.343 -0.113 -0.038  0.098  0.563  0.098 -0.038 -0.113
 [8,] -0.369 -0.237 -0.054  0.343 -0.113 -0.038  0.098  0.563  0.098 -0.038
 [9,]  0.228 -0.369 -0.237 -0.054  0.343 -0.113 -0.038  0.098  0.563  0.098
[10,]  0.077  0.228 -0.369 -0.237 -0.054  0.343 -0.113 -0.038  0.098  0.563
\end{verbatim}
\end{document}