User talk:Wotao.yin

From Wikimization

(Difference between revisions)

Current revision

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)

Retrieved from "http://www.convexoptimization.com/wikimization/index.php/User_talk:Wotao.yin"

@@ Line 8: / Line 8: @@
 </center>
-Rectangular submatrix <math>\,X\!\in\mathbb{R}^{1024\times256}\,</math> comes from a permutation matrix <math>\,\Xi\!\in\!\mathbb{R}^{1024\times1024}\,</math> having three out of every four consecutive columns discarded. &nbsp;  This discard occurs because of structural redundancy in <math>\Xi\,</math>.
+Nonnegative rectangular submatrix <math>\,X\!\in\mathbb{R}^{1024\times256}\,</math> comes directly from a permutation matrix <math>\,\Xi\!\in\!\mathbb{R}^{1024\times1024}\,</math> having three out of every four consecutive columns discarded. &nbsp;  This discard occurs because of structural redundancy in <math>\Xi\,</math>.
-Notation <math>\mbox{vec}\,X</math> denotes vectorization; it means, the columns of <math>\,X</math> are stacked with column 1 on top and column 256 on the bottom.
+Notation <math>\mbox{vec}\,X\!\in\mathbb{R}^{262144}</math> denotes vectorization; it means, the columns of <math>\,X</math> are stacked with column 1 on top and column 256 on the bottom.
 Matrix <math>A\!\in\!\mathbb{R}^{10565\times262144}</math> is sparse having only 979,444 nonzeros. &nbsp;
-It contains only integers from the set <math>\{{-1},0,1,2\}\,</math>.&nbsp;
+All its entries are integers from the set <math>\{{-1},0,1,2\}\,</math>.&nbsp;
 The 2 appears only in the fifth row from the bottom of <math>A\,</math>.
 Vector <math>b\,</math> is quite sparse having only a single nonzero entry: <math>1\,</math>.
-A Matlab binary containing matrices <math>\,A</math> and <math>\,b</math> is
+A [http://www.convexoptimization.com/TOOLS/Wotao.Yin/WotaoX.mat Matlab binary] contains matrices <math>\,A</math> and <math>\,b</math>. &nbsp;
-[http://www.convexoptimization.com/TOOLS/Wotao.Yin/WotaoX.mat here]. &nbsp;
+Vector <math>c\,</math> is left unspecified because I want to vary it later as part of a
-Vector <math>c\,</math> is left unspecified because I want to vary it later as part of a convex iteration. &nbsp;
+[[Convex Iteration]]. &nbsp;
 Vector <math>c\,</math> may arbitrarily be set to <math>\mathbf{0}</math> or <math>\mathbf{1}</math>, 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 <math>\,A</math> because one of the constraints '''('''fifth row from the bottom of <math>\,A\,</math>''')''' has only nonnegative entries. &nbsp;  This means that about 50,000 entries in permutation submatrix <math>X\,</math> can be set to zero before numerical solution begins. &nbsp;  The [http://www.convexoptimization.com/TOOLS/Wotao.Yin/WotaoX.mat Matlab binary] possesses all 262,144 columns of <math>A\,</math>; &nbsp; none of its columns have been discarded in a presolve.
+A good presolver can eliminate about 50,000 columns of <math>\,A</math> because one of the constraints '''('''fifth row from the bottom of <math>\,A\,</math>''')''' has only nonnegative entries. &nbsp;  This means that about 50,000 entries in permutation submatrix <math>X\,</math> can be set to zero before numerical solution begins. &nbsp;  The [http://www.convexoptimization.com/TOOLS/Wotao.Yin/WotaoX.mat Matlab binary] possesses all 262,144 columns of <math>A\,</math>; &nbsp; none of its columns have yet been discarded by a presolve.
 --[[User:Dattorro|Dattorro]] 03:31, 5 November 2010 (PDT)

User talk:Wotao.yin

From Wikimization

Current revision

Views

Personal tools

Navigation

Search

Toolbox