tag:blogger.com,1999:blog-51990457611478283052017-11-19T00:44:19.936-08:00The Connected PictureMusings of a math prof at WSU on topology, geometry, and optimization.Bala Krishnamoorthynoreply@blogger.comBlogger6125tag:blogger.com,1999:blog-5199045761147828305.post-15952101271270580412017-11-15T20:18:00.000-08:002017-11-15T23:40:08.496-08:00Category Theory and Sheaves<div dir="ltr" style="text-align: left;" trbidi="on"><html><head><script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"> MathJax.Hub.Config({ HTML: ["input/TeX","output/HTML-CSS"], TeX: { extensions: ["AMSmath.js","AMSsymbols.js", "AMScd.js"], equationNumbers: { autoNumber: "AMS" } }, extensions: ["tex2jax.js"], jax: ["input/TeX","output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\\(","\\)"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true }, "HTML-CSS": { availableFonts: ["TeX"], linebreaks: { automatic: true } } }); </script><style>p { text-indent: 40px; } </style><style>q { text-indent: 140px; } </style></head> <title>Category Theory and Sheaves</title> <body> <i>Guest post by PhD Student <a target="_blank" href="http://www.math.wsu.edu/students/mbroussard/">Matthew Broussard</a>.</i><br><br> <h3>Motivation</h3> <p>In this post, we plan to explore the basic language of <a target="_blank" href="https://en.wikipedia.org/wiki/Category_theory">category theory</a> with an eye towards defining <a target="_blank" href="https://en.wikipedia.org/wiki/Sheaf_(mathematics)">sheaves</a>, mathematical constructs which formalize the transition between local and global data on a space. In future posts we will explore the theory and application of sheaves in more detail, but first we need to lay the groundwork for our later discussion. </p> <p>There is quite a bit of background and vocabulary necessary to make sense of sheaves. We could argue that sheaves are mathematical entities with rich structure in themselves, and thus are of interest to abstract mathematicians. Still, generally if one puts in the effort to learn any mathematical concept technical enough to be called "theory," one wishes to get <i>something</i> from the work. It is disappointing to go to all the work to learn such a discipline only to find that it doesn't actually give you a way to approach new problems! </p> <p>Sheaves give us powerful tools which make many generalizations possible. For example, homology and cohomology can both be expanded from their purely topological roots into the world of sheaves, and the more general framework allows the topological results to fall out as special cases (as one hopes from a generalization). Viewed over graphs, sheaves show the topological underpinnings of certain graph and network theoretic problems. </p> <p>But what new avenues do these open? Sheaves give us better insight into the structure of spaces. For instance, Joel Friedman <a href="https://www.blogger.com/blogger.g?blogID=5199045761147828305#ref">[2]</a> showed that morphisms from graphs $G_i$ to a graph $G$ can be viewed as sheaves $S(G_i)$ over $G$, and that morphisms between $G_i$ and $G_j$ induce morphisms between their respective sheaves. However, there are sheaf morphisms between these induced sheaves which are not the result of graph morphisms. These extra morphisms capture aspects of the structure of $G$ which have not been well captured in graph theory alone. This refinement of structural detection allows sheaf theory to address questions about graphs which have been intractable to normal graph theoretic approaches. </p> <h3>Category Theory</h3> <p>When one studies various structures in mathematics, one often encounters similar patterns in different constructs. For instance, cycles in topological spaces behave in some ways like abelian groups. As another example, there are some properties of a structure drawn from the base set on which the structure is imposed. Category theory is a language which makes such correspondences more rigorous, as well as the tools to turn these correspondences into a mathematical structure of their own. </p> <p>We will explore an introduction to category theory with a focus in topology, both due to the personal interest of the author and because topology is the historical origin of categories. We will focus particularly on the categories of presheaves and sheaves. These categories are of particular interest to topological data processing and analysis, as we will explore more deeply in a future post. </p> <h4>Categories</h4> <p>First, though, we must understand the language of category theory. What exactly is a category? (We mostly follow the construction found in <b>Elements of Algebraic Topology</b> by Munkres, though with fewer, but more detailed examples). </p> <p>We define a <b>category</b> to consist of three things: <ol> <li>A class of <b>objects</b></li> <li>For each ordered pair of objects $(X,Y)$, a set $\mathrm{hom}(X,Y)$ of <b>morphisms</b></li> <li>A composition function on the morphisms such that $(f,g)=g \circ f: \mathrm{hom}(X,Y) \times \mathrm{hom}(Y,Z) \rightarrow \mathrm{hom}(X,Z)$ for all objects $X, Y, Z$ where $g \circ f$ is associative and has identities — that is <ul><li>If $f \in \mathrm{hom}(W,X), h \in \mathrm{hom}(X,Y)$, and $g\in \mathrm{hom}(Y,Z)$, then $h \circ (g \circ f)=(h\circ g)\circ f$</li> <li>There exists $1_{X} \in \mathrm{hom}(X,X)$ such that $1_{X}\circ f=f$ and $g\circ 1_{X}=g$</li></ul> </li></ol></p> <p> There are several categories which we use in the study of algebraic topology. Most ubiquitous are the category of topological spaces with continuous maps and standard composition and the category of abelian groups under homomorphism (with standard composition, which we will take as implied henceforth unless a particular composition rule is stated). The category of chain complexes and chain maps is also a fairly common sight, though there are others — later, for instance, we will discuss the category of topological spaces with restriction maps as morphisms, as well as the category of finite semimodules with quotient maps. </p> <p> Usually the objects in a category are the things we study in a particular branch of mathematics (topological spaces, groups, rings, manifolds, etc.) and the morphisms are maps between members of our chosen object which are sufficient to preserve some aspect or aspects of our object (for instance, if we only wish to discuss topological invariants, we could consider the category of topological spaces under homeomorphism. If we cared about properties preserved by continuous maps, we would instead equip our category with morphisms of continuous maps). </p> <p> Thus far, category theory hasn't given us anything new. It has only provided a slightly different way to talk about maps between structural elements. The theory's utility arises from functors, a type of map between categories. </p> <h3>Functors</h3> <p>A <b>functor</b> is a function $G:C \rightarrow D$ where $C$ and $D$ are categories such that <ol><li>for each object $X$ of $C, G(C)$ is an object of $D$;</li> <li>for each morphism $F:X\rightarrow Y$ of $C, G(f):G(X)\rightarrow G(Y)$ is a morphism of $D$;</li> <li>$G(1_{X})=1_{G(X)}$ for all $X$; and </li> <li>$G(g\circ f)=G(g)\circ G(f)$ for all $g,f$.</li> </ol>(It is of interest to note that the categories with functor morphisms is an admissible category, though we will not use this fact.) </p> <p>There are several basic functors, with the identity functor and the forgetful functor perhaps foremost among them. The <b>identity functor</b> maps from a category to itself and, as with most identity maps, takes objects and morphisms back to themselves. The <b>forgetful functor</b>, a map that takes a structured space to its underlying set and its morphisms to their underlying set maps. </p> <p> However, there are also some functors which we use regularly in algebraic topology without realizing their functorial nature. Perhaps the most common one we use is homology. $H_n:Top \rightarrow Ab$ is a functor from the category of topological spaces to the category of abelian groups by assigning to each topological space (that is, the objects of $Top$) its $nth$ homology group (an object of the category of abelian groups). Then given a continuous map $f$, the following diagram commutes: <br/><br/><center><span style="font-size: large;">$\begin{CD} H_n(X) @>{\rm Pushforward}>> H_n(Y)\\ @AAA @AAA\\ X@>>{f}> Y \end{CD}$ </span></center></p> <p> The morphism $ f_*$ between $H_n(X)$ and $H_n(Y)$ is known as the <a href="https://en.wikipedia.org/wiki/Pushforward_(homology)">pushforward</a>. Its construction is discussed in detail in <a href="https://www.blogger.com/blogger.g?blogID=5199045761147828305#Ref">[4]</a>, but the relevant results for our purposes are that (i) the identity map induces the identity homomorphism, and (ii) for $f:K\rightarrow L$ and $g:L\rightarrow M$, we have $(g\circ f)_*=g_*\circ f_*$. </p> <p>Clearly the first requirement holds: every space has an $nth$ homology group. Likewise, we noted that each map induces a homomorphism, so if we say $H_n$ takes $f$ to $f_*$ the second requirement is filled. The third and fourth requirements follow from the results we noted about induced homomorphisms. </p> <p>Whether explicitly or implicitly stated, the functoriality of the homology construction is an integral part of the proof that homology is a topological invariant. </p> <p> Likewise, there is a functor from the category of simplicial complexes and simplicial maps to that of chain complexes and chain maps which assigns $K\rightarrow \mathscr{C} (K)$ and $f\rightarrow f_\#$. Again, every simplicial complex has a chain complex associated with it, and every simplicial map $f$ induces a chain map $f_\#$, so the first two conditions are upheld. The latter two arise from the verification that the identity simplicial map $\iota$ induces the identity chain map and that $(g\circ f)_\#=g_\#\circ f_\#$, both of which follow from the definition of $f_\#$. </p> <p> Other functors appear in topological studies. Homotopy relies on the fundamental group, for instance, which also exhibits functorial properties. While the fact that these are functors is an important and useful point, these results are generally used independently of category theory. Our interest, however, will lie with a form of functor that is rarely discussed outside of the context of category theory: sheaves. </p> <h3>What is a Sheaf?</h3> <i>N.B.:</i> The information we present here on sheaf theory is largely drawn from <a href="https://www.blogger.com/blogger.g?blogID=5199045761147828305#Ref">[1]</a>, with some clarifications from <a href="https://www.blogger.com/blogger.g?blogID=5199045761147828305#Ref">[4]</a>. <p>A <i>sheaf</i> is a means to keep track of data over a space. Data sources are required to agree on comparable data when they overlap in space, and local data is required to be sufficient to recover global data. </p> <p>Formally, a <b>presheaf</b> is a functor $F:\rm{Open}^{op}(X) \rightarrow \rm{Alg}$ from the category of open sets on the topological space $X$ with restriction morphisms to an algebraic category. A <b>sheaf</b> is a presheaf with additional structure: <ol><li>Given an open cover $\{U_i\}$ of an open set $U$, if $s,t \in F(U)$ with $s|_{U_i}=t|_{U_i}$ for each $i$, then $s=t$.</li> <li>Given an open cover $\{U_i\}$ of an open set $U$, with an $s_i\in F(U_i)$ for each $i$ such that $s_i |_{U_i\cap U_j}=s_j|_{U_i\cap U_j}$ for all $i,j$, then there is an element $s\in F(U)$ such that $s|_{U_i}=s_i$ for all $i$.</li></ol></p> <p> The first condition (called the locality condition) requires that two pieces of global data that look the same locally are in fact the same globally. The second (called the gluing condition) requires that data which agrees can be glued together into a global structure. We think of $s$ and $t$ (called sections) as particular choices of data with the assigned algebraic structures as all possible data. <br> (Note that locality demands that $F(\varnothing)=0$, since $\cup_{i\in \varnothing} U_i$ is an open cover of $\varnothing$, and any two distinct sections agree on all elements of the cover yet are not equal. This requirement will generally be implied.) </p> <h4>Example 1</h4> Let's look at a specific example of a sheaf built on a space $X$ composed of two disjoint open sets $A$ and $B$. <p> We want to build a sheaf that works as much like a constant function as we can. Let's define a functor $F:Top(X)\rightarrow Grp$ from the category of open sets of $X$ with restriction maps to the category of groups with group homomorphisms by $F(U)=G$ for each non-empty open set $U$ for a fixed group $G$ and $F(g)=\iota$ for all restriction maps except those to $\varnothing$, which all map to $0$. Is this a sheaf? </p> <p> That this is a presheaf (that is, that $F$ is a functor) is easy to show. For locality, suppose there is an open set $U$ with open cover $\{U_i\}$. Given two sections $s,t \in G$ with $s\neq t$, since restriction maps induce the identity homomorphism $s=s|_{U_i}$ and $t=t|_{U_i}$. Thus $s|_{U_i}\neq t|_{U_i}$ for some $i$ (indeed for all $i$), so by the contrapositive if $s,t \in F(U)$ with $s|_{U_i}=t|_{U_i}$ for each $i$, then $s=t$, so locality holds. </p> <p> Finally, the gluing condition. Take $G=\{0,1\}$ and the open cover $A, B$. Choose the local sections $s_1=F(A)=0$ and $s_2=F(B)=1$. Since they don't intersect, $s_1|_{A\cap B}=0=s_2|_{A\cap B}$, yet there is no value in $s\in F(X)=G$ with $s_{A}=s_1$ and $s_{B}=s_2$, so there is no global section which works. </p> <p> The closest we can get to what we would think of intuitively as a constant sheaf on this space is to assign $F(U)=G\times G$ if $U$ intersects both $A$ and $B$, $F(U)=G\times \varnothing$ if $U$ only intersects $A$, and $F(U)=\varnothing \times G$ if $U$ only intersects $B$, rendering the following diagram:<br><br> <center><span style="font-size: large;">$\begin{CD} G @<{\pi_1}<< G\times G @>{\pi_2}>> G\\ @AA{F}A @AA{F}A @AA{F}A\\ V_2@<<{\rm Containment}< V_1 @>>{\rm Containment}>V_3 \end{CD}$ </span></center></body></html></div><br> Here, $V_1$ is the set of open subsets of $X$ which intersect $A$ and $B$, $V_2$ those that intersect only $A$, and $V_3$ those that intersect only $B$. Containments within one of these classes induces the identity map, and all containments of the null set induce the zero map, though we don't include these details in the diagram. </p> <p> Note that again this is a presheaf and locality holds, but now the gluing condition is fulfilled, and hence it is a sheaf. We call this the constant sheaf on this space. <br>(See <a href="https://www.blogger.com/blogger.g?blogID=5199045761147828305#Ref">[1]</a> section 3.1 for more information on when constant sheaves are possible and when locally constant sheaves are required) </p><br> <h3>Example 2</h3> <p> In the previous example, we explored how locally consistent data can fail to produce a global section, where the data that we allow for the entire space is too restrictive to capture the variety of local data. Now we will explore the opposite problem: what happens when the global data isn't restrictive enough? </p> <p> Consider the discrete two point space $\{a, b\}$ where we assign $\mathbb{R}^3$ to $\{a,b\}$ and $\mathbb{R}$ to both $\{a\}$ and $\{b\}$, with the restriction map from $\{a,b\}$ to $\{a\}$ given by the projection $\pi_1$ onto its first coordinate and the restriction from $\{a,b\}$ to $\{b\}$ given by the projection $\pi_2$ onto its second coordinate, as shown in the diagram below.<br> <br><center><span style="font-size: large;">$\begin{CD} \mathbb{R} @<{\pi_1}<< \mathbb{R}^3 @>{\pi_2}>> \mathbb{R}\\ @AA{F}A @AA{F}A @AA{F}A\\ \{a\}@<<{\rm Containment}< \{a,b\} @>>{\rm Containment}>\{b\} \end{CD}$ </span></center><br></p> <p>Clearly any compatible local sections one chooses can be glued together as a global section. Indeed, given $s_1$ the local section over $\{a\}$ and $s_2$ over $\{b\}$, choosing any $(s_1, s_2, s_3)$ will be a global section consistent with both local sections. However, that very ease of choice makes this construction fail to be a sheaf. Two different global sections (any two distinct $s_3$ and $s_3'$ will do) agree on all local sections of the space, a violation on the condition of locality. In order to create a sheaf from this structure, we must either reduce the vector space attached to $\{a,b\}$ from $\mathbb{R}^3$ to $\mathbb{R}^2$ or we must introduce a third point in the space onto which we project the third coordinate from the full space, as illustrated below.<br><br><br><div class="separator" style="clear: both; text-align: center;"><a href="https://1.bp.blogspot.com/-Oxw2Ao33xoo/WdgY7rPm3zI/AAAAAAAAAFo/bG5mj4QKOn4ryR0ItnIYj6BwH3e96dGCQCLcBGAs/s1600/SheafDiagram3.png" imageanchor="1" style="background-color: white; margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="200" data-original-width="340" height="220" src="https://1.bp.blogspot.com/-Oxw2Ao33xoo/WdgY7rPm3zI/AAAAAAAAAFo/bG5mj4QKOn4ryR0ItnIYj6BwH3e96dGCQCLcBGAs/s320/SheafDiagram3.png" width="374" /></a></span></div><br>(See <a href="https://www.blogger.com/blogger.g?blogID=5199045761147828305#Ref">[1]</a> section 2.1 for the development of where the original scenario might arise) </p> <h3>Conclusion</h3> <p> Thus far we have discussed the basic terms required to understand sheaf theory. However, the intuition behind the construction still isn't clear. We claimed at the beginning that sheaves were a method of, among other things, keeping track of data. One might ask how the construction we've created corresponds with data in the normal sense. </p> <p>In the next post, we will show how we might understand the way sheaves track data in the context of pictures. Though sheaves are not usually applied in the case of image reconstruction (since it is easy enough to keep track of the involved information without going to the trouble of constructing a sheaf!), it will still give us an intuitive idea of what, exactly, a sheaf <i>does</i>, and what restriction morphisms, the gluing condition, and locality actually mean in a more concrete sense. </p> <h3 id="Ref">Works Cited</h3> [1] Curry, Justin M., "Sheaves, Cosheaves and Applications," University of Pennsylvania, 2014. <a target="_blank" href="https://arxiv.org/abs/1303.3255">arXiv</a><br>[2] Friedman, Joel, "Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture" University of British Columbia, 2011. <a target="_blank" href="https://arxiv.org/abs/1105.0129">arXiv</a><br>[3] Munkres, James R. "Elements of Algebraic Topology," Perseus Publishing, 1984<br>[4] <A target="_blank" href="https://www.math.upenn.edu/~ghrist/notes.html">R. Ghrist, Elementary Applied Topology</a>, ed. 1.0, Createspace, 2014 </span></div>Matthew Broussardhttps://plus.google.com/104508534740905463895noreply@blogger.com0tag:blogger.com,1999:blog-5199045761147828305.post-22441722189155552902017-10-31T20:00:00.000-07:002017-11-02T16:17:06.874-07:00De Rham Cohomology <div dir="ltr" style="text-align: left;" trbidi="on"><script src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"> MathJax.Hub.Config({ HTML: ["input/TeX","output/HTML-CSS"], TeX: { extensions: ["AMSmath.js","AMSsymbols.js"], equationNumbers: { autoNumber: "AMS" } }, extensions: ["tex2jax.js"], jax: ["input/TeX","output/HTML-CSS"], tex2jax: { inlineMath: [ ['$','$'], ["\\(","\\)"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ], processEscapes: true }, "HTML-CSS": { availableFonts: ["TeX"], linebreaks: { automatic: true } } }); </script> <i>Guest post by Phd student </i><a href="http://www.math.wsu.edu/students/ealvarado/" target="_blank"><i>Enrique Alvarado</i>. </a><br><br><br>In the following, we will take a look at the motivation for considering \(closed\) and \(exact\) forms on manifolds. This will lead us to look for the closed forms which are \(\it{not}\) exact -- which to put crudely, is what de Rham cohomology studies.<br><br>Let's first take an intuitive look at what differential forms are. <br><br>\({\mathbf{1.}}\)<br><br>\(\color{purple}{\mathbf{Definition.}}\) A differential \(k\)-form on \(\mathbb{R}^3\) is a differentiable mapping, \(\varphi : \mathbb{R}^3 \to \Lambda^k\), that takes a point in 3-space to a \(k\)-covector. <br><br>So, what are \(k\)-covectors?<br><br>\(\color{purple}{\mathbf{Definition.}}\) A \(k\)-\(\it{covector}\) is a funciton, \(\lambda : \Lambda_k \to \mathbb{R}\), that takes objects called \(k\)-\(\it{vectors}\) to real numbers.<br><br>In other words, \(\Lambda^k\) is the dual space of \(\Lambda_k\).<br><br>Now, to understand the vector space of \(k\)-vectors, denoted \(\Lambda_k\), let's take a little trip into Intuitionland by considering the cases for \(k = 0, 1, 2\), and \(3\). <br><br>A \(0\)-vector in \(\mathbb{R}^3\) can be thought to be a real number, a \(1\)-vector in \(\mathbb{R}^3\) can be thought to be a vector in \(\mathbb{R}^3\), and a \(2\)-vector in \(\mathbb{R}^3\) can be pictured as the wedge of two linearly independent vectors, as shown below.<br><br><br><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-bo6FW4xnUCs/VnIaUM_5K_I/AAAAAAAAAOo/6FfLJea6D40/s1600/2vector.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="273" src="https://1.bp.blogspot.com/-bo6FW4xnUCs/VnIaUM_5K_I/AAAAAAAAAOo/6FfLJea6D40/s320/2vector.png" width="320" /></a></div><div class="separator" style="clear: both; text-align: center;"></div><br>Similarly, a \(3\)-vector in \(\mathbb{R}^3\) can be pictured as a wedge of three linearly independent vectors as shown below.<br><br><div class="separator" style="clear: both; text-align: center;"><a href="http://1.bp.blogspot.com/-RzT6n0QxGlc/VnIZxuDqlZI/AAAAAAAAAOg/3ySldkJKMco/s1600/3vector.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="273" src="https://1.bp.blogspot.com/-RzT6n0QxGlc/VnIZxuDqlZI/AAAAAAAAAOg/3ySldkJKMco/s320/3vector.png" width="320" /></a></div><br>Now, although there is no geometric difference between \(k\)-vectors and \(k\)-covectors, there is an algebraic one. This reason can be intuitively explained by considering the difference between a \(1\)-vector and a \(1\)-covector. Notice that we are just saying that we are considering the difference between a vector, and a covector in 3-space. <br><br>If we think of 1-vectors as column vectors, \(\left(\begin{array}{}x_1\\ y_1\\ z_1\\ \end{array}{} \right),\) we can then think about 1-covectors as \(\it{row}\) vectors \(\left(x_2, y_2, z_2\right)\) since we can then operate on the column vectors to get a real number as follows. <br><br>\(\begin{array}{}\left(x_2, y_2, z_2\right) \end{array}{}<br>\cdot<br>\left(\begin{array}{} x_1\\ y_1\\ z_1\\ \end{array}{}\right) = x_1x_2 + y_1y_3 + z_1z_3\).<br><br>So what a differential \(k\)-form \(\varphi\) does is that to every point \(p\) in \(\mathbb{R}^3\), we have an associated \(k\)-covector. The figure below is a mapping \(p \mapsto \varphi \in \Lambda^3\).<br><br><br><div class="separator" style="clear: both; text-align: center;"><a href="http://2.bp.blogspot.com/-bOZnweG9TIs/VnIupWqrb5I/AAAAAAAAAO4/jLphngADFLU/s1600/3form.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="305" src="https://2.bp.blogspot.com/-bOZnweG9TIs/VnIupWqrb5I/AAAAAAAAAO4/jLphngADFLU/s320/3form.png" width="320" /></a></div><br>Another way of defining a differential \(k\)-form on \(\mathbb{R}^3\), is by saying that it is a \(k\)-covector field on \(\mathbb{R}^3\). We will denote the space of all \(k\)-forms on a manifold \(M\) as \(\mathbf{C}^k(M)\).<br><br>As we have seen, \(0\)-forms can be identified to be scalar functions. In \(\mathbb{R}^3\), 1-forms can be identified with vector fields, 2-forms can also be identified with vector fields via the right-hand rule, and 3-forms can be identified with scalar functions via a similar rule. There is a generalization of the gradient operator that is applied to forms.<br><br>\begin{align*}<br>d: \mathbf{C}^k(M) \to \mathbf{C}^{k+1}(M)<br>\end{align*}<br><br>Keeping in mind the ways we can identify 0-forms, 1-forms, and 2-forms, \(\omega \mapsto d\omega\) is then identifiable to:<br><br>(1) The gradient operator \(\omega \mapsto \nabla \omega\) when \(\omega\) is a 0-form.<br><br>(2) The curl operation \(\omega \mapsto \nabla \times \omega\) when \(\omega\) is a 1-form.<br><br>(3) The divergence operation \(\omega \mapsto \nabla \cdot \omega\) when \(\omega\) is a 2-form. <br><br>\({\mathbf{2.}}\)<br><br>Now, differential forms may be used to give us <i>global</i> information about manifolds, rather than local. For example, let's consider the manifold \(M := \mathbb{R}^2 - B\), where \(B\) is some open ball centered about the origin. If we take any point in \(M\), we can find a sufficiently small open ball that looks identical to some open ball in \(\mathbb{R}^2\). Therefore, all local properties of \(M\) are the same as those in \(\mathbb{R}^2\). But the fact that the origin is missing is a global property. <br><br>Certain differential forms are interesting for the purpose of detecting these types of global properties. The interesting ones have their <i>exterior derivative</i> zero. Such differential forms are called <i>closed</i>. That is, a differential form \(\varphi\) is \(\it{closed}\) if \(d\varphi = 0\). <br><br>So why are closed forms interesting when trying to investigate global properties? <br><br>Let \(\omega\) be a closed \(k\)-form, and let's integrate it over a closed smooth \(k\)-chain \(C\) (a chain \(C\) is closed if it has no boundary) in a manifold \(M\) that is at least \(k\)-dimensional. If \(S\) is the boundary of an orientable, compact, smooth submanifold \(S\) (i.e \(\partial S = C\)) of \(M\), then Stokes' Theorem states<br><br>\begin{align*}<br>\int_C \omega &= \int_S d\omega \\<br>&= \int_S 0 \\<br>&= 0.<br>\end{align*}<br><br>Therefore, if we have a closed \(k\)-form \(\omega\) on a submanifold \(C\) of \(M\) for which<br><br>\begin{align*}<br>\int_C\omega &\neq 0,<br>\end{align*}<br><br>we then know that \(C\) must \(\it{not}\) be \(\it{the}\) boundary of any oriented, compact, smooth submanifold of \(M\)! The fact that there exists such a submanifold \(C\) tells us about the global information of the manifold \(M\). <br><br>If we want to be able to detect these global properties, we have to find reasonable forms to integrate over \(S\). There might be forms which always integrate to 0, no matter what \(S\) is!<br><br>Such forms are called \(\it{exact}\). <br><br>\(\color{purple}{\mathbf{Definition}}\) A \(k\)-form, \(\omega\) is \(\it{exact}\) if there exists a \((k-1)\)-form such that \(\omega = d\varphi\).<br><br>Note that \(d:\mathbf{C}^{k}\to \mathbf{C}^{k+1}\) is an operator that takes k-forms and gives us (k+1)-forms, so the above definition makes sense. <br><br>Integrating exact forms over closed chains will always evaluate to 0. Let's prove this result for exact 1-forms and 1-chains.<br><br><a href="http://1.bp.blogspot.com/-G8L_r6cCRYc/VnRapMPu9-I/AAAAAAAAAPk/tMCt8beLvz8/s1600/closedcurve.png" imageanchor="1" style="clear: right; float: right; margin-bottom: 1em; margin-left: 1em;"><img border="0" height="281" src="https://1.bp.blogspot.com/-G8L_r6cCRYc/VnRapMPu9-I/AAAAAAAAAPk/tMCt8beLvz8/s320/closedcurve.png" width="320" /></a>Let's consider a 1-form \(\omega\) and a 0-form <span id="goog_498119398"></span><span id="goog_498119399"></span>\(\varphi\) for which \(\omega = d\varphi\), and let \(C\) be any closed 1-chain. If we pick any two points \(p, q \in C\), we may then say that \(C = A + B\) where \(A\) is the curve that goes from \(p\) to \(q\), and \(B\) is the curve that goes from \(q\) to \(p\).<br><br> We can now compute the following,<br><br>\begin{align*}<br>\int_C\omega &= \int_{A + B}\omega\\<br>&= \int_{B}\omega + \int_{A}\omega\\<br>&= \int_{B}d\varphi + \int_{A}d\varphi\\<br>&= \int_{p - q}d\varphi + \int_{q - p} d\varphi\\<br>&= 0.<br>\end{align*}<br><br>So yes, integrating an exact 1-from over a closed 1-chain always gives us zero, and this result holds in general as well. You may however say that the only reason that we were able to find global properties of a manifold was by applying Stokes' Theorem to closed forms. So this would only be <i>bad</i> if all exact forms are closed. This is in fact true!<br><br>\(\color{red}{\mathbf{Theorem.}}\) If \(\omega \in \mathbf{C}^k\) is exact, then it is also closed. That is, for any differential form \(\varphi\), \(d\circ d\varphi = 0\).<br><br>What this means is that we cannot just integrate any closed form. We must choose closed forms which are not exact. Do there exists such closed forms? What does exactness depend on?<br><br>To investigate these questions a little further, let's take a look at a 1-form on the punctured plane, and then a 1-form on the half plane. <br><br>\(\color{blue}{\mathbf{Example.}}\) Let \(M := \mathbb{R}^2 - \{0\}\), and consider the 1-form on \(M\)<br><br>\begin{align*}<br>\omega &= \frac{xdy - ydx}{x^2 + y^2}.<br>\end{align*}<br><br>Let \(\gamma : [0, 2\pi] \to M\) be the curve defined by \(\gamma (t) = (\cos{t}, \sin{t})\), whose trace is the unit circle. By substituting \(x = \cos{t}\) and \(y = \sin{t}\) everywhere in the formula for \(\omega\), we get that<br><br>\begin{align*}<br>\int_\gamma\omega &= \int_{[0,2\pi]}\frac{\cos{t}(\cos{t}\ dt) - \sin{t}(-\sin{t}\ dt)}{\sin^2{t} + \cos^2{t}} \\<br>&= \int_0^{2\pi}dt \\<br>&= 2\pi.<br>\end{align*}<br><br>This implies that \(\omega\) is not exact; because if it were, then integrating it over any closed curve would give us \(0\).<br><br>However, \(\omega\) \(\it{is}\) exact on some smaller domains such as the right half-plane \(H := \{(x, y) \in \mathbb{R}^2 : x > 0\}\). In the right half-plane, we get that \(\omega = d(\tan^{-1}({y/x}))\). In polar coordinates, we would get that \(\omega = d\theta\). <br><br>This in fact is true in general, as the following theorem describes.<br><br>\(\color{red}{\mathbf{Theorem.}}\) Let \(M\) be a smooth manifold with or without boundary. Each point of \(M\) has a neighborhood on which every closed form is exact.<br><br>What this tells us is that a form being exact is not a local property. So if our objective is to investigate global properties of manifolds, we must then find out which closed forms are \(\it{not}\) exact. This is precisely what <b>de Rham cohomology</b> studies! <br><br>\({\mathbf{3.}}\) <br>The way we do this is by constructing the following equivalence relation among closed \(k\)-forms. <br><br>Two closed \(k\)-forms \(\varphi\) and \(\omega\) are \(\it{equivalent}\) if their difference, \(\omega - \varphi\) is an exact form. That is, if<br><br>\begin{align*}<br>\omega - \varphi &= d\phi<br>\end{align*}<br><br>for some \(\phi \in C^{k-1}(M)\).<br><br>This will partition our space of closed \(k\)-forms into equivalence classes. So instead of talking about a specific form \(\omega\), we will consider the equivalence class<br><br>\([\omega] := \{\varphi \in \mathbf{C}^k : \omega - \varphi = d\phi\) for some \(\phi \in \mathbf{C}^{k-1}\}\).<br><br>We can then say that \([\omega] = [\varphi]\) for such forms \(\varphi\).<br><br>Notice that constructing this equivalence relation is exactly what we get when we define the following quotient group. <br><br>Let's first define a couple of subspaces of \(\mathbf{C}^k(M)\) when \(M\) is a smooth manifold with or without boundary. <br><br> \begin{align*}<br />\mathcal{Z}^k(M) &:= \{{\rm closed } \ k{\rm -forms \ on } \ M\},\\ <br />\mathcal{B}^k(M) &:= \{{\rm exact } \ k{\rm -forms \ on } \ M\}.<br />\end{align*} <br /> <br><br>Because \(d: \mathbf{C}^k(M) \to \mathbf{C}^{k+1}(M)\) is linear, its kernel and image are linear subspaces. Together with the fact that every exact form is closed, we may define the de Rham cohomology group in degree \(k\) as the following.<br><br>\(\color{purple}{\mathbf{Definition.}\ (de\ Rham\ cohomology\ group)}\) We define the \(pth\) de Rham group of \(M\) to be the quotient vector space<br><br>\begin{align*}<br>H^k_{dR}(M) &= \mathcal{Z}^k(M)/\mathcal{B}^k(M).<br>\end{align*}<br><br>Notice that the diference between an exact form and the form which always returns the number \(0\) is an exact form. Thus, if \(\omega \in C^k\) is exact, then \(\omega\) is equivalent to zero in \(H_{dR}^k(M)\).<br><br>To get our hands a little dirty, let's try to reason out what we can get for \(H^0(M)\) when \(M\) is a smooth manifold. So let's begin by asking, when is a \(0\)-form closed? Recall that \(0\)-forms on \(M\) are just functions \(\varphi: M \to \mathbb{R}\) which assign to every point in \(M\) a real number.<br><br>Thus, in local coordinates,<br><br>\begin{align*}<br>df &= \frac{\partial \varphi}{\partial x_1}dx_1 + ... + \frac{\partial\varphi}{\partial x_n}dx_n.<br>\end{align*}<br><br>Hence, a \(0\)-form \(\varphi\) is closed if and only if its first partial derivatives vanish. That is, if it is locally constant. The only way for a locally constant function \(M\) to <i>not</i> be constant on \(M\) is for \(M\) to have multiple connected components, say, \(M_1, M_2, ..., M_m\). The most general such functions are \(\varphi_i\) which take on the constant values \(c_i\) on \(M_i\) and \(0\) elsewhere, for each \(1\leq i \leq m\). <br><br>Now, if we are trying to find exact \(0\)-forms, we must be able to have \((-1)\)-forms, which do not exist! Therefore we have \(\mathcal{B}^0(M) = \{0\}\), the trivial group. <br><br>Hence, <br><br>\begin{align*}<br>H^0_{dR}(M) &= \mathcal{Z}^0(M)/\mathcal{B}^0(M)\\<br>&= \mathcal{Z}^0(M)/\{0\}\\<br>&\simeq \mathcal{Z}^0.<br>\end{align*} <br><br>This implies that \(H^0_{dR}(M)\) is isomorphic (i.e., algebraically the same) to the space of locally constant functions on \(M\). This space has dimension equal to the number of components \(M\) has; in our case, dimension \(m\). <br><br>Then, how do we know if a closed \(k\)-form is exact if it depends on the underlying space? We do have the following wonderful theorem!<br><br>\(\color{red}{\mathbf{Theorem.}}\) Let \(S\) be a \(k\)-dimensional manifold, \(M\) a smooth manifold, and let \(\omega\) be a differential \(k\)-form on \(M\). If<br><br>\begin{align*}<br>\int_S\phi^\ast\omega = 0<br>\end{align*}<br><br>for every map \(\phi: S\to M\), then \(\omega\) is exact.<br><br>Let's investigate what this theorem is saying by first looking at a slight variation of its statement for \(k = 1\). Let \(\varphi\) be a 1-form on \(M\). If \(\int_{\gamma}\varphi = 0\) for all closed curves \(\gamma\), then \(\varphi\) is exact.<br><br>If we consider some \(k\)-dimensional smooth manifold \(S\) and a smooth manifold \(M\), what the theorem is saying is that \(\omega\) is exact only if its \(\it{pullback}\) by all maps \(\phi:S\to M\) integrate to zero.<br><br>The pullback by \(\phi\) is a \(k\)-form \(\phi^\ast \omega\) on \(S\). The intuition for considering different \(\phi\)'s is that they move \(S\) around in \(M\), and considering \(\phi^\ast\omega\), let's us look at the form \(\omega\) on these different images of \(S\) in \(M\). This is very much like considering all different k-dimensional manifolds \(S\) in \(M\), and looking at what \(\omega\) integrates to over all these different manifolds.<br></div>Enrique Alvaradohttps://plus.google.com/109586990157816696262noreply@blogger.com0tag:blogger.com,1999:blog-5199045761147828305.post-58038714871266932652016-01-06T20:27:00.000-08:002016-01-06T20:39:44.796-08:00Dissemination of Math in the internet age<div dir="ltr" style="text-align: left;" trbidi="on"> <p> I'm at the <a href="http://jointmathematicsmeetings.org/meetings/national/jmm2016">Joint Mathematics Meetings</a> in Seattle. One of the first talks (8:00 AM!) of the first day was given by <a href="https://gowers.wordpress.com/">Prof. Tim Gowers</a> on <a href="http://jointmathematicsmeetings.org/meetings/national/jmm2016/2181_program_ss65.html#1711">How might Mathematics be better disseminated</a> (slight change in the title from what was originally published). Prof. Gowers highlighted several themes on <i>better</i> ways of doing mathematical research as well as <i>better</i> ways of disseminating the same, which he has been working on, and popularizing on the web, in recent years. Here are some of my <b>own</b> interpretations of what he talked about. </p> <p> In the current setting of mathematical research, most emphasis is on being the "first to prove the theorem", and the basic unit of discourse is the peer-reviewed journal article. There are more than a few things wrong with this set up, the main one being that the wheel is reinvented repeatedly! Here is a type of result which could be very useful. <i>If Lemma A is true, then BIG RESULT B is true, which would be fantastic news!. But, I have a counterexample for Lemma A</i> :-(. Unfortunately, such a negative result cannot be "published" in a peer-reviewed journal article. Hence, others fumble around and reinvent the same result! </p> <p> Another major drawback of the current system is that mathematical conversation happens at an inordinately slow pace. Someone proves a theorem, which appears in the journal in two years time. Then someone else reads it, comes up with a modification or a simpler proof, which appears in another journal two more years later! But in the current internet age, it's only natural to expect conversations occurring at a much faster pace (live tweets, any one?). </p> <p> While electronic publication has made all research easily searchable, the search capacity is strong only in one direction, so to speak. If you know what you're looking for in terms of keywords, then it's easy to find it by search, e.g., you want to know what <A href="https://en.wikipedia.org/wiki/Szemer%C3%A9di's_theorem">Szemerédi's theorem</a> states, a quick search pulls up multiple relevant web pages. What would be very useful is a way to search "in reverse" using some limited keywords or partial statements (and not the name itself!) to see if such a result is already known. In other words, the community needs a mathematics research database that allows <A href="https://en.wikipedia.org/wiki/Semantic_search">semantic search</a>. Today, forums such as the <a href="http://mathoverflow.net/">mathoverflow</a> often gets us accurate answers to questions of the form "has this been done before?". </p> <p> In current times, mathematics research should use the internet - both for conducting it as well as to disseminate it. But someone having a high rating on the <a href="http://math.stackexchange.com/">Math StackExchange</a> for posting numerous answers, or who writes popular blog articles on otherwise difficult to understand math papers, is not rewarded for these activities in the current system. To get tenure, you better have the required number of papers in the top(-enough!) journals! One could have a potentially huge impact by writing easy-to-understand expository blog posts on otherwise hard-to-read set of mathematical papers written by other authors. These blog posts could in turn spur new contributions from others, who would not have had the inclination otherwise to digest the original papers. As such, this effort could potentially be worth much more than publishing a paper with a new theorem! But then again, the current system has no means of rewarding such expository efforts. </p> <p> In follow-up conversation, Prof. Gowers agreed that senior/reputed mathematicians such as himself could afford to spend more time and effort on such endeavors on the internet without worrying about the rewards or evaluations. For tenure-track faculty or other junior researchers, the best course might well be to do <i>both</i> - publish via the conventional means, but also spend some effort on internet-based activities. Further down the line, we as a community would want to be able to judge how "impactful" a series of blog posts have been, so as to reward the same. But we must be careful not to go down the same path as overusing journal impact factors (so, don't judge the impact of a blog post by the number of times it has been re-tweeted, or +1-ed!). </p> <p> In the latter part of the talk, Prof. Gowers highlighted four of his personal efforts in this regard - a reform of the journal system (<a href="https://submissions.scholasticahq.com/sites/discrete-analysis">Discrete Analysis</a>), informal mathematical writing (via his <a href="https://gowers.wordpress.com/">blog</a>), <a href="http://polymathprojects.org/">polymath</a> projects, and automating proof discovery. He also presented his ideas of what mathematics research would be like in 20-30 years from now, and then in 50-60 years from now. Not surprisingly, computers would be expected to do most of the heavy (and light:-) lifting in the future. </p> <p> A question from the audience inquired about the place of real, i.e., face-to-face, conversations on mathematics that happen at conferences. Would there be less of a place for them in mathematics research in the future? While agreeing that such conversations have their place, Prof. Gowers observed that may be the back-and-forth postings on a polymath project (with time-stamps!) allows the posters the time to understand the subject better, and think through before posting what they want to post. An instant face-to-face conversation would not give that luxury! </p> <p> In summary, much need to be changed for mathematics research to be done right and be impactful in the internet age. Individual researchers need to be a bit bold, and not worry too much about rewards and ratings when spending time and effort on the internet. The more people who do so, the sooner the inevitable transition would happen! </p> </div>Bala Krishnamoorthyhttps://plus.google.com/101928045873106846660noreply@blogger.com0tag:blogger.com,1999:blog-5199045761147828305.post-13254661820801465182015-11-04T21:01:00.000-08:002015-11-06T06:49:17.560-08:00Discrete optimization @ Oaxaca - II<div dir="ltr" style="text-align: left;" trbidi="on"> <head> <script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"> </script> </head> <p> Some snippets from days 2 and 3 at the <a target="_blank" href="http://www.birs.ca/events/2015/5-day-workshops/15w5006">BIRS-CMO Workshop on Discrete Optimization</a> in Oaxaca. </p> <p> <a href="http://www.math.washington.edu/~rothvoss">Thomas Rothvoss</a> presented his work on <a href="http://arxiv.org/abs/1404.0339">constructive discrepancy minimization for convex sets</a> (<a href="http://www.math.washington.edu/~rothvoss/slides/constructivediscrepancyminimization.pdf">slides</a> are available). The basic problem is that of assigning one of two colors \(\chi(i)\) to each \(i \in [n]:=\{1,\dots,n\}\) of \(n\) items represented by \(\{-1,+1\}\) such that for a system of sets \(\cal{S} = \{S_1,\dots,S_m\}\) with \(S_i \in [n]\) we minimize the maximum "mismatch", defined as the <i>discrepancy</i>: <br> <center> \( \rm{disc}(\cal{S}) = \min\limits_{\chi(i) = \pm 1} \max\limits_{S \in \cal{S}} \left| \sum_{i \in S} \chi(i) \right| \). </center> <br> I found the techniques developed fairly deep, and would find use in lots of applications (i.e., for proving results on other optimization problems; Thomas talked about an application to bin packing). We had previously looked at the somewhat related problem of <a href="http://www.optimization-online.org/DB_HTML/2008/10/2118.html">number partitioning</a>. There, we assign a set of integers \(\{a_1, \dots, a_n\}\) to two sets such that the sums of the numbers over the two sets are as close to each other as possible (the difference between these two sums is the <i>discrepancy</i> here). At the same time, the corresponding alternative definition of discrepancy given as <br> <center> \( \rm{disc'}(\cal{S}) = \min\limits_{\chi(i) = \pm 1} \sum\limits_{S \in \cal{S}} \left| \sum_{i \in S} \chi(i) \right|\) </center> <br> would make the problem sort of "easy" here. With that objective, one could prove that a random assignment of \(\pm 1\) would perhaps do as well as we can. Nonetheless, an appropriately defined notion of "weighted" discrepancy, where each element now has, say, nonnegative weights, would be interesting to consider. It appears a generalization to more than two colors would be interesting, but perhaps tricky to establish the building blocks of results. </p> <p> <a href="http://people.math.sfu.ca/~tamon/">Tamon Stephen</a> talked about a variant of the <a href="https://en.wikipedia.org/wiki/Hirsch_conjecture">Hirsch conjecture</a> using <a href="http://arxiv.org/abs/1503.05252">circuit diameter</a> of polyhedra, instead of the default <a href="https://en.wikipedia.org/wiki/Distance_%28graph_theory%29">graph diameter</a>. See the <a href="http://arxiv.org/abs/1503.05252">preprint</a> for an illustration of circuit distance between vertices of a polyhedron - unlike the graph diameter, it's not symmetric. The idea is that one is allowed to take "shortcuts" along the interior of the polyhedron along with the walks along the edges. In that sense, it's mixing the ideas of the default simplex method and the interior point method for solving linear programs (LPs). The authors show that the most basic counterexample to the Hirsch conjecture, the Klee-Walkup polyhedron, in fact satisfies the Hirsch bound. It would be interesting for software programs that solve LPs to be able to <i>seamlessly</i> and <i>intelligently</i> switch back and forth between interior point and simplex methods (a basic ability to do so is already provided by some of the state-of-the-art solvers) </p> <p> <a href="http://web.mit.edu/jvielma/www/index.html">Juan Pablo Vielma</a> talked about when are Minkowski sums good/bad in the context of formulations for unions of polyhedra, and for unions of convex sets in general (the slides should be up soon <a href="http://web.mit.edu/jvielma/www/presentations/">here</a>; but other versions are already available). For unions of polyhedra, aggregated formulations are often "short", but are not as tight as disaggregated ones (also termed extended formulations). The latter formulations are sharp/ideal, but are often too large in size (see the <a href="http://web.mit.edu/jvielma/www/publications/index.html#Mixed-Integer-Linear-Programming-Formulation-Techniques">excellent review</a> on MIP formulation techniques by JP Vielma, or lectures 5-7 from my <a href="http://www.math.wsu.edu/math/faculty/bkrishna/FilesMath567/S15/LecNotes/">IP class</a> for a shorter overview). This <a href="http://web.mit.edu/jvielma/www/publications/index.html#Embedding-Formulations-and-Complexity">interesting line of work</a> tries to find a better middle ground by finding the sharpest formulations that are not extended, i.e., without having to add extra variables. Things get very interesting when one considers unions of convex sets (in place of polyhedra)! </p> <p> </p></div>Bala Krishnamoorthyhttps://plus.google.com/101928045873106846660noreply@blogger.com0tag:blogger.com,1999:blog-5199045761147828305.post-24280331704852437092015-11-02T22:16:00.000-08:002015-11-02T22:16:55.197-08:00Discrete optimization @ Oaxaca - I<div dir="ltr" style="text-align: left;" trbidi="on"> <head> <script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"> </script> </head> <p> I'm at the <a target="_blank" href="http://www.birs.ca/events/2015/5-day-workshops/15w5006">BIRS-CMO Workshop on Discrete Optimization</a> in beautiful Oaxaca (in Mexico). Unlike other typical workshops, the organizers have tried hard to encourage lots of discussion and interactions among the participants - big props to <a target="_blank" href="http://www.math.ucdavis.edu/~deloera">Jesus De Loera</a> and <a target="_blank" href="https://sites.google.com/site/jonleewebpage/">Jon Lee</a>! I'm hoping to write snippets on talks/discussion that I found particularly interesting (yes, it'll be a biased view :-). </p> <p> The meeting started with an apt talk by <a target="_blank" href="http://www.columbia.edu/~dano/">Dan Bienstock</a> on LP formulations for polynomial optimization problems (based on <a href="http://arxiv.org/abs/1501.00288">this paper</a>; Dan has also posted the <a href="http://www.columbia.edu/~dano/talks/o15.pdf">slides</a>). He started with a motivating problem - the optimal power flow (OPF) problem, which motivates the use of the <a href="https://en.wikipedia.org/wiki/Treewidth">treewidth</a> of the intersection graph of the constraints as the parameter which controls the complexity of the proposed reformulation operator. And real-life power grids often have small treewidths. The reformulation operator produces linear programming approximations that attain provable bounds for mixed integer polynomial problems where the variables are either binary, or require \(0 \leq x_j \leq 1\). </p> <p> Informally, the intersection graph of a system of constraints has one vertex for each variable \(x_j\), and edge \((x_i,x_j)\) is present when both \(x_i\) and \(x_j\) appear in some constraint. The simple example of a subset sum (or knapsack) problem was insightful. With the single constraint being \(x_1+\dots+x_n \leq \beta\), a constraint graph could have \(n+1\) vertices \({0,1,\dots,n}\), with the \(n\) edges \((0,j)\) for each \(j\) corresponding to \(x_j\) (node \(0\) is a "dummy" node here). The treewidth of this "star" graph is \(1\). The other key trick employed is the use of binary variables to approximate a continuous variable \(0 \leq x \leq 1\) (attributed originally to <a href="http://en.wikipedia.org/wiki/Fred_W._Glover">Glover</a>). For a given error term \(0 < \gamma < 1\), we can approximate \(x \approx \sum_{j=1}^L \left(1/2^h\right) y_h\), where \(y_h\) are binary variables. With \(L = \lceil \log_2 (1/\gamma) \rceil \), we can get \(x \leq \sum_{j=1}^L \left(1/2^h\right) y_h \leq x + \gamma\). This step helps to get pure binary problems in place of the mixed integer problems. The treewidth gets blown up by \(L\), but things still work out nicely. This paper seems to have lots of nice and deep "tricks" (I hope to study it in detail). </p> <p> There were several other interesting talks, and a very interactive problem session to conclude the day. Oh, and I learned a new terminology used in the power industry from <A href="http://www2.isye.gatech.edu/~sahmed/">Shabbir Ahmed's</a> talk: a <i>prosumer</i> is someone who both produces and consumes power. I'm wondering why that is more apt than a <i>conducer</i>... </p> <p> There was some lively discussion over dinner about how the optimization and operations research communities have failed to sell itself as well as the CS community (as a whole, or even the CS theory community by itself). Large membership sizes of <a href="http://www.acm.org/">ACM</a> vs <a href="http://www.informs.org">INFORMS</a> and similarly large NSF budgets for CS vs OR were cited as indicators. There was also an anecdote mentioned about how back in the 1980s when NSF funding for algorithms/CS theory was on the decline, a group of several top big names from that field submitted a memo/petition to the lawmakers in DC, and also convinced them in person that "algorithms/theory is as fundamental as cosmology" (needless to say, I'm paraphrasing to a huge extent here!). And yes, they managed to restore the funding flow. The optimization community tried a bit of the same trick with <A href="https://en.wikipedia.org/wiki/Narendra_Karmarkar">Karmarkar's</a> interior point algorithm for LP. May be we optimizers should try harder - not just from the point of view of securing funding, but also from the point of view of our students getting better industry jobs! </p></div>Bala Krishnamoorthyhttps://plus.google.com/101928045873106846660noreply@blogger.com0tag:blogger.com,1999:blog-5199045761147828305.post-49570806809375780512015-09-12T01:15:00.001-07:002015-09-12T09:11:39.238-07:00Math of Data Science @ ICERM<div dir="ltr" style="text-align: left;" trbidi="on"><div dir="ltr" style="text-align: left;" trbidi="on"><br /></div><span style="color: #ea9999;"><b>Note:</b> This is a re-post of the blog post I wrote originally on <a href="http://www.wordpress.com/">WordPress</a> last month. It appears that Blogger is a much better platform for the kind of posts I'd like to make. Yes, I'm still learning ...</span> <br /><br /><p>I recently attended the topical workshop on <a href="https://icerm.brown.edu/topical_workshops/tw15-6-mds/" target="_blank">Mathematics in Data Sciences</a> at <a href="http://www.icerm.brown.edu/" target="_blank">ICERM</a>. The attendance was good mix of students, postdocs, and researchers/faculty from academic institutions and national labs along with a sizable number of industry folks. The line of talks involved a similar mixture as well (abstracts/slides from many of the talks are available from the workshop page linked above). In particular from the industry side, there were talks from data scientists (or "engineers" with similar roles) from <a href="http://www.ayasdi.com target=">Ayasdi</a>, <a href="http://linkedin.com/" target="_blank">LinkedIn</a> (formerly), <a href="http://www.netflix.com/" target="_blank">Netflix</a>, <a href="http://www.nytimes.com/" target="_blank">New York Times</a>, and <a href="http://www.slb.com/about/rd/research/sdr.aspx" target="_blank">Schlumberger-Doll</a>, to name a few. Indeed, I found this diversity a direct indicator of the young age of the discipline in question, i.e., <a href="https://en.wikipedia.org/wiki/Data_science" target="_blank">data science</a>. And yes, the usual jokes about data science/big data were not spared, including the one about how big data is like teenage sex, how big data is very much a man's game since you usually hear men boasting "my data is bigger than yours", and how data scientists are mostly data janitors! </p><p>Coming from the academic side, what I found most interesting at this workshop were the panel (and open) discussion sessions. In the first such discussion, the group tried to come up with a (not so short!) list of topics that a program in data science should train the (undergraduate/masters) student in. After starting with the usual suspects such as calculus and linear algebra, probability and statistics, algorithms, machine learning, and databases, the group expanded the scope. Next came high dimensional geometry, information theory, data visualization/exploration, experimental design, and communication/business "skills". But many in the audience appeared to be surprised by the suggestion of a class on inverse problems, and electromagnetism (yes!). The topics and then associated skills to be taught soon filled up two large panels of white board (recall the "teenage sex" joke, any one?). To wrap up the session, it was suggested that the student be trained (at least) in Python, GitHub, Sql (or something similar), all from the point of view of industry readiness. As far as the mathematicians are concerned, it was suggested that they could start by making a wish list of all results (related to data science) one wants to see as theorems, and such a list will keep them busy for more than a life time. But to see any such effort make huge impact, one should ideally work with a domain expert. One particular subtopic of much importance in this con<b>text</b> (no pun intended!) is that of textual data - very important for data science, and as yet not well explored by mathematicians. </p><p>The panel discussion about careers in data science was quite popular as well. A majority of the panelists were junior (read "young") data scientists from the industry, and were able to shed a lot of light on what a typical work day looks like for a data scientist. One aspect of their work that particularly appealed to me (coming from traditional academia) is how quickly and directly they are able to see the impact of their ideas and work. For instance, a data scientist in a social media company could brainstorm for 2 hours, write the code in 2 more hours, and see thousands of users enjoying the benefits before the end of the day! On the other hand, academicians often wait years, if not months, to just count citations of their papers. </p><p>If there was one take home message from the data scientists to (young and old) aspirants, it was to just play with data - of many types and from many sources, and not to worry so much about all the different classes/training (or proving theorems). Be ever-ready to dive into any data that you come across, manipulate/analyze it quickly, and get the first insights. </p><p>I'm not attempting to list any summary/thoughts on the Mathematics involved (as meant in the title of the workshop). The list of relevant Math/Stat/CS topics has been huge already, and is not getting any shorter in this era of data science. I doubt if we're going to precisely define what data science is any time soon! </p><p><br /></div>Bala Krishnamoorthyhttps://plus.google.com/101928045873106846660noreply@blogger.com0