User talk:Wotao.yin

From Wikimization

(Difference between revisions)
Jump to: navigation, search
Line 1: Line 1:
-
I regard the following as a difficult problem, having spent considerable time with it.
+
I regard the following as a very difficult problem, having spent considerable time with it.
<center>
<center>
Line 8: Line 8:
</center>
</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.
+
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>.
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</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.
+
Matrix <math>A\!\in\!\mathbb{R}^{10565\times262144}</math> is sparse having only 979,444 nonzeros. &nbsp;
-
It contains integers from the set <math>\{{-1},0,1,2\}\,</math>.
+
It only contains integers from the set <math>\{{-1},0,1,2\}\,</math>.
Vector <math>b\,</math> is quite sparse having only a single nonzero entry: <math>1\,</math>.
Vector <math>b\,</math> is quite sparse having only a single nonzero entry: <math>1\,</math>.
- 
-
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. This means that about 50,000 entries in permutation submatrix <math>X\,</math> can be set to zero before solution begins.
 
A Matlab binary containing matrices <math>\,A</math> and <math>\,b</math> is
A Matlab binary containing matrices <math>\,A</math> and <math>\,b</math> is
-
[http://www.convexoptimization.com/TOOLS/Wotao.Yin/WotaoX.mat here].
+
[http://www.convexoptimization.com/TOOLS/Wotao.Yin/WotaoX.mat here]. &nbsp;
-
Vector <math>c\,</math> is left unspecified beause I may want to vary it later in a convex iteration.
+
Vector <math>c\,</math> is left unspecified beause I may want to vary it later in a convex iteration. &nbsp;
-
For your purposes, it may arbitrarily be set to <math>\mathbf{0}</math> or <math>\mathbf{1}</math>.
+
For your purposes, <math>c\,</math> may arbitrarily be set to <math>\mathbf{0}</math> or <math>\mathbf{1}</math>.
 +
 
 +
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 solution begins. &nbsp; The Matlab binary above has all columns of <math>A\,</math>; &nbsp; none of its columns have been discarded.
 +
 
--[[User:Dattorro|Dattorro]] 03:31, 5 November 2010 (PDT)
--[[User:Dattorro|Dattorro]] 03:31, 5 November 2010 (PDT)

Revision as of 04:21, 5 November 2010

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}

Rectangular submatrix LaTeX: \,X\!\in\mathbb{R}^{1024\times256}\, comes 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 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.   It only contains integers from the set LaTeX: \{{-1},0,1,2\}\,.

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

A Matlab binary containing matrices LaTeX: \,A and LaTeX: \,b is here.   Vector LaTeX: c\, is left unspecified beause I may want to vary it later in a convex iteration.   For your purposes, LaTeX: c\, may arbitrarily be set to LaTeX: \mathbf{0} or LaTeX: \mathbf{1}.

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 solution begins.   The Matlab binary above has all columns of LaTeX: A\,;   none of its columns have been discarded.


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

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