# User talk:Wotao.yin

I regard the following as a very difficult problem, having spent considerable time with it.

$LaTeX: \begin{array}{cl}\mbox{minimize}_X&c^{\rm T}\mbox{vec}\,X\\ \mbox{subject to}&A\,\mbox{vec}\,X=b\\ &X^{\rm T\!}X=I\\ &X\geq_{}\mathbf{0}\end{array}$

Nonnegative rectangular submatrix $LaTeX: \,X\!\in\mathbb{R}^{1024\times256}\,$ comes directly from a permutation matrix $LaTeX: \,\Xi\!\in\!\mathbb{R}^{1024\times1024}\,$ having three out of every four consecutive columns discarded.   This discard occurs because of structural redundancy in $LaTeX: \Xi\,$.

Notation $LaTeX: \mbox{vec}\,X\!\in\mathbb{R}^{262144}$ denotes vectorization; it means, the columns of $LaTeX: \,X$ are stacked with column 1 on top and column 256 on the bottom.

Matrix $LaTeX: A\!\in\!\mathbb{R}^{10565\times262144}$ is sparse having only 979,444 nonzeros.   All its entries are integers from the set $LaTeX: \{{-1},0,1,2\}\,$.  The 2 appears only in the fifth row from the bottom of $LaTeX: A\,$.

Vector $LaTeX: b\,$ is quite sparse having only a single nonzero entry: $LaTeX: 1\,$.

A Matlab binary contains matrices $LaTeX: \,A$ and $LaTeX: \,b$.   Vector $LaTeX: c\,$ is left unspecified because I want to vary it later as part of a Convex Iteration.   Vector $LaTeX: c\,$ may arbitrarily be set to $LaTeX: \mathbf{0}$ or $LaTeX: \mathbf{1}$, for your purposes, but leave a hook for it in case you require another value.

A good presolver can eliminate about 50,000 columns of $LaTeX: \,A$ because one of the constraints (fifth row from the bottom of $LaTeX: \,A\,$) has only nonnegative entries.   This means that about 50,000 entries in permutation submatrix $LaTeX: X\,$ can be set to zero before numerical solution begins.   The Matlab binary possesses all 262,144 columns of $LaTeX: A\,$;   none of its columns have yet been discarded by a presolve.

--Dattorro 03:31, 5 November 2010 (PDT)