TITLE: Subfields of Number Theory that aren't about prime numbers.
QUESTION [0 upvotes]: A friend of mine who knows more mathematics that I do, told me that nowadays number theory is basically about studying prime numbers.
I'm under the impression that solving diophantine equations and cryptography for example are subfields of number theory.
I'm under the impression that although at first glance these subfields dont seem to have anything to do with prime numbers, prime numbers play a central role in them. (is this true?)
So it seems that in certain subfields of number theory that aren't directly about prime numbers, the researchers study and tackle their problems by studying prime numbers, and so prime numbers would be central in such subfields.
So I'm asking for examples of subfields of number theory that don't rely heavily/aren't prime number focused.
Thanks.

REPLY [0 votes]: As an approximation, analytic number theory is largely to do with studying the prime numbers, but algebraic number theory is not, for the most part.  Prime numbers (and prime ideals) are hugely important in algebraic number theory, but the field is not primarily concerned with things like the distribution of the prime numbers and which particular numbers are prime.
As an example, Fermat's Last Theorem was proved using techniques of algebraic number theory.  The weak Goldbach conjecture was proved using analytic number theory.


TITLE: Can one find 4024 positive integers such that the number "2013" cannot divide the sum of any 2013 of them
QUESTION [1 upvotes]: As stated on the title,

Is it possible to find $4024$ positive integers such that the sum of any $2013$ of them is not divisible by $2013$?

I used to assumed they have to be distinct. Being inspired by the answer below, I am thinking maybe we have to select those $4024$ numbers by two types: the first group of $2012$ integers being those that are divisible by $2013$, and the rest $2012$ integers are those not divisible by $2013$. So that if you pick any $2013$ of them you will end up having to pick at least $1$ of those $2012$ not-divisible-by-$2013$ integers. Does that work out?
If the numbers don't have to be distinct then the following suggestion seems to work well, but I am not sure whether they have to be distinct.  I will update the question if there are any changes.  Thank you guys.

REPLY [5 votes]: Half of them 1, half of them 2013.


TITLE: Failure of Baire Category Theorem if collection of sets is not closed or not countable.
QUESTION [2 upvotes]: The Baire Category Theorem implies that $\mathbb{R}^n$ cannot be written as the union of a countable collection of closed subsets having empty interior.
I was wondering how it can be showed that this fails if the sets are not specified to be closed, or the collection is not required to be countable.
Help is appreciated. Thanks

REPLY [4 votes]: If sets are not closed, you can get by with two sets: the irrationals and the rationals.
If the collection is not countable: all singletons.


TITLE: Unitaries $u$ span $A$ linearly?
QUESTION [1 upvotes]: I can't understand this paragraph in my book:
If $a$ is a self-adjoint element of the closed unit ball of a unital $C^\ast$-algebra $A$ then $1-a^2$ is positive and $u=a + i\sqrt{1-a^2}$ and $v = a - i\sqrt{1-a^2}$ are unitaries such that $a = {1\over 2}(u+v)$. Therefore the unitaries linearly span $A$.
I really don't see how it could be true that unitaries linearly span $A$. If $a\in A$ is any not self-adjoint element, then $u,v$ are not unitary. And I don't see how such $a$ can be written as a linear combination of unitaries. Please could someone shed some light?

REPLY [2 votes]: As an example for better understanding, consider the case where $A=\mathbb C$. Then, for a fixed $z\in\mathbb C$, you write $$z=\sqrt{a^2+b^2}\left(\frac a{\sqrt{a^2+b^2}}+i\frac b{\sqrt{a^2+b^2}}\right),$$ with $a,b\in\mathbb R$. Since
$$
-1\leq \frac a{\sqrt{a^2+b^2}}\leq1,
$$
there exists $\theta$ such that $\frac a{\sqrt{a^2+b^2}}=\cos\theta$. Similarly, there exists $\phi$ such that $\frac b{\sqrt{a^2+b^2}}=\cos\phi$. So
$$
z=\sqrt{a^2+b^2}\,\left(\cos\theta+i\cos\phi\right).
$$
Now we construct the unitaries (i.e. complex numbers of absolute value $1$ in this case)
$$
u_1=\cos\theta+i\sin\theta,\ \ u_2=\cos\theta-i\sin\theta,\ \ \ v_1=\cos\phi+i\sin\phi\ \ \ \ v_2=\cos\phi-i\sin\phi,
$$
and
$$
z=\frac{|z|}2\,(u_1+u_2+iv_1+iv_2)
$$
is a linear combination of four unitaries.


TITLE: Prime factor question and geometry
QUESTION [0 upvotes]: I have a shape that is less than 9 sides. The sum of its interior angles is divisible by 16. How many sides does this shape have?
So, here's how I started thinking about this problem. The formula for interior angles is 180(n-2) where is the number of sides.
So,
If the shape is a triangle, then the sum of its interior angles is 180(1) = 180.
If the shape is a square, then the sum of its interior angles is 180(2) = 360.
If the shape has 5 sides, then the sum of its interior angles is 180(3) = 540.
So the numbers are multiples of 180.
So, which is these numbers is divisible by 16? I'm trying to think of a fast way to do this.
180's prime factors are let's see... : 9 * 20 = 3 * 3 * 10 * 2 = 3 * 3 * 5 * 2 * 2
16's prime factors are : 2 * 2 * 2 * 2
Is there a fast way for me to do this with prime factor and divisor rules? I seem to have forgotten how to go from here.

REPLY [0 votes]: Hmmm... I'm trying to comprehend Calvin's hint. I don't think the hint is registering with me because I seem to have forgotten rules about prime factorization.
So the question is just this:
180(n-2) is divisible by 16 and n < 9. What is n?
Again the prime factors of 180 are = 90 * 2 = 10 * 9 * 2 = 2 * 3 * 3 * 5 * 2
And the prime factors of 16 are = 8 * 2 = 4 * 2 * 2 = 2 * 2 * 2 * 2.
I remember this being the first step in figuring out if a number is divisible by another, but I forget how to proceed. and why?


text:
{\bf Problem.} In triangle $ABC,$ $\angle B = 30^\circ,$ $AB = 150,$ and $AC = 50 \sqrt{3}.$  Find the sum of all possible values of $BC.$
{\bf Level.} Level 3
{\bf Type.} Precalculus
{\bf Solution.} By the Law of Sines,
\[\frac{AB}{\sin C} = \frac{AC}{\sin B},\]so
\[\sin C = \frac{AB \sin B}{AC} = \frac{150 \sin 30^\circ}{50 \sqrt{3}} = \frac{\sqrt{3}}{2}.\]Hence, $C = 60^\circ$ or $C = 120^\circ.$

If $C = 60^\circ,$ then $A = 180^\circ - 30^\circ - 60^\circ = 90^\circ.$  Then by Pythagoras,
\[BC = \sqrt{150^2 + (50 \sqrt{3})^2} = 100 \sqrt{3}.\]if $C = 120^\circ,$ then $A = 180^\circ - 30^\circ - 120^\circ = 30^\circ.$  Then by the Law of Cosines,
\[BC = \sqrt{150^2 + (50 \sqrt{3})^2 - 2 \cdot 150 \cdot 50 \sqrt{3} \cdot \cos 30^\circ} = 50 \sqrt{3}.\]Thus, the sum of all possible values of $BC$ is $\boxed{150 \sqrt{3}}.$

set_name: MATH


TITLE: Set of fixed points by a continuous function is closed
QUESTION [0 upvotes]: Let $X$ be a Hausdorff space, and $f:X \to X$ continuous. Then the following set is closed in $X$:
$$B=\{x \in X;f(x)=x\}$$
I saw that question that says to consider $g:X \to X \times X$ with $g(x)=(x,f(x))$, and I could do it by arguing that $g(B)=\Delta = \{(x,x);x \in X\}$ and showing that $\Delta$ is closed. But that argument depends on $g$ being a continuous function. How can I show that?

REPLY [2 votes]: You can also give a direct proof: suppose that $p \notin B$ so that $f(p) \neq p$. As $X$ is Hausdorff, there are open sets $U_p, U_{f(p)}$ such that $p \in U_p, f(p) \in U_{f(p)}, U_p \cap U_{f(p)} = \emptyset$. As $f$ is continuous, $f^{-1}[U_{f(p)}]$ is an open neighbourhood of $p$ as well and we define $O_p = U_p \cap f^{-1}[U_{f(p)}]$, which is thus an open neighbourhood of $p$ too. One easily checks that $O_p \cap B = \emptyset$ and so as $p \notin B$ was arbitrary, $B$ is closed.
$g$ in your question is continuous because $\pi_1 \circ g = 1_X$ and $\pi_2 \circ g = f$ are both continuous, using the universal property for continuity of maps into a product.


text:
The purpose of this section is to prove theorem 1. We start with a reformulation of our result in terms of edge-coloring of graphs and explain how it fits into the context of previous results of Bruhn and Stein. Our theorem actually is a corollary of a slightly stronger coloring result that we prove in the second part of the section.

\subsection{Reducing to an edge-coloring problem}

Let $G$ be a graph. The line graph of $G$ is denoted $L(G)$ and is defined as follows: the vertex set of $L(G)$ is $\eds{G}$ and $u,v\in E(G)$ are adjacent in $L(G)$ if and only if they are incident in $G$. We say that $G$ is a line graph if there exists a graph $H$ such that $G$ is isomorphic to $L(H)$.

Cao and Nemhauser characterized the h-perfectness of $L(G)$ (among other notions of perfectness) in terms of excluded subdivisions in $G$. We need a few more definitions.

Let $C_5^{+}$ be the graph defined by $\vts{C_5^{+}}=\set{1,2,\ldots,5}$ and $\eds{C_5^{+}}=\set{12,23,34,45,15}$. In other words, $C_5^{+}$ corresponds to the 5-circuit to which we added a chord.

A graph $H$ is a subdivision of $G$ if it is obtained by replacing every edge $e$ with a path $P_e$ joining the ends of $e$, such that the paths $P_e$ ($e\in\eds{G}$) are pairwise-inner-disjoint. Furthermore, it is a totally odd subdivision if each $P_e$ has odd length

A totally odd subdivision of $C_5^{+}$ is said to be an odd-$C_5^{+}$. Now, a graph $G$ is odd-$C_5^{+}$-free if it does not have a subgraph isomorphic to an odd-$C_5^{+}$.

\begin{thm}[Cao, Nemhauser]
Let $G$ be a graph. The following statements are equivalent:
\begin{itemize}
\item [i)] $L(G)$ is h-perfect,
\item [ii)] $G$ is \cfpfree.
\end{itemize}
\end{thm}

Hence, coloring the vertices of an h-perfect line graph corresponds to color the edges of a \cfpfree graph. Let us recall the basic terminology of edge-coloring.

A matching of a graph $G$ is a set of pairwise non-incident edges of $G$. A $k$-edge-coloring of $G$ is a set of $k$ pairwise-disjoint matchings of $G$ whose union is $\eds{G}$. We say that $G$ is $k$-edge-colorable if it admits a $k$-edge-coloring.
The chromatic index of $G$, denoted $\chi'(G)$, is the smallest integer $k$ such that $G$ has a $k$-edge-coloring. In particular, $\chi(L(G))=\chi'(G)$.
The fractional chromatic index of $G$, denoted $\chi_f'(G)$, is defined as the fractional chromatic number of $L(G)$: $\chi_f'(G)=\chi_f(L(G)$.

Using the above characterization of Cao and Nemhauser, Bruhn and Stein proved the round-up property for h-perfect line graphs in the unweighted case. Let us state their result in terms of edge-colorings:

\begin{thm}[Bruhn, Stein]
Every \cpfree graph $G$ satisfies $\chi'(G)=\ceil{\chi'_f(G)}$.
\end{thm}

Now, let us see how a problem of weighted coloring can be formulated as a edge-coloring problem.
Let $G$ be a graph and $c\in\zset_+^{\vts{G}}$.
It is straightforward to check that

Our proof of the weighted case does not use Seb\H{o}'s lemma and entirely relies on edge-colorings.  The first step is reformulate the statement in terms of edge-colorings using theorem REF.

Bruhn and Stein proved the unweighted case of theorem 1:

\begin{thm}
Every h-perfect line graph $G$ satisfies: $\chi(G)=\ceil{\chi_f(G)}$.
\end{thm}

Their proof proceeds as follows: let $H$ be a graph such that $G=L(H)$.

Cao and Nemhauser characterized the h-perfectness of $L(G)$ in terms of the structure of $G$. Their result was already used by Bruhn and Stein to prove the unweighted case of theorem 1:

\subsection{The proof}

We actually prove a slightly stronger result

Let $G$ be a graph. The multiplicity $\mu_G(e)$ of an edge $e$ of $G$ is the number of edges which are parallel to $e$ (including $e$).
If $\ecol$ is an edge-coloring of $G$, we will always

\begin{lem}\label{lem-precol}
Let $G$ be a graph such that $\chi'(G)>\Delta(G)$ and let $e=uv$ be a critical edge of $G$. If $\ecol$ is an optimal edge-coloring of $G-e$, then:
\begin{itemize}
\item [i)] Every matching $M\in\ecol$ either covers $u$ or $v$,
\item [ii)] There exist two $A,B\in \ecol$ such that $A$ covers $u$ and misses $v$, whereas $B$ covers $v$ and misses $u$.
\end{itemize}
\end{lem}
\begin{dem}
We first prove i): by contradiction, if there exists a color $C$ of $\ecol$ which misses $u$ and $v$,
then we can extend $\ecol$ to an edge-coloring $\ecol'$ of $G$ by adding $e$ to $C$. Since $|\ecol|=|\ecol'|$, we have $\chi'(G)\leq \chi'(G-e)$: a contradiction with the criticality of $e$.

We now show that ii) holds. Let $\ecol_u$ (resp. $\ecol_v$) denote the set of $M\in \ecol$ covering $u$ (resp. $v$) and missing $v$ (resp. $u$). By the symmetry between $u$ and $v$, it is enough to prove that $\ecol_u\nsubseteq\ecol_v$ to conclude. Seeking a contradiction, suppose $ \ecol_u\se\ecol_v $.
Using i), we have:
\[ \chi'(G-e)=|\ecol_u\cup\ecol_v|+\mu_{G-e} (e)=|\ecol_v|+\mu_{G-e}(e)=d_{G-e}(v) =d_{G}(v)-1. \]
Hence, $\chi'(G-e)\leq \Delta(G)-1$. But since $e$ is critical we have $\chi'(G-e)=\chi'(G)-1$. Hence $\chi'(G)\leq \Delta(G)$, which contradicts our initial assumption on $G$.
\end{dem}

Let $G$ be a graph and $M$ be a matching of $G$. A chain of $G$ is \emph{$M$-alternating} if its edges consecutively alternate between $M$ and $\eds{G}\sm M$.

A \emph{ring} of $G$ is an induced subgraph of $G$ whose underlying simple graph is a circuit. A ring is \emph{odd} if it has an odd number of vertices.

Let $G$ be a graph, $C$ an odd ring of $G$. A $C$-matching of $G$ is a matching $M$ such that $|\eds{C}\cap M|=\dfrac{|C|-1}{2}$ and $M$ misses a (necessarily unique) vertex of $C$.

Let $G$ be a graph. If $F\se\eds{G}$, let $\psbg{G}{F}$ denote the graph $(\vts{G},F)$.

We will often use the following classic lemma.

\begin{lem}
Let $G$ be a graph, $\ecol$ be an edge-coloring of $G$ and $A,B$ be distinct elements of $\ecol$.

If $K$ is a connected component of $\psbg{G}{A\Delta B}$, then $ (\ecol\sm\set{A,B})\cup\set{A\Delta \eds{K},B\Delta \eds{K} } $ is an edge-coloring of $G$ which uses the same number of colors as $\ecol$. We will denote it by $\ecol^{K}$.
\end{lem}

Our main result is as follows:

\begin{thm}\label{thm-main}
Let $G$ be a graph such that $\chi'(G)>\Delta(G)$.
If $e$ is a critical edge of $G$, then one of the following statements holds:
\begin{itemize}
\item [i)] $e$ is contained in an odd-$C_5^+$ of $G$,
\item [ii)] $e$ is contained in an odd ring $R$ of $G$ such that:
\[ |\eds{R}|= (\chi'(G)-1)r+1, \]
where $r=\dfrac{|\vts{R}|-1}{2}$.
\end{itemize}
\end{thm}

\begin{dem}
Let us assume that $e$ is not contained in an odd-$C_5^+$ of $G$. We will prove ii).
Let $u$ and $v$ be the ends of $e$, $H:=G-e$ and $\ecol$ be an optimal edge-coloring of $H$. Notice that we are under the assumptions of \myref{lem-precol}.
By its second point, there exist distinct matchings $A,B\in\ecol$ such that $A$ covers $u$ and misses $v$, whereas $B$ covers $v$ and misses $u$.

Consider the connected component $P$ of $u$ in the graph $\psbg{H}{A\Delta B}$. It is either a chain or a circuit, but $B$ misses $u$ so it must be a chain.

If $v\notin\vts{P}$, then $(\ecol\sm\set{A,B})
\cup\set{A\Delta \eds{P},B\Delta\eds{P}}$ is an optimal edge-coloring of $G$ in which $e$ is not incident with the color class $A\Delta\eds{P}$. It can therefore be extended in an edge-coloring of $G$ with $\chi'(G-e)$ colors: a contradiction with the criticality of $e$.
Hence $P$ is a $uv$-chain and the graph $L:=P+e$ is an odd circuit of $G$. It is also induced: if $f$ is a chord of $L$, then $L+f$ forms an odd-$C_5^+$ containing $e$, which contradicts our initial assumption on $e$.
Hence $L$ is contained in an odd ring $R$ of $G$. Let $r=(|R|-1)/2$. We claim that:
\begin{center}
\emph{$R$ contains exactly $r$ edges of each color $M$ of $\ecol$.}
\end{center}
Let us immediately show how this statement allows us to end the proof of the theorem: every edge of $R$ except $e$ belongs to one of the color classes of $\ecol$ and these are disjoint.
Thus, the claim implies $|E(R)|=|\ecol| r+1=\chi'(G-e)\cdot r+1$, and the equality of the theorem follows from $\chi'(G-e)=\chi'(G)-1$, which holds because $e$ is critical.

We now turn to the proof of the claim above.
Let $M\in\ecol$.

If $M$ is either $A$ or $B$, then $M$ has $r$ edges in $R$ because $|\vts{L}|=|\vts{R}|=2r+1$ and the edges of $P$ alternate  between $A$ and $B$.
So let us henceforth assume that $M\notin\set{A,B}$.

Using the symmetry between $u$ and $v$, we may assume (without loss of generality) that $M$ covers $u$.
Let $K$ be the component of $u$ in $\psbg{G}{M\Delta B}$. The graph $K$ is a chain since $B$ is an $R$-matching of $G$ which misses $u$.
We claim that:
\begin{center}
\emph{the graph $K\cap R$ is an even chain.}
\end{center}

Indeed, if $K\cap R$ has more than one connected component then $K$ contains an ear $P'$ of $L$ with both  its end-edges in $M$. Hence $P'$ is an odd ear of $L$ (the edges of $K$ alternates between $M$ and $B$) and $L+P'$ forms an odd-$C_5^{+}$ of $G$ containing $e$: a contradiction. So $K\cap R$ is a chain.
Now, $B$ is an $R$-matching so the end of $K\cap R$ other than $u$ (if it exists) must be covered by $B$ in $K\cap R$. Therefore $K\cap R$ has even length and this ends the proof of the claim above. It follows that :
 \[ |M'\cap \eds{R}|=|M\cap \eds{R}|, \]
where $M':=M\Delta K$.

We now prove that $M'\cap R$ has $r$ edges in $R$.

Let $B'=B\Delta \eds{K}$  and $\ecol'=\ecol\sm\set{M,B}\cup\set{M',B'}$. Using lemma 3, we have that $\ecol'$ is an edge-coloring of $G-e$ with $|\ecol|=\chi'(G-e)$ colors and that $M'$ misses $u$. So $M'$ must cover $v$:  we could otherwise extend $\ecol'$ to an edge-coloring of $G$ by adding $e$ to $M'$, which would contradict $\chi'(G-e)<\chi'(G)$.

Let $K'$ be the component of $v$ in $\psbg{G}{M'\Delta A}$. By construction, $A$ is an $R$-matching of $G$ which misses $v$.
Hence, we can repeat the argument of the claim above to show that $Q:=K'\cap R$ is a chain.
If $u\notin K'$, then let $M''=M\cap \eds{K'}$, $A'=A\cap \eds{K'}$ and $\ecol''=\ecol'\sm\set{M',A}\cup\set{M'',A'}$.
As above, we apply lemma 3 to show that  $\ecol''$ is an edge-coloring of $G-e$ which uses $\chi'(G-e)$ colors. However, no edge of $M''$ is incident with $e$. It follows that $\ecol''$ can be extended to an edge-coloring of $G$ by adding $e$ to $M''$, which again contradicts $\chi'(G-e)<\chi'(G)$.

Hence, $u$ must belong to $K'$. Since $uv\notin M'$  (because $M'$ misses $u$), the only way for $Q$ to be a chain is that it coincides with the underlying simple graph of $R-e$. Therefore $|M'\cap R|=|M'\cap Q|=r$, because $Q$ is $M$-alternating and of even length.

\end{dem}

A graph $G$ is rounding-critical if $\chi'(G)>\kappa(G)$ and $\chi'(G-e)=\kappa(G-e)$ for every $e\in\eds{G}$.

For every graph $H$, let $\kappa(H)=\ceil{\chi'_f(H)}$. It is an easy exercise to show that $\kappa(H_1)\leq \kappa(H_2)$ whenever $H_1$ is a subgraph of $H_2$.

\begin{thm}
Let $G$ be a rounding-critical graph.
\end{thm}
\begin{dem}

Let $G$ be a rounding-critical graph. If $\eds{G}=\vn$, then the result is trivial. So let us assume that $|\eds{G}|\geq 1$ and let $e\in\eds{G}$. The edge $e$ is obviously critical, hence:
\[ \kappa(G-e)=\chi'(G-e)=\chi'(G)-1\geq \kappa(G)\geq\kappa(G-e). \]
So the inequalities above are equalities. In particular: $\kappa(G-e)=\kappa(G)$.

Seeking a contradiction, suppose that $e$ does not belong to an odd-$C_5^{+}$. By theorem \myrefwp{thm-main}, there exists an odd ring $R$ of $G$ such that $|E(R)|=(\chi'(G-e))r+1$, where $r=(|R|-1)/2$. Hence:
\[ \kappa(G-e)=\kappa(G)\geq \dfrac{|E(R)|}{r}=\chi'(G-e)+\dfrac{1}{r}>\chi'(G-e), \]
which contradicts $\chi'(G-e)=\kappa(G-e)$.

\end{dem}

The following corollary is a straightforward consequence of theorem 2.

\begin{thm}
If $G$ is a graph without an odd-$C_5^{+}$, then $\chi'(H)=\kappa(H)$.
\end{thm}

config: arxiv


text:
import algebra.category.Ring.basic
import data.polynomial

noncomputable theory -- the default implementation of polynomials is noncomputable

local attribute [irreducible] polynomial.eval₂

def Ring.polynomial : Ring ⥤ Ring :=
{ obj := λ R, Ring.of (polynomial R),
  map :=
  begin
    -- The goal is `Π {X Y : Ring}, (X ⟶ Y) → (Ring.of (polynomial ↥X) ⟶ Ring.of (polynomial ↥Y))`
    -- so we need to:
    intros R S f,
    -- The goal is now to provide a morphism in `Ring`
    -- from `Ring.of (polynomial R)` to `Ring.of (polynomial S)`.
    -- By definition this is a `ring_hom (polynomial R) (polynomial S)`,
    -- which can also be written `polynomial R →+* polynomial S`.

    -- The hint suggested looked at `polynomial.map`.
    -- If you type `#print polynomial.map` above, you'll see that it just provides a "bare function"
    -- `polynomial R → polynomial S`, rather than an actual `ring_hom`.
    -- Looking further in the same file, you can find its morphism version, called
    -- `polynomial.map_ring_hom`.

    apply polynomial.map_ring_hom,

    -- Now it's "downhill": we just tell Lean what we want to use:
    apply f,

    -- With the goals completed, you should now try to "golf" this proof to a term mode proof.
    -- The next hint file walks you through doing this.
  end, }

def CommRing.polynomial : CommRing ⥤ CommRing :=
sorry

open category_theory

def commutes :
  (forget₂ CommRing Ring) ⋙ Ring.polynomial ≅ CommRing.polynomial ⋙ (forget₂ CommRing Ring) :=
sorry

subset_name: curated


TITLE: Why the ODE $x'(t)=x^2(t)$ doesn't have solutions if $x(0)=x_{0}\neq 0$
QUESTION [0 upvotes]: I need help figuring out why the fisr order ODE : $x'(t)=x^2(t)$ with the initial condition  $x(0)=x_{0}\neq 0$ doesn't have a solution defined for all t.
Does anyone have an idea ?

REPLY [0 votes]: Nobody has said that any initial value problem you cook up will have a solution for all $t$ – in the same vein that you cannot expect a real solution for all equations of the form $x^2=c\in{\mathbb R}$.
On the positive side you can say the following: When the hypotheses of the existence and uniqueness theorem are satisfied throughout the domain $\Omega\subset{\mathbb R}^2$ of the given ODE $x'=f(x,t)$ then the graph of any "complete" solution will finally leave any given compact $K\subset\Omega$.
In the case at hand the graph of the solution $y(t)=x_0/(1-t x_0)$ will go off to $\infty$ when $t x_0\to 1-$.


TITLE: The sum $1!+2!+3!+...+2007!$ is not a perfect square
QUESTION [4 upvotes]: Today my teacher told me to prove this:-
Prove that $1!+2!+3!+...+2007!=\sum_{n=1}^{2007}(n!)  $ is neither a perfect square nor a perfect cube. Not getting any idea. Please help. Thanks in advance.

REPLY [0 votes]: Hint: What is your sum modulo $7$?  What are the possible squares and cubes modulo $7$?


TITLE: Is the interior of the closure of a set equal to the interior of that set?
QUESTION [4 upvotes]: I tried to prove that with the set being  subset of a space X with metric d,
" the interior of the closure of a set equal to the interior of that set".
I proved that the interior of,namely, $A$ is included in the interior of the closure of $A$. But I could not prove the reverse, in special because I think that there can be points that are limit points of A and is contained in the interior of the closure, am I wrong?
I am doing this to prove that the closure is equal to the union of the interior points of the closure with the set of all limit points of the set.
Is the aforementioned statement true?
Thank you.

REPLY [0 votes]: Think about the set $\mathbb R$$-${$0$}


TITLE: Name of Particular Constrained Optimization Problem
QUESTION [0 upvotes]: I am writing to ask if any of you know what is the name in the research literature of a particular constrained optimization problem I am facing. I would like to find a general name so that I can research better on the matter.
The problem in question is:
I have P persons that need to be assigned to T tasks (P>>T). Each person can be assigned to only one task. A particular person p_i has a different score (ability) to complete a task t_i. To simplify, let's assume the score distribution for each person p_i is a probability distribution over the tasks (sum to 1). Moreover, each task t_i has a precise capacity C_t_i which is the number of persons that must be assigned to the task. Pay attention that sum of C_t_i over i equals P so that all people can be assigned to one task. I want to find a feasible solution that maximizes the score.

P persons
T tasks
p_i must be assigned to only one task
t_i has a capacity C_t_i of people which must be assigned to t_i
sum_over_i (C_t_i) = P

This can be visualized in a matrix S (score matrix). Find in the table below an example of score matrix S:
----------------------------
|   \  T | t_1 | t_2 | t_3 |
| P  \   |     |     |     |
----------------------------
| p_1    | 0.1 | 0.2 | 0.7 | -> sum to 1
| p_2    | 0.9 | 0.1 | 0   | -> sum to 1
| p_3    | 0.1 | 0.1 | 0.8 |
| p_4    | 0.3 | 0.4 | 0.3 |
| p_5    | 0.2 | 0.2 | 0.6 |
----------------------------
| C      | 1   | 2   | 2   |
----------------------------

A feasible solution to the example is the following matrix, let's call it X:
----------------------------
|   \  T | t_1 | t_2 | t_3 |
| P  \   |     |     |     |
----------------------------
| p_1    | 1   | 0   | 0   |
| p_2    | 0   | 1   | 0   |
| p_3    | 0   | 0   | 1   |
| p_4    | 0   | 1   | 0   |
| p_5    | 0   | 0   | 1   |
----------------------------
| C      | 1   | 2   | 2   |
----------------------------

Which has a overall score of 0.1+0.1+0.8+0.4+0.6=2. There is of course a better solution with a higher score.
The problem can be re-written in mathematical formulas such as:
find matrix X
maximizing sum_over_i_j ( X.S ) for every i in rows and j in columns
such that sum_over_j (X_i) = 1 for every i in rows and j in columns
and sum_over_i (X_j) = C_t_j for every i in rows and j in columns

Where . is the point-wise multiplication between matrices.
Thank you guys

REPLY [1 votes]: This is called the transportation problem.  The people are the supply nodes, with a supply of $1$ unit each.  The tasks are the demand nodes, with demand C_t_i.  The usual formulation has a minimization objective, but you can negative the objective function for maximization.


text:
\subsection{Appendix: Proof of Theorem \ref{stabres_simple_modcs}}
\label{proof_simple_modcs}

We prove the first claim by induction. Using condition \ref{initass_simple} of the theorem, the claim holds for $t=0$. This proves the base case. For the induction step, assume that the claim holds at $t-1$, i.e. $|\tDelta_{e,t-1}| =0$, $|\tT_{t-1}| \le S_0$, and $\tDelta_{t-1} \subseteq \Sset_{t-1}(2)$ so that $|\tDelta_{t-1}| \le 2S_a$. Using this assumption we prove that the claim holds at $t$. In the proof, we use the following facts often: (a) $\Rset_t \subseteq N_{t-1}$ and $\Aset_t \subseteq N_{t-1}^c$, (b) $N_t = N_{t-1} \cup \Aset_t \setminus \Rset_t$, and (c) if two sets $B,C$ are disjoint, then, $(D \cap B^c) \cup C = D \cup C \setminus B$ for any set $D$.

We first bound $|T_t|$, $|\Delta_{e,t}|$ and $|\Delta_t|$.
Since $T_t = \tT_{t-1}$, so $|T_t| \le S_0$. Since $\Delta_{e,t} = \Nhat_{t-1} \setminus N_t =  \Nhat_{t-1} \cap [(N_{t-1}^c \cap \Aset_t^c) \cup \Rset_t] \subseteq \tDelta_{e,t-1} \cup \Rset_t = \Rset_t$. The last equality follows since $|\tDelta_{e,t-1}| =0$. Thus $|\Delta_{e,t}| \le |\Rset_t| = S_a$.

Now consider $|\Delta_t|$. Notice that $\Delta_t = N_t \setminus \Nhat_{t-1}  = (N_{t-1} \cap \Nhat_{t-1}^c \cap \Rset_t^c) \cup (\Aset_t \cap \Rset_t^c \cap \Nhat_{t-1}^c) = (\tDelta_{t-1} \cap  \Rset_t^c) \cup ( \Aset_t \cap \Nhat_{t-1}^c) \subseteq  (\Sset_{t-1}(2)  \cap  \Rset_t^c) \cup  \Aset_t = \Sset_{t-1}(2) \cup  \Aset_t \setminus \Rset_t$. The second last equality uses $\tDelta_{t-1} \subseteq \Sset_{t-1}(2)$.
 Since $\Rset_t$ is a subset of $\Sset_{t-1}(2)$ and $\Aset_t$ is disjoint with $\Sset_{t-1}(2)$, thus $|\Delta_t| \le |\Sset_{t-1}(2)| + |\Aset_t| - |\Rset_t| = 2S_a + S_a - S_a = 2S_a$.

Next we bound  $|\tDelta_t|$, $|\tDelta_{e,t}|$ and $|\tT_t|$. Consider the support estimation step. Apply the first claim of Lemma \ref{lemma_modcs} with $S_N=S_0$, $S_{\Delta_e}=S_a$, $S_\Delta = 2S_a$, and $b_1 = 2r$. Since conditions \ref{measmodel_simple} and \ref{add_del_simple} of the theorem hold, all elements of $N_t$ with magnitude equal or greater than $2r$ will get detected. Thus, $\tDelta_t \subseteq \Sset_t(2)$. Apply the second claim of the lemma. Since conditions \ref{measmodel_simple} and \ref{threshes_simple} hold, all zero elements will get deleted and there will be no false detections, i.e. $|\tDelta_{e,t}|=0$. Finally using $|\tT_t| \le |N_t| + |\tDelta_{e,t}|$, $|\tT_t| \le S_0$.


TITLE: Are polynomials with positive coefficients convex in $[0,1]^d$?
QUESTION [2 upvotes]: Are polynomials of a given order with positive coefficients, for example
$$a+bx_1+cx_2+dx_3+ex_1x_2+fx_1^2x_3+gx_2^3$$
convex in $(x_1,x_2,x_3) \in[0,1]^3$? If not, is it convex in $1'x \le 1$ and $x \ge 0$?

REPLY [3 votes]: Convexity requires the Hessian matrix to be positive semidefinite. The Hessian matrix of the quadratic polynomial
$$
Ax_1^2 + 2Bx_1x_2 + Cx_2^2
$$
is precisely
$$\begin{pmatrix} A & B \\ B & C\end{pmatrix}$$
at every point $(x_1, x_2)$.
Is every symmetric matrix with positive entries positive-semidefinite? No, a counterexample being
$$\begin{pmatrix} 1 & 2 \\ 2 & 1\end{pmatrix}$$
which corresponds to
$$
x_1^2 + 4x_1x_2 + x_2^2 = (x_1+x_2)^2 + 2x_1x_2
$$
The lack of convexity can be seen directly by restricting this polynomial to the line $x_2 = \alpha - x_1$.


TITLE: Calculate limit
QUESTION [5 upvotes]: I need to calculate limit
$$\lim\limits_{n \to \infty} n^2 q^n,$$
where $|q|<1$. Any hints how to do that would be appreciated.

REPLY [2 votes]: Another fancy way: take the series
$$\sum_{n=1}^\infty n^2q^n\;,\;\;|q|<1$$
Applying the $\;n$-th root test we get:
$$\sqrt[n]{n^2|q|^n}=\sqrt[n]{n^2}\;|q|\xrightarrow[n\to\infty]{}|q|<1$$
and thus the series converges (even absolutely), and from here we get at once that
$$n^2q^n\xrightarrow[n\to\infty]{}0$$


TITLE: A question about the Chern-Weil construction of Euler class
QUESTION [5 upvotes]: I'm reading Appendix C of "Characteristic Classes" by Milnor & Stasheff and something confuses me. When proving that the Pfaffian of the curvature form (of an oriented $2n$-plane bundle $\xi$ over a smooth manifold $M$, with a metric and a connection compatible with that metric) represents a multiple of the Euler class of $\xi$, the authors say:

(here $K$ stands for curvature tensor)
The notation $Pf(K(\tilde{\gamma}))$ suggests that $\tilde{\gamma}$ has a connection on it, thus the base space must be a smooth manifold. On the other hand, $\tilde{\gamma}$ is required to be "universal", so it should be the tautological bundle over the oriented Grassmannian $\tilde{G}_{2n}(\mathbb{R}^{\infty})$, but then the base space is not a manifold, seemingly a contradiction. So what should this bundle $\tilde{\gamma}$ be?

REPLY [9 votes]: In the second line of the quoted passage, it says that $\tilde\gamma$ should be `universal in dimensions $\leq 4n$'. This means that it's universal for bundles over complexes of dimension at most $4n$, and so we can take a finite dimensional oriented Grassmannian $\tilde{G}_{2n}(R^N)$ for sufficiently large $N$. This is a manifold, and the restriction of $\tilde\gamma$ has a connection.
You can read about $n$-universal bundles in Steenrod's book, Fiber Bundles.


TITLE: What about $\ell^1$ with pointwise multiplication
QUESTION [5 upvotes]: This question occurred to me after reading this thread.
I was working on finding an example of a Banach algebra. The example I came up with was $\ell^1 (\mathbb N)$ with pointwise multiplication. I believe I even proved that $\ell^1 (\mathbb N)$ is closed with respect to pointwise multiplication and that the norm is submultiplicative.
Is it really possible that $\ell^1 (\mathbb N)$ can be turned into a Banach algebra in two ways, by convolution and by pointwise multiplication, or is there necessarily a mistake in my proof? (I'm happy to post the proof if the answer is yes -- for now I'm just trying to keep this question short)

REPLY [3 votes]: I don't see any contradiction, at first sight. In fact, any Banach space can be made into a Banach algebra if you define the product as zero.


TITLE: Show that a polynomial $f(x)$ over a field $k$ is irreducible if and only if the polynomial $f(x+1)$ is irreducible
QUESTION [2 upvotes]: I have literally no idea how to do this. I tried writing out $f(x+1)$ and rewriting it but didn't seem to get anywhere. I suspect I should use the degree of the polynomials but don't know how.

REPLY [6 votes]: Let me phrase this in a somewhat more general context.
Let $R$ be a UFD. Then, for any $\alpha\in R$ which is irreducible, $\varphi(\alpha)$ is irreducible for every $\varphi\in\text{Aut}(R)$. Indeed, if $\varphi(\alpha)=\beta\gamma$, where neither $\beta$ nor $\gamma$ are units, then certainly $\alpha=\varphi^{-1}(\beta)\varphi^{-1}(\gamma)$, and since $\delta$ is a unit if and only if $\varphi(\delta)$ is a unit, we arrive at a contradiction.
You're problem then just comes from the fact that $f(x)\mapsto f(x+1)$ is a ring automorphism of $k[x]$.

REPLY [4 votes]: Hint : $f(x)=g(x)h(x)$ if and only if $f(x+1)=g(x+1)h(x+1)$.


TITLE: How to find the convergence interval and radius of $\sum_{n=1}^{\infty}\sqrt[n]{n}(2x+5)^n$?
QUESTION [1 upvotes]: Find the convergence interval and convergence radius of the sequence $$\sum_{n=1}^{\infty}\sqrt[n]{n}(2x+5)^n.$$
I tried ratio test: $$\lim_{n\to \infty}\left|\frac {\sqrt[n+1]{n+1}(2x+5)^{n+1}}{\sqrt[n]{n}(2x+5)^n}\right|=|(2x+5)|\lim_{n\to \infty}\left|\frac {\sqrt[n+1]{n+1}}{\sqrt[n]{n}}\right|.$$
But couldn't conclude.

REPLY [1 votes]: You're almost right, just log the expressions:
$$
\frac{(n+1)^{\frac{1}{n+1}}}{n^{\frac{1}{n}}} \rightarrow \frac{\log(n+1)}{n+1} - \frac{\log n}{n} \to_n0-0=0
$$
hence the limit of the ration is $e^0=1$. So allyou need to do is check $|2x+5|<1$.


TITLE: Is the ring of formal power series in $n$ variables the colimit of the powers of its maximal ideal
QUESTION [1 upvotes]: Let $\mathbb C[[t_1, ..., t_n]]$ be the noetherian local ring of formal power series in $n$ variables with a unique maximal ideal $\mathfrak{m}=(t_, ..., t_n)$. Then, there is a descending chain of ideals of $\mathbb C[[t_1, ..., t_n]]$ given by $(1)\supset\mathfrak{m}\supset\mathfrak{m}^2\supset\cdots\mathfrak{m}^p\supset\cdots$. It is a well-known fact that every module is the direct limit (colimit) of its finitely generated submodules. Is it true that $\mathbb C[[t_1, ..., t_n]]\cong colim_p\mathfrak{m}^p$ as $\mathbb C[[t_1, ..., t_n]]$-modules?

REPLY [1 votes]: Yes, but for trivial reasons; I don't think this is the question you meant to ask. The colimit over any diagram $F : J \to C$ of shape $J$ such that $J$ has a terminal object $1$ is just the evaluation $F(1)$, which here is the unit ideal. So the same would be true of any descending chain of ideals starting at the unit ideal, in any ring.
There is a nontrivial statement which looks a bit like this, which is that $\mathbb{C}[[t_1, \dots t_n]]$ is the limit of the quotients $\mathbb{C}[[t_1, \dots t_n]/m^p$.


TITLE: Non-generator elements of a group and Intersection of all maximal subgroups.
QUESTION [0 upvotes]: A non-generator element $u$  of a group $G$ is defined as,

If $H\not=G,$ then $\langle H,u\rangle\not=G$ for any $H\le G.$

Show that set of all non-generators of $G$ is a subgroup of the intersection of all maximal subgroups of G.
I have no idea to attempt this question.
Any idea to start an answer? Thank You.

REPLY [1 votes]: David Holden gave me a wonderful solution. But I think it is better to prove that the set of all non-generators are form a subgroup.
Since $1$ is a non-generator, set of all non-generators is non empty.
Lets take any two non-generators $u_1, u_2$ and a proper subgroup $H$ of $G.$
Then we can see that $$\langle H,u_1u_2^{-1}\rangle\le\langle \langle H,u_1\rangle,u_2\rangle\lt G$$ Hence $u_1u_2^{-1}$ is also a non-generator of $G.$
Therefore set of all non-generators form a subgroup of $G.$


TITLE: On how to get a solution for a nonhomogeneous problem for the heat equation.
QUESTION [4 upvotes]: Evans PDE book presents the following problem (page 87):

Write down an explicit formula for a solution of
  $$\left\{\begin{matrix}
u_t-\Delta u+cu=f &\text{ in }\mathbb{R}^n\times(0,\infty) \\
 u=g&\text{ on }\mathbb{R}^n\times\{0\}
\end{matrix}\right.\tag{1}$$
  where $c\in\mathbb{R}$.

In the text (page 51) was given a solution of
$$\left\{\begin{matrix}
v_t-\Delta v=F &\text{ in }\mathbb{R}^n\times(0,\infty) \\
 v=G&\text{ on }\mathbb{R}^n\times\{0\}
\end{matrix}\right.\tag{2}$$
So, it's seems natural to try to reduce $(1)$ to $(2)$. This was done here (page 10).
My question (possibly elementary) is: If no one give us the answer, how can we discover that we should set $v(x,t)=u(x,t)e^{ct}$? What's the insight behind this choose?
Thanks.

REPLY [3 votes]: Since the general solution of $u_t+cu=0$ is $u(x,t)=C(x)e^{ct}$ , therefore let $v(x,t)=u(x,t)e^{ct}$ can solely eliminating the term $cu$ of the PDE.


text:
\begin{document}

\twocolumn[
\icmltitle{Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence}

\begin{icmlauthorlist}
\icmlauthor{Lijun Ding}{orie}
\icmlauthor{Yingjie Fei}{orie}
\icmlauthor{Qiantong Xu}{cs}
\icmlauthor{Chengrun Yang}{ece}

\end{icmlauthorlist}

\icmlaffiliation{orie}{School of ORIE, Cornell University, Ithaca, NY 14850, USA}
\icmlaffiliation{ece}{School of Electrical and Computer Engineering, Cornell University, Ithaca, NY 14850, USA}
\icmlaffiliation{cs}{Facebook AI Research, Menlo Park, CA 94025, USA}

\icmlcorrespondingauthor{Lijun Ding}{ld446@cornell.edu}

\icmlkeywords{Machine Learning, ICML}

\vskip 0.3in
]

\printAffiliationsAndNotice{}

\global\long\def\fronorm#1{\|#1\|_{\text{F}}}

\global\long\def\twonorm#1{\|#1\|_{2}}

\global\long\def\opnorm#1{\|#1\|_{\text{op}}}

\global\long\def\nucnorm#1{\|#1\|_{*}}

\global\long\def\infnorm#1{\|#1\|_{\infty}}

\global\long\def\abs#1{\left|#1\right|}

\global\long\def\real{\mathbb{R}}

\global\long\def\integer{\mathbb{Z}}

\global\long\def\inprod#1#2{\langle#1,#2\rangle}

\global\long\def\symMat{\mathbb{S}}

\global\long\def\specsplex{\mathcal{S}_n}

\global\long\def\dm{n}

\global\long\def\cons{m}

\global\long\def\tr{\mathbf{tr}}

\global\long\def\Amap{\mathcal{A}}

\global\long\def\xsol{X_{\star}}

\global\long\def\rsol{r_{\star}}

\global\long\def\zsol{Z_{\star}}

\global\long\def\ssol{s_{\star}}

\global\long\def\face#1{\mathcal{C}_{#1}}

\global\long\def\onevec{\mathbf{1}}

\global\long\def\ddiag{\mbox{ddiag}}

\global\long\def\diag{\mbox{diag}}

\global\long\def\range{\mbox{range}}

\global\long\def\dist{\mbox{dist}}

\global\long\def\nullspace{\mbox{nullspace}}

\global\long\def\rank{\mbox{rank}}

\global\long\def\proj{P}

\global\long\def\relint{\mbox{relint}}

\global\long\def\dualdim{k_\star}

\global\long\def\dspacerep{V_\star}

\global\long\def\EV{\mathbf{EV}}

\newcommand{\blue}[1]{\textcolor{blue}{#1}}

\begin{abstract}
We develop a novel variant of the classical Frank-Wolfe algorithm, which we call spectral Frank-Wolfe, for convex optimization over a spectrahedron. The spectral Frank-Wolfe algorithm has a novel ingredient: it computes a few eigenvectors of the gradient and solves a small-scale SDP in each iteration. Such procedure overcomes slow convergence of the classical Frank-Wolfe algorithm due to ignoring eigenvalue coalescence. We demonstrate that strict complementarity of the optimization problem is key to proving linear convergence of various algorithms, such as the spectral Frank-Wolfe algorithm as well as the projected gradient method and its accelerated version.

\end{abstract}

\section{Introduction}

We consider solving the following optimization problem with the decision
variable $X\in\real^{\dm\times\dm}$:
\begin{align}
\mbox{minimize}\quad & f(X):=g(\Amap X)+\inprod CX\label{eq:Mainoptimization}\\
\mbox{subject to\ensuremath{\quad}} & \tr(X)=1\quad X\succeq0.\nonumber
\end{align}

\paragraph{Problem setup.}
The setup of Problem~(\ref{eq:Mainoptimization}) is as follows. We assume $C \in\real^{\dm\times\dm}$ is a symmetric matrix.  The constraint $X\succeq0$ means that $X$ is symmetric and positive semidefinite.
We assume that $\Amap:\symMat^{\dm}\rightarrow\real^{\cons}$ is a linear map
from the set of symmetric matrices $\symMat^{\dm}$ to the $m$-dimensional Euclidean space. We also assume that the
function $g:\real^{\cons}\rightarrow\real$ is differentiable and its
gradient $\nabla g$ is $L_{g}$-Lipschitz continuous. We use $\tr(\cdot)$ to denote the standard
trace operation, the sum of diagonal entries of the input matrix. We denote by $\specsplex$ the feasible region of Problem~(\ref{eq:Mainoptimization}). The set $\specsplex$ is called the spectrahedron, which
is nonempty and compact. Hence Problem (\ref{eq:Mainoptimization})  always has an optimal solution.
In this paper, we assume Problem~(\ref{eq:Mainoptimization})
admits a unique optimal solution $\xsol$ with rank $\rsol$ for the sake of simplicity.
The main results, Theorem \ref{thm:MainAlgorithmTheorem} and \ref{thm:MainStructralTheorem} below, can be adapted to the setting where multiple optimal solutions exist; see Section \ref{sec: uniqueness} in the Appendix for a further discussion. It is worth noting that for almost all matrix $C$, the solution of Problem~(\ref{eq:Mainoptimization}) is indeed
unique \citep[Corollary 3.5]{drusvyatskiy2011generic}.

\paragraph{Applications.} The optimization problem covers many low rank matrix recovery problems
including matrix sensing \cite{recht2010guaranteed}, matrix completion \cite{candes2009exact,jaggi2010simple}, phase retrieval
\cite{candes2015phase,yurtsever2017sketchy}, and blind deconvolution \cite{ahmed2013blind}. The constraints $X\succeq0$ and
$\tr(X)=1$ impose low-rankness on the solution. The rank $\rsol$ of optimal solutions in these applications
is expected to be small comparing to the problem dimension $\dm$. We note that
the following problem:
\begin{equation}
\begin{aligned}\label{eq: tracenormballformulation}
\mbox{minimize}_{\nucnorm X\leq\alpha}\quad f(X),
\end{aligned}
\end{equation}
is sometimes a more direct optimization formulation for aforementioned low
rank matrix recovery problems. Since Problem~(\ref{eq: tracenormballformulation}) can be re-formulated
as Problem~(\ref{eq:Mainoptimization})   \cite{jaggi2010simple}, we consider Problem~(\ref{eq:Mainoptimization})
as our main focus of study in this paper.

\paragraph{Background and related works.} A natural but costly algorithm for solving~\eqref{eq:Mainoptimization} is using the projected gradient descent method (PGD) or its accelerated version (APGD) \cite{nesterov2013introductory}. Although
the iteration complexity of PGD or APGD is considerably low,\footnote{ PGD or APGD achieves an $\epsilon$-approximate solution in $\mathcal{O}(\log(\frac{1}{\epsilon}))$ iterations for strongly convex $f$. APGD achieves an  $\epsilon$-approximate solution $\mathcal{O}(\frac{1}{\sqrt{\epsilon}})$ for general smooth $f$.}
each of their iteration requires computing a full eigenvalue decomposition of an $\dm \times \dm$ matrix, which scales as
$\mathcal{O}(n^3)$~\cite{trefethen1997numerical}. The high per-iteration cost prevents their large-scale deployment.
\begin{algorithm}[tb]
	\caption{Frank-Wolfe with line search}
	\label{alg: Frank_wolfe}
	\begin{algorithmic}
		\STATE {\bfseries Input:} initialization $X_0\in\specsplex$
		\FOR{$t=1,2,\dots,$ }
		\STATE \textbf{Eigenvalue computation:} compute an eigenvector $v$ of $\nabla f(X_t)$ associated with smallest
		eigenvalue.
		\STATE \textbf{Line search:} solve $\hat{\eta}=\arg\min_{\eta \in [0,1]}f(\eta X_{t}+(1-\eta)vv^\top )$  and set $X_{t+1} = \hat{\eta} X_{t}+(1-\hat{\eta})vv^\top$.
		\ENDFOR
	\end{algorithmic}
\end{algorithm}
\begin{algorithm}[tb]
	\caption{Generalized BlockFW (G-BlockFW)}
	\label{alg:generalizedBlockFW}
	\begin{algorithmic}
		\STATE {\bfseries Input:} initialization $X_0\in\specsplex$, a step size $\eta\in[0,1]$,
		a smooth parameter $\beta$, and an integer $k>0$
		\FOR{$t=1,2,\dots,$ }
		\STATE \textbf{Eigenvalue computation:} compute top $k$ eigenvalues
		$(\lambda_1,\dots,\lambda_r)$ and their eigenvectors $V=[v_1,\dots,v_k]$ of $X_t-\frac{1}{\eta \beta}\nabla f(X_t)$.
		\STATE \textbf{Eigenvalue projection:} project $(\lambda_1,\dots,\lambda_k)$ to the $k$-dimensional
		probability simplex $\{x\in \real^k\mid \sum_{i=1}^k x_i =1,x_i\geq 0 \}$, and get the projected point $\Lambda$.
		\STATE \textbf{Forming a new iterates:} set $X_{t+1}= (1-\eta)X_t+\eta V\diag(\Lambda)V^\top$.
		\ENDFOR
	\end{algorithmic}
\end{algorithm}
Hence, projection-free methods are sought, such as the Frank-Wolfe method (FW) \cite{frank1956algorithm,jaggi2013revisiting} presented in Algorithm \ref{alg: Frank_wolfe}. In the spectrahedron setting, each step only
requires computing \emph{one} eigenvector of the gradient of $f$, which can be efficiently done using the Lanczos method \cite{kuczynski1992estimating} by taking advantage of the structure of $\nabla f(X)=\Amap^*(\nabla g)(\Amap X) +C$ as well as the sparsity of $\Amap$ and $C$.  FW converges to an $\epsilon$-approximate solution\footnote{A matrix $X$ is $\epsilon$-approximate solution to Problem \eqref{eq:Mainoptimization} if $X$ is feasible and $f(X)-f(\xsol)\leq \epsilon$.}
within $\mathcal{O}(\frac{1}{\epsilon})$ many iterations. However, the iteration complexity $\mathcal{O}(\frac{1}{\epsilon})$ is tight as shown in \cite{garber2016faster} even if $f$ is strongly convex and no structural assumption is posed on the solution of \eqref{eq:Mainoptimization}.
Considerable recent research effort  \cite{garber2016faster,fd2017extended,allen2017linear,garber2019linear} has focused on incorporating the low-rankness
of solution $\xsol$. Of particular relevance to our work are \citet{garber2019linear} and \citet{allen2017linear}:
\begin{itemize}
    \vspace{-0.5cm}
    \setlength\itemsep{0em}
	\item \citet{garber2019linear} shows that Algorithm~\ref{alg: Frank_wolfe}  converges linearly
	given that the solution is rank \emph{one}, and an eigengap assumption on the gradient $\nabla f(\xsol)$ at the optimal solution is satisfied. We note that the rank-one assumption is crucial for the linear convergence of Algorithm~\ref{alg: Frank_wolfe} to hold. As we will demonstrate in Section \ref{sec: numerics}, if the solution is not rank one, Algorithm~\ref{alg: Frank_wolfe} gets stagnant and behaves in the worst case as  $\mathcal{O}(\frac{1}{\epsilon})$.

	  \item  \citet{allen2017linear} proposes an algorithm called BlockFW, which is re-formulated as Algorithm \ref{alg:generalizedBlockFW} for our setting and renamed as  generalized BlockFW(G-BlockFW) \footnote{We note that BlockFW is \emph{not} designed for \eqref{eq:Mainoptimization}, but rather for \eqref{eq: tracenormballformulation}. Since \eqref{eq: tracenormballformulation} covers~\eqref{eq:Mainoptimization}, we renamed the algorithm as G-BlockFW.}. It computes only $k$ eigenvectors in each step, and converges linearly so long as $k\geq \rsol=\rank(\xsol)$ and $f$ is strongly convex.  However, the method relies critically on the assumption $k\geq \rsol$: no convergence guarantees can be made if this assumption fails. Indeed, we will demonstrate in Section \ref{sec: numerics} that if $k<\rsol$, G-BlockFW  gets stuck at moderate accuracy and cannot make further progress.\footnote{\citet{allen2017linear} gives an adaptive $k$ selection procedure which works well in their experiments, but there is no theoretical guarantee for the procedure.} Moreover, the method needs
	to store iterates explicitly to compute the eigenvectors. This not only incurs an extra $\mathcal{O}(n^2)$ space complexity, but also increases the burden of
	computing eigenvectors as the iterates themselves have no structure to be exploited for fast eigenvector computation.\footnote{Actually \citet{allen2017linear}  provides a method to avoid the extra space and time costs. However, the method requires knowledge of the strong convexity parameter, which is unavailable in all experiments they perform.}
\end{itemize}
In summary, previous methods converge linearly only when the optimal solution is rank one, or the number of eigenvectors computed in each iteration is no smaller than the rank of the optimal solution.
\iffalse
$\rsol =\rank(\xsol)=1$ or $k\geq \rsol$ (where $k$ is the number
of eigenvectors computed in each iteration).
\fi

\begin{table*}\label{table: comparison}
\centering

\begin{tabular}{cccc}
\toprule
    \multirow{2}{*}{Algorithm} & \multicolumn{3}{c}{Convergence Rate} \\
    \cmidrule(lr){2-4}
	& Worst  & Linear  & Condition  \\
\midrule
FW (Alg.~\ref{alg: Frank_wolfe}) & $\frac{8L_f}{t}$ & $(1-\frac{\delta}{12L_f})^t$ & $\rsol=1$ and strict comp.  \\
G-BlockFW (Alg.~\ref{alg:generalizedBlockFW}) & \xmark  & $(1-\frac{\gamma}{2L_f})^t$ & $k\geq \rsol$ and QG \\
SpecFW (Alg.~\ref{alg:spectral_frank_wolfe}) & $\frac{8L_f}{t}$ & $(1-\frac{\min(\delta,\gamma)}{12L_f})^t$ & $k\geq \rsol $, QG, and strict comp. \\
\bottomrule
\end{tabular}
\caption{Comparision of FW, G-BlockFW and SpecFW. Here, we assume $f$ has gradients $\nabla f$ that are $L_f$-Lipschitz. The optimal
solution rank is $\rsol=\rank(\xsol)$. We let $t$ be the number of iterations.
Convergence rates are measured by $f(X_t)-f(\xsol)$. We set $\delta$ to be the difference
between the smallest eigenvalue and the $(\rsol+1)$th-smallest eigenvalue of
$\nabla f(\xsol)$, that is, $\delta =\lambda_{n-\rsol}(\nabla f(\xsol))- \lambda_{n}(\nabla f(\xsol))$.  "Strict comp." means strict complementarity (Definition \ref{def:(Strict-Complementarity)-Suppose}). "QG" means quadratic growth with parameter
$\gamma$ (Definition \ref{def: growthCondition}). Both FW and SpecFW have
 burn-in phases which are bounded by $\frac{72L_f^3}{(\min\{\gamma,\delta\})^3}$. Here, the burn-in phase
is the number of iterations in which the method converges with standard
rate $L_f/t$, before shifting to the faster rate (if linear convergence condition is satisfied).
The convergence rate of G-BlockFW can be found in Lemma \ref{lem: linearConvergenceOfBlockFW} in
Section \ref{sec: lemmaForSection4} of the Appendix.}
\end{table*}

\paragraph{Our contributions.} The contribution of this work is two-fold. On the problem structure side:
\begin{itemize}
    \vspace{-0.3cm}
    \setlength\itemsep{0em}
	\item We show that the eigengap assumption in \cite{garber2019linear} is equivalent to
	the strict complementarity condition, a well-known regularity condition of semidefinite programming~\cite{alizadeh1997complementarity};
	see Section~\ref{sec: StrictComplementarityAndGrowth} for more detail.
	\item Based on the eigengap condition, or the equivalent strict complementarity  condition, we show that
	Problem \eqref{eq:Mainoptimization} satisfies the quadratic growth property (Definition~\ref{def: growthCondition} below)  when
	the outer function $g$ is strongly convex over the feasible region $\specsplex$ of Problem \eqref{eq:Mainoptimization}, which is true for all the application being considered. This governs the linear convergence of many first order methods such as PGD, APGD, and our method, Spectral Frank Wolfe.
\end{itemize}
On the algorithm side, we propose a new algorithm called Spectral Frank-Wolfe (SpecFW) in Section \ref{sec: SpectralFrank-WolfeAndItsConvergenceRate}, which has the following
properties:
\begin{itemize}
    \setlength\itemsep{0.2pt}
	\item In each of its iteration, it computes $k$ eigenvectors using \emph{only} the current gradient information.
	\item In each of its iteration, it solves a small-scale sub-problem efficiently by APGD for small $k$.
	\item It always converges at the rate $\mathcal{O}(\frac{1}{\epsilon})$ no matter what choice of $k$ is.
	\item It converges linearly when $k\geq \rsol$, and the strict complementarity and
	quadratic growth condition are satisfied. In particular, we do \emph{not} require $f$ to be strongly convex or the rank $\rsol$ to be $1$.
	\item It can easily incorporate the matrix sketching idea from \citet{tropp2017practical} and achieves the so-called storage
	optimality discussed in \citet{yurtsever2017sketchy}. The sketching procedure obviates the need for storing the full decision matrix $X$ throughout iterations, thereby saving $\mathcal{O}(n^2)$ space.\footnote{Interested readers can find the procedure in Section \ref{sec: SpecFWmatrixSketching} in the Appendix.
		We note the matrix sketching idea cannot be combined with G-BlockFW easily to avoid storing $X$, as G-BlockFW uses a sum of the current iterate and current gradient to compute the eigenvectors, which destroys the fast matrix-vector product property of the gradient.}
\end{itemize}

\paragraph{Organization.} The rest of the paper is organized as follows.
In Section \ref{sec: StrictComplementarityAndGrowth}, we explain
the concept of strict complementarity and the  classical Frank-Wolfe algorithm, and how they motivate our Spectral Frank-Wolfe. In Section \ref{sec: SpectralFrank-WolfeAndItsConvergenceRate}, we present the Spectral Frank-Wolfe and its convergence guarantees. In Section \ref{sec: QuadraticGrowthAndLinearConvergence}, we show that the strict complementarity enforces the quadratic growth condition whenever $g$ is strongly convex on $\specsplex$. Finally, we demonstrate numerically the effectiveness of the Spectral Frank-Wolfe in Section~\ref{sec: numerics}.

\paragraph{Notation.} For a symmetric matrix $A\in\protect\symMat^{\protect\dm}$,
we denote its $i$-th largest eigenvalue as $\lambda_{i}(A)$. The operator two norm, nuclear norm,
and Frobenius norm are denoted as $\opnorm{A}$, $\nucnorm{A}$, and $\fronorm{A}$, respectively. The inner product $\inprod{\cdot}{\cdot}$ on
symmetric matrices is the standard trace inner product. We also equip $\mathbb{R}^m$ with the dot product.
For a linear map $\mathcal{B:\protect\symMat}^{d}\rightarrow\protect\real^{l}$, the
adjoint map of $\mathcal{B}$ is denoted as $\mathcal{B}^{*}$.
We also define its largest and smallest singular values as $\protect\opnorm{\mathcal{B}}=\sigma_{\max}(\mathcal{B})=\max_{\protect\fronorm A=1}\protect\twonorm{\mathcal{B}(A)}$
and $\sigma_{\min}(\mathcal{B})=\min_{\protect\fronorm A=1}\protect\twonorm{\mathcal{B}(A)}$.
Given a matrix $V\in\protect\real^{d\times r}$, we denote the restriction of $\mathcal{B}$ to $V$ as  $\mathcal{B}_{V}:\protect\symMat^{r}\rightarrow\protect\real^{l}$
by $\mathcal{B}_{V}(S)=\mathcal{B}(VSV^{\top})$ for any $S\in\protect\symMat^{r}$.

\section{Motivating SpecFW from complementarity and Frank-Wolfe}\label{sec: StrictComplementarityAndGrowth}
In this section, we explain the motivations of the  spectral
Frank-Wolfe from strict complementarity and its relationship with
the classical Frank-Wolfe.
\subsection{Observation from complementarity}
Let first introduce the KKT condition to see what complementarity means.
\paragraph{KKT condition.} By Slater's condition for \eqref{eq:Mainoptimization} and the fact that the feasible region $\specsplex$ is compact, the following KKT condition of (\ref{eq:Mainoptimization}) always holds: there is some
dual optimal solution $\zsol\succeq 0$ and $\ssol\in\real$ such that\footnote{If there are multiple primal optimal solutions, then the KKT condition holds for any one of them.}
\begin{align}
\nabla f(\xsol)-\zsol-\ssol I & =0,\quad\text{(First Order Condition)}\label{eq:KKT}\\
\inprod{\zsol}{\xsol} & =0,\quad\text{(Complementarity)}\nonumber \\
\tr(\xsol) & =1,\quad\text{(Linear Constraint Feasibility)}\nonumber \\
\zsol,\xsol & \succeq0.\quad\text{ (PSD Feasibility)}\nonumber
\end{align}
Here $I$ is the identity matrix in $\symMat^{\dm}$.
We prove in Lemma \ref{lem: uniquenessOfTheDual} in the Appendix
that the dual
solution $(\zsol,\ssol)$ is actually unique.

\paragraph{Complementarity: extract $\xsol$ from $\zsol$.} we first note that using $\zsol,\xsol\succeq0$ and complementarity  $\inprod{\zsol}{\xsol}=0$,
we have $\zsol\xsol=0$. This equality implies that
\begin{align}\label{eq: rangexsolNullspaceZsol}
\range(\xsol)\subset\nullspace(\zsol),
\end{align}
and
\begin{align}\label{eq: inequalityrankxsolnullspacedimZ}
\rsol=\rank(\xsol)\leq\dim(\nullspace(\zsol))=:\dualdim.
\end{align}

Hence, if we can compute a matrix $\dspacerep \in \real^{\dm \times \dualdim}$ with orthonormal
columns that span the null space of $\zsol$, and solve for
\begin{equation}
\begin{aligned} \label{eq: reducedProblem}
S_\star = \arg\min_{S\in \mathcal{S}_{\dualdim}} f(\dspacerep S \dspacerep^\top),
\end{aligned}
\end{equation}
then we get the primal optimal solution $\xsol =\dspacerep S_\star \dspacerep^\top$.

We note that it is
necessary to optimize over the $\dualdim$-spectrahedron $\mathcal{S}_{\dualdim}$ instead of just a
$\dualdim$-dimensional probability simplex, as $\dspacerep$ may not be the eigenvectors of $\xsol$ for $\dualdim>1$.
Problem
\eqref{eq: reducedProblem} can be solved by APGD rapidly so long as $\dualdim$, the \emph{size}
of $S$, is small.

This naturally leads to the following questions:
\begin{enumerate}
	\item Problem \eqref{eq: reducedProblem} is easy to solve only if $\dualdim$ is small; yet for now we only have
	$\dualdim\geq \rsol$. With $\rsol$ expected to be small, can we hope for $\dualdim =\rsol$ to hold,
	so that $\dualdim$ is small as well?
	\item Suppose we have $\dualdim=\rsol$, can we compute $\dspacerep$ exactly or approximate it well enough?
\end{enumerate}

We answer the first question in the next section by defining strict complementarity
and establishing its equivalence to an eigengap condition on $\nabla f(\xsol)$.
To answer the second question, we draw relationship between the first order condition in \eqref{eq:KKT}
and the classical Frank-Wolfe algorithm in Section \ref{sec: fwmotivation}.

\subsection{Strict complementarity}\label{sec: strictcomplementarity}
We answer why we expect $\rsol =\dualdim$ in this section.
Using the rank-nullity theorem, we see that the equation $\rsol=\rank(\xsol)\leq\dim(\nullspace(\zsol))$
is equivalent to
\[
\rank(\xsol)+\rank(\zsol)\leq\dm.
\]
Strict complementarity \cite{alizadeh1997complementarity}
assumes that we have equality instead of
inequality.
\begin{defn}
	\label{def:(Strict-Complementarity)-Suppose}(Strict Complementarity)
	Let $\xsol,\zsol$ and $\ssol$ satisfy the KKT condition (\ref{eq:KKT}).
	We say that Problem (\ref{eq:Mainoptimization}) (or the pair $(\xsol,\zsol)$) satisfies strict complementarity if
	\[
	\rank(\xsol)+\rank(\zsol)=\dm.
	\]
\end{defn}
It is immediately clear that using the rank-nullity theorem again, we see that strict complementarity
is equivalent to
\[
\rsol =\dualdim,
\]
which is what we desire.
By \eqref{eq: rangexsolNullspaceZsol} and given that the solution rank is $\rsol$,
strict complementarity is equivalent to
\begin{equation}
\lambda_{n-\rsol}(\zsol)>0.\label{eq:equivalenceOfStrictComplementarity}
\end{equation}
Equation~\eqref{eq: rangexsolNullspaceZsol} also implies that we always have for all $i=1,\dots,\rsol$,
\begin{align}
\lambda_{n-\rsol+i}( & \zsol)=0.\label{eq:zsolsmalleigenvaluearezero}
\end{align}
\paragraph*{Relation with the eigengap assumption.}

In \citet{garber2019convergence,garber2019linear}, the author proposed an eigengap condition:
\[
\lambda_{n-\rsol}(\nabla f(\xsol))-\lambda_{n}(\nabla f(\xsol))>0.
\]
This is in fact  equivalent to strict complementarity: since $\nabla f(\xsol)=\zsol+\ssol I$,
we have
\begin{align*}
&\lambda_{n-\rsol}(\nabla f(\xsol))-\lambda_{n}(\nabla f(\xsol))\\
 =& \lambda_{n-\rsol}(\zsol+\ssol I)-\lambda_{n}(\zsol+\ssol I)\\
 = &\lambda_{n-\rsol}(\zsol)+\ssol-\lambda_{n}(\zsol)-\ssol\\
 = & \lambda_{n-\rsol}(\zsol),
\end{align*}
where the last step is due to (\ref{eq:zsolsmalleigenvaluearezero}). Using
(\ref{eq:equivalenceOfStrictComplementarity}), we deduce the equivalence.

\paragraph*{Why strict complementarity should hold.}

Strict complementarity as shown in \citet{drusvyatskiy2011generic} holds for almost all $C$ (see
Lemma \ref{lem: genericstrictcomplementarity} for a more detailed derivation).
We will also verify this assumption numerically in our experiments in Section~\ref{sec: numerics}.
Moreover, as demonstrated in \citet[Lemmas 2 and  10]{garber2019linear}, such assumption should hold if
we expect the solution rank $\rsol$ to be stable under small
perturbations.

\subsection{FW and approximation of $\nullspace(\zsol)$}\label{sec: fwmotivation}
We have just argued why we expect $\rsol =\dualdim$ should hold for Problem \eqref{eq:Mainoptimization}. In this section,
we draw relation of FW and approximation of $\nullspace(\zsol)$.

Denote by $\EV_r(A)$ the eigenspace of the smallest $r$ eigenvalues of a matrix $A\in \symMat^{\dm}$.
In view of the first order condition \eqref{eq:KKT}, we have
\begin{equation}
\begin{aligned}\label{eq: gradientAndDual}
\EV_{\dualdim}(\nabla f(\xsol)) = \nullspace(\zsol).
\end{aligned}
\end{equation}
Hence $ \nullspace(\zsol)$ can be identified using the gradient of $f$ at $\xsol$.

Note that FW indeed uses the eigenvector corresponding to the smallest eigenvalue of $\nabla f(X_t)$ in each of
its  iteration, and therefore it tries to approximate $\EV_{\dualdim}(\nabla f(\xsol))$. This is
the main intuition that linear convergence of FW can be established  when $\rsol=1$  as in \citet{garber2019linear}. It also reveals that FW fails to converge in a linear rate for $\dualdim>1$, as approximation using
one eigenvector is not enough for a $\dualdim$-dimensional space. Also,
from \eqref{eq:zsolsmalleigenvaluearezero} and the first order condition in
the KKT condition, we see the smallest
$\dualdim$ eigenvalues of the gradient coalesce, and hence it
is important to compute the $\dualdim$-dimensional space
to attain
better numerical stability and accuracy.
Hence, to overcome this issue, we need to  compute at least $\dualdim$ eigenvectors  and solve a sub-problem like \eqref{eq: reducedProblem} in each iteration.

The above discussion motivates our algorithm, the Spectral Frank-Wolfe (Algorithm \ref{alg:spectral_frank_wolfe}),
described in the next section.

\section{Spectral Frank-Wolfe and its Convergence guarantees}\label{sec: SpectralFrank-WolfeAndItsConvergenceRate}
In this section, we describe the Spectral Frank-Wolfe algorithm and its theoretical
guarantees.
\subsection{The Spectral Frank-Wolfe algorithm}
The Spectral Frank-Wolfe algorithm is presented in Algorithm~\ref{alg:spectral_frank_wolfe}. We highlight its key mechanism as follows.
\begin{algorithm}[tb]
	\caption{Spectral Frank-Wolfe}
	\label{alg:spectral_frank_wolfe}
	\begin{algorithmic}
		\STATE {\bfseries Input:} initialization $X_0\in\specsplex$, an integer $k>0$
		\FOR{$t=1,2,\dots,$ }
		\STATE \textbf{Eigenvalue computation:} compute the $k$ eigenvectors, $v_1,\dots,v_k$ of $\nabla f(X_t)$ associated with the $k$ smallest
		eigenvalues, and form the matrix $V = [v_1,\dots,v_k]\in \real^{\dm \times k}$.
		\STATE \textbf{Solving a small-scale SDP:} solve $\min_{\eta+\tr(S)=1,S\succeq 0,\eta \geq 0}f(\eta X_{t}+VSV^{\top})$ and get an optimal solution $(\hat{S},\hat{\eta})$.
		\STATE \textbf{Forming a new iterate:} set $X_{t+1} = \hat{\eta} X_{t}+V\hat{S}V^{\top}$.
		\ENDFOR
	\end{algorithmic}
\end{algorithm}

\paragraph{Solving a small-scale SDP.}
The small-scale semidefinite programming (SDP)
\begin{equation}
\begin{aligned}\label{eq: smallksubproblem}
\min_{\eta+\tr(S)=1,S\succeq 0,\eta \geq 0}f(\eta X_{t}+VSV^{\top}).
\end{aligned}
\end{equation}
can be solved easily using APGD since  projection to
the set $\{(\eta,S)\mid \eta+\tr(S)=1,S\succeq 0, \eta\geq 0\}$ only requires an eigenvalue decomposition of a symmetric matrix of size $k$ and a projection to the $(k+1)$-dimensional probability simplex. The correctness of the procedure for projection can be verified using arguments in  \citet[Lemma 3.1]{allen2017linear},
and \citet[Lemma 6]{garber2019convergence}.
We note that when evaluating gradient is very expensive, instead of minimizing $f(\eta X_{t}+VSV^{\top})$, one can also minimize an upper bound
of it (and the guarantees in the next section continue to hold). This is discussed in Section \ref{sec: upperboundf} in the Appendix.

\paragraph{Averaging with current $X_t$.} In addition to the eigenvectors from the current gradient, we also
utilize the information of previous iterates when solving the small-scale SDP \eqref{eq: smallksubproblem}.
This follows the same spirit as the classical Frank-Wolfe, which performs a line search over the current iterate and the new
atom $vv^\top$. This averaging scheme stabilizes the algorithm and facilitates the $\mathcal{O}(\frac{1}{\epsilon})$
convergence rate.

\paragraph{The choice of $k$.} From the proof of the convergence in the next section, it can be observed that
so long as $k\geq \dualdim$, Algorithm~\ref{alg:spectral_frank_wolfe}  converges linearly. Of course, one may not know $\dualdim$ in
advance. In this case, $k$ may be taken as the largest value subject to the user's computational budget or the
largest rank of the solution the user can afford in terms of storage. An adaptive strategy
may also be employed based on the progress of objetive value decay as in \citet[Section 6.2]{allen2017linear}. We do not further the discussion of this issue due to the space limit.

\subsection{Theoretical  guarantees}

To state our result, we first define the notion of quadratic growth.

\begin{defn}[Quadratic Growth (QG)]\label{def: growthCondition}
	We say that the optimization problem \eqref{eq:Mainoptimization} satisfies quadratic growth with parameter $\gamma>0$, if for every feasible $X\in \specsplex$ there holds
	\[
		f(X)-f(\xsol)\geq\gamma \fronorm{X-\xsol}^2.
		\]
\end{defn}

The quadratic growth condition is necessary for linear convergence of
gradient descent type methods as shown in ~\citet[Theorem 13]{necoara2019linear}.
Hence we should expect it to hold if we are to show linear convergence of Frank-Wolfe methods.
The condition automatically holds for strongly convex $f$, and more broadly,
it is satisfied for almost all $C$ so long as
$g$ is semi-algebraic, as shown in~\citet[Corollary 4.8]{drusvyatskiy2016generic}.
In Section \ref{sec: QuadraticGrowthAndLinearConvergence}, we show that
strict complementarity and strong convexity of the outer function $g$ (but not $f$)
implies quadratic growth, as well as an explicit formula of $\gamma$ in terms of the
solution $\xsol$, the map $\Amap$, and smoothness and strong convexity parameters
of $g$.

We now state the theoretical guarantees for our Algorithm~\ref{alg:spectral_frank_wolfe}.
\begin{thm}
	\label{thm:MainAlgorithmTheorem}Suppose strict complementarity holds
	for Problem (\ref{eq:Mainoptimization}), the optimal solution $\xsol$
	is unique with rank $\rsol$, the function $g$ has $L_{g}$-Lipschitz continuous
	gradients, Problem (\ref{eq:Mainoptimization}) satisfies quadratic growth
	with parameter $\gamma$, and the choice of $k$ satisfies $k\geq\rsol=\dualdim$. Define $h_{t}=f(X_{t})-f(\xsol)$
	for each $t$, and $\beta=\opnorm{\Amap}^{2}L_{g}$. Then for all
	$t$,
	we have
	\begin{equation}
	f(X_{t})-f(\xsol)\leq\frac{8\beta}{t}.\label{eq:firstpartofthm3}
	\end{equation}
	For all $t\geq T_{0}=\frac{72\beta^{3}}{\gamma\lambda_{n-\rsol}^{2}(\zsol)}$, we have
	\begin{equation}
	h_{t+1}\leq\left(1-\min\left\{ \frac{\gamma}{4\beta},\frac{\lambda_{n-\rsol}(\zsol)}{12\beta}\right\} \right)h_{t}.\label{eq:secondparthm3}
	\end{equation}
\end{thm}

\paragraph{Discussion on the assumptions.} As discussed before, these assumptions
are expected to be necessary for linear convergence and robustness of the rank under small perturbations. The assumption of the unique optimal solution is only for the purpose of clear presentation.

\paragraph{Preparation of the proof.} Let us first give the definition of the $r$-th spectral
set.
\begin{defn}
	For each $X\in\symMat^{\dm},$ let $V_{X}\in\real^{\dm\times k}$
	having orthonormal eigenvectors as columns corresponding to the smallest
	$k$ eigenvalues of $X$. Define the spectral $k$-th set $\face k(X)$
	of $X$ as
	\begin{align*}
	\face k(X) :=
	&\left\{ V_{X}SV_{X}^{\top}\in\symMat^{\dm}\mid S\in\mathcal{S}_k\right\} .
	\end{align*}
\end{defn}
We next present the following important lemma which is proved
in Section \ref{sec: AppendixSpectralFrank-WolfeAndItsConvergenceRate} in the Appendix.
\begin{lem}
	\label{lem:Let--and}Given $Y\in\symMat^{\dm}$ which satisfies $\lambda_{\dm-r}(Y)-\lambda_{\dm-r+1}(Y)\geq\delta$
	for some $\delta>0$, then for any $X\in\symMat^{\dm}$, $X\succeq0$,
	and $\tr(X)=1$, there is some $W\in\face r(Y)$ such that
	\[
	\inprod{X-W}Y\geq\frac{\delta}{2}\fronorm{X-W}^{2}.
	\]
\end{lem}
We are now ready to start the proof.
\begin{proof}[Proof of Theorem \ref{thm:MainAlgorithmTheorem}] Using the Lipschitz
	smoothness of $f$, we have for any $t\geq 1$,
	$\eta\in[0,1]$, and any $W\in\face{\rsol}(\nabla f(X_{t}))$:
	\begin{equation} \label{eq: QuadraticApproximationDueTosmoothness}
	\begin{aligned}
	f(X_{t+1})  \leq &f(X_{t})+(1-\eta)\inprod{W-X_{t}}{\nabla f(X_{t})}
	\\ &  +\frac{(1-\eta)^{2}\beta}{2}\fronorm{W-X_{t}}^{2}.
	\end{aligned}
	\end{equation}
	Now choose $W=v_{n}v_{n}^{\top}$where $v_{n}$ is the eigenvector
	of $\nabla f(X_{t})$ with the smallest eigenvalue, we can then perform
	the analysis as normal Frank-Wolfe as is done in \cite{jaggi2013revisiting}
	to reach the first part  of the theorem, the inequality  (\ref{eq:firstpartofthm3}).

	For the second part, we first note that by the discussion after the
	Definition \ref{def:(Strict-Complementarity)-Suppose} of strict
	complementarity, we have $\lambda_{n-\rsol}\left(\nabla f(\xsol)\right)-\lambda_{n-\rsol+1}(\nabla f(\xsol))=\lambda_{n-\rsol}(\zsol)$,
	and $\lambda_{n-\rsol+1}(\nabla f(\xsol))=\dots=\lambda_{n}(\nabla f(\xsol))$.

	Using Lipschitz continuous gradient of $f$ in step $(a)$, the quadratic growth of $f$ in step $(b)$, and
	the choice of $T_0$ in step $(c)$,  we find that for all $t\ge T_{0}$,
	\begin{align}
	\fronorm{\nabla f(X_{t})-\nabla f(\xsol)} &\overset{(a)}{\leq}\beta\fronorm{X_{t}-\xsol \nonumber}\\
&\overset{(b)}{\leq}\beta \left(\frac{f(X_{t})-f(\xsol)}{\gamma}\right)^{\frac{1}{2}} \nonumber\\
	&\overset{(c)}{\leq}\frac{1}{3}\lambda_{n-\rsol}(\zsol). \label{eq: smoothnessgradientnearoptimalgradient}
	\end{align}

	Using the inequality \eqref{eq: smoothnessgradientnearoptimalgradient} and Weyl's inequality, we find that
	\begin{equation} \label{eq:gapdifference}\
	\begin{aligned}
	&\lambda_{n-\rsol}(\nabla f(X_{t}))-\lambda_{n-\rsol+1}(\nabla f(X_t)) \\
	=& \underbrace{\lambda_{n-\rsol}\left(\nabla f(\xsol)\right)-\lambda_{n-\rsol+1}(\nabla f(\xsol))}_{=\lambda_{n-\rsol}(\zsol)}\\
	& +\underbrace{\left(\lambda_{n-\rsol}(\nabla f(X_{t}))-\lambda_{n-\rsol}\left(\nabla f(\xsol)\right)\right)}_{\geq-\frac{1}{3}\lambda_{\dm-\rsol}(\zsol)}\nonumber \\
	& +\underbrace{\left(\lambda_{n-\rsol+1}\left(\nabla f(\xsol)\right)-\lambda_{n-\rsol+1}(\nabla f(X_{t}))\right)}_{\geq-\frac{1}{3}\lambda_{n-\rsol}(\zsol)}\\
	& \geq\frac{1}{3}\lambda_{n-\rsol}(\zsol).\nonumber
	\end{aligned}
	\end{equation}
	Now we subtract the inequality \eqref{eq: QuadraticApproximationDueTosmoothness} both sides by $f(\xsol)$, and denote
	$h_{t}=f(X_{t})-f(\xsol)$ for each $t$, we reach
	\begin{equation}\label{eq:htht+1intermediatequantity}
	\begin{aligned}
	h_{t+1}\leq & h_{t}+(1-\eta)\underbrace{\inprod{W-X_{t}}{\nabla f(X_{t})}}_{R_1}\\
	            & +\frac{(1-\eta)^{2}\beta}{2}\underbrace{\fronorm{W-X_{t}}}_{R_2}.
    \end{aligned}
	\end{equation}
	Using Lemma \ref{lem:Let--and} and the inequality \eqref{eq:gapdifference},
	we can choose $W\in\face{\rsol}(\nabla f(X_{t}))$ such that
	\begin{align}
	\inprod{W-\xsol}{\nabla f(X_{t})} & \leq-\frac{\lambda_{n-\rsol}(\zsol)}{6}\fronorm{\xsol-W}^{2}.\label{eq:intermediateinequality2forlinearconvergence}
	\end{align}
	Let us now analyze the term $R_1=\inprod{W-X_{t}}{\nabla f(X_{t})}$
	using (\ref{eq:intermediateinequality2forlinearconvergence}) and convexity of $f$:
	\begin{equation*}
	\begin{aligned} \label{eq:inprodw-xtalgorithmtheorem}
	 R_1=   & \inprod{W-X_{t}}{\nabla f(X_{t})}\\
	  = & \inprod{W-\xsol}{\nabla f(X_{t})}+\inprod{\xsol-X_{t}}{\nabla f(X_{t})}\nonumber \\
	\leq&-\frac{\lambda_{n-\rsol}(\zsol)}{6}\fronorm{\xsol-W}^{2}-h_{t}.
	\end{aligned}
    \end{equation*}
	The term $R_2=\fronorm{X_{t}-W}^{2}$ can be bounded by
	\begin{equation*}
	\begin{aligned}
	R_2 = \fronorm{X_{t}-W}^{2} &\overset{(a)}{\leq}2\left(\fronorm{X_{t}-\xsol}^{2}+\fronorm{\xsol-W}^{2}\right)\\
	&\overset{(b)}{\leq}\frac{2}{\gamma}h_{t}+2\fronorm{\xsol-W}^{2},\label{eq:xt-walgorithminequality}
	\end{aligned}
	\end{equation*}
	where we use triangle inequality and the basic inequality $(a+b)^{2}\leq2a^{2}+2b^{2}$
	in step $(a)$, and the quadratic growth condition in step $(b)$.

	Now combining (\ref{eq:htht+1intermediatequantity}), and the bounds of $R_1$ and $R_2$, we reach that there is a
	$W\in\face{\rsol}(\nabla f(X_{t}))$ such that for any $\xi=1-\eta\in[0,1]$, we have
	\begin{align*}
	h_{t+1}
	\leq & h_{t}+\xi\left(-\frac{\lambda_{n-\rsol}(\zsol)}{6}\fronorm{\xsol-W}^{2}-h_{t}\right)\\
	+&\frac{\xi^{2}\beta}{2}\left(\frac{2}{\gamma}h_{t}+2\fronorm{\xsol-W}^{2}\right)\\
   =&\left(1-\xi+\frac{\xi^{2}\beta}{\gamma}\right)h_{t}\\
    +&\left(\xi^{2}\beta-\frac{\xi\lambda_{n-\rsol}(\zsol)}{6}\right)\fronorm{\xsol-W}^{2}.
	\end{align*}
	A detailed calculation and choice of $\xi$ in Section \ref{sec: AppendixSpectralFrank-WolfeAndItsConvergenceRate} in Appendix reveals that we can reach the second part of the theorem, the inequality \eqref{eq:secondparthm3}.
\end{proof}

\section{Quadratic Growth and Linear Convergence of Algorithms}\label{sec: QuadraticGrowthAndLinearConvergence}

In this section, we show that when $g$ is $\alpha$-strongly convex \cite{nesterov2013introductory}
and strict complementarity of (\ref{eq:Mainoptimization}) holds, then
we have quadratic growth of Problem (\ref{eq:Mainoptimization}).
We also demonstrate when the dual matrix $\zsol$ has rank $n-1$ then we do not require $g$ to be $\alpha$-strongly convex. An immediate consequence is
the linear convergence of PGD and APGD \cite{karimi2016linear}, the generalized blockFW\footnote{We show its convergence
under quadratic growth in Lemma \ref{lem: linearConvergenceOfBlockFW} in Section \ref{sec: lemmaForSection4} in the Appendix.} (Algorithm~\ref{alg:generalizedBlockFW}, and
the spectral Frank-Wolfe (Algorithm~\ref{alg:spectral_frank_wolfe}) as shown in Theorem \ref{thm:MainAlgorithmTheorem}.
\begin{thm}
	\label{thm:MainStructralTheorem}Suppose strict complementarity of
	(\ref{eq:Mainoptimization}) and one of the following conditions
	hold:

	(i) $g$ is $\alpha$-strongly convex, and the solution $\xsol$ is
	unique, or

	(ii) the dual matrix $\zsol$ in the KKT condition (\ref{eq:KKT})
	has rank $n-1$,

	then Problem~(\ref{eq:Mainoptimization}) satisfies quadratic
	growth. The constant $\gamma$ takes the form of

	(i) $\gamma=\min\left\{ \frac{\lambda_{n-\rsol}(\zsol)}{4+8\frac{\sigma_{\max}^{2}(\tilde{\Amap})}{\sigma_{\min}^{2}(\tilde{\Amap}_{V})}},\frac{\alpha\sigma_{\min}^{2}(\tilde{\Amap}_{V})}{8}\right\} $
	in the first case, where $\tilde{\Amap}(X)=\begin{bmatrix}\tr(X)\\
	\Amap(X)
	\end{bmatrix}$, and

	(ii) $\gamma=\frac{\lambda_{n-\rsol}(\zsol)}{2}$ in the second case. In addition, the uniqueness of $\xsol$ is  implied in the second case.
\end{thm}

\begin{proof}
	The second case has been verified in \citet[Lemmas 1 and 2]{garber2019convergence}. We
	provide a self-contained and different proof in Section \ref{sec: lemmaForSection4} in
	Appendix.

	Now consider the first case. For any feasible $X$ and the optimal
	solution $\xsol,$ we have
	\begin{equation} \label{eq: optimalitygStrongconvexityInequality}
	\begin{aligned}
            	    &f(X)-f(\xsol)\\
                   =& g(\Amap X)-g(\Amap\xsol)+\inprod C{X-\xsol}\\
\overset{(a)}{\geq}	& \inprod{(\nabla g)(\Amap\xsol)}{\Amap(X-\xsol)}\\
               	   +&\inprod C{X-\xsol}+\frac{\alpha}{2}\twonorm{\Amap X-\Amap\xsol}^{2} \\
\overset{(b)}{=}	& \inprod{\Amap^{*}(\nabla g)(\Amap\xsol)+C}{X-\xsol}\\
	               +&\frac{\alpha}{2}\twonorm{\Amap X-\Amap\xsol}^{2} \\
	\overset{(c)}{=}& \inprod{\zsol+\ssol I}{X-\xsol}+\frac{\alpha}{2}\twonorm{\Amap(X-\xsol)}^{2} \\
\overset{(d)}{=}	& \inprod{\zsol}X+\frac{\alpha}{2}\twonorm{\Amap(X-\xsol)}^{2}\overset{(e)}{\geq}0
	\end{aligned}
    \end{equation}
	Here step $(a)$ is due to the strong convexity of $g$. Step $(b)$
	is because of the definition of $\Amap^*$. For step $(c)$, we uses
	the first order condition of KKT condition (\ref{eq:KKT}) in terms
	of $g$ and $\Amap$: $\Amap^{*}(\nabla g)(\Amap\xsol)+C-\zsol-\ssol I=0.$
	The step $(d)$ is due to the complementarity in KKT condition (\ref{eq:KKT})
	and feasibility of $X$ and $\xsol.$ The last inequality $(e)$ is
	beacause $Z,X\succeq0.$

	We claim that a feasible matrix $X\in\symMat^{\dm}$ is optimal if and only
	if $X$ satisfies
	\begin{equation} \label{eq:linearmatrixinequalityoptimalcondition}
	\begin{aligned}
	\inprod{\zsol}X  =0,\quad
	\Amap X -\Amap\xsol=0,\\
	\tr(X)  =1,\quad\text{and}\quad
	X  \succeq0.
	\end{aligned}
    \end{equation}
	Indeed, if $X$ is optimal, then \eqref{eq: optimalitygStrongconvexityInequality}
	and feasibility of $X$ implies \eqref{eq:linearmatrixinequalityoptimalcondition}.
    Conversely, if $X$ satisfies \eqref{eq:linearmatrixinequalityoptimalcondition}, then it
    satisfies the KKT condition
    \eqref{eq:KKT} and hence it is optimal because the problem \eqref{eq:Mainoptimization} is convex.
	Since the optimal solution is unique by assumption, we know the system
	(\ref{eq:linearmatrixinequalityoptimalcondition}) admits a unique
	solution. Using Lemma \ref{lem:Suppose-the-following} in Section \ref{sec: lemmaForSection4} in the Appendix, we have the
	relationship between $(\inprod{\zsol}X,\twonorm{\Amap(X-\xsol)})$
	and the distance to the solution $\fronorm{X-\xsol}$:
	\begin{equation}\label{eq:xxsolzxax-brelation}
	\begin{aligned}
	\fronorm{X-\xsol}^{2}&\leq\left(4+8\frac{\sigma_{\max}^{2}(\tilde{\Amap})}{\sigma_{\min}^{2}(\tilde{\Amap}_{V})}\right)\frac{\inprod{\zsol}X}{\lambda_{n-\rsol}(\zsol)}\\
	&+\frac{4}{\sigma_{\min}^{2}(\tilde{\Amap}_{V})}\twonorm{\Amap(X)-b}^{2}.
	\end{aligned}
	\end{equation}
	Combining  \eqref{eq: optimalitygStrongconvexityInequality} and (\ref{eq:xxsolzxax-brelation}),
	we see that
	\[
	f(X)-f(\xsol)\geq\gamma\fronorm{X-\xsol}^{2}
	\]
	for $\gamma=\min\left\{ \frac{\lambda_{n-\rsol}(\zsol)}{4+8\frac{\sigma_{\max}^{2}(\tilde{\Amap})}{\sigma_{\min}^{2}(\tilde{\Amap_{V})}}},\frac{\alpha\sigma_{\min}^{2}(\tilde{\Amap}_{V})}{8}\right\} $.
\end{proof}

\section{Numerics}\label{sec: numerics}
In this section, we verify numerically a few of our claims in the paper,
and show the advantages of the Spectral Frank-Wolfe algorithm when strict complementarity
is satisfied and the solution rank is larger than $1$. We focus on the
quadratic sensing problem \cite{chen2015exact}. Given a random matrix $U_{\natural}\in \real^{\dm\times r_\natural}$ with
$r_\natural =3$ and Frobenius norm $\fronorm{U_\natural }^2 =1$,
we generate Gaussian vectors $a_i\in \real^{\dm\times 1},i=1,\dots,m$ and construct
quadratic measurement vectors $y_0(i) = \fronorm{U_\natural ^\top a_i}^2,i=1,\dots,m$. We then add noise
$\mathtt{n}=c \twonorm{y_0}v$, where $c$ is the inverse signal-to-noise ratio and $v$ is a random unit vector. Our
observation is given by $y= y_0 + \mathtt{n}$ and we aim to recover $U_\natural U_\natural ^\top$ from $y$. To this end, we solve the following optimization problem:
\begin{equation}\label{eq: quadraticSensing}
\begin{aligned}
\mbox{minimize}\quad & f(X):=\frac{1}{2}\sum_{i=1}^m\left(a_i^\top Xa_i-y_i\right)^2 \\
\mbox{subject to\ensuremath{\quad}} & \tr(X)=\tau, \quad X\succeq 0.
\end{aligned}
\end{equation}
We set $m = 15n r_\natural$ in all our experiments.

\paragraph{Low rankness and strict complementarity.} We verify the low rankness
and strict complementarity for $n=100,200,400$ and $600$. We set $c=0.5$ for the noise Level.
We also set $\tau =0.5$, since otherwise, the optimal solution will fit the noise and results in a higher rank matrix.
Problem \eqref{eq: quadraticSensing} is solved via FASTA \cite{GoldsteinStuderBaraniuk:2014, FASTA:2014}. We found
that every optimal solution rank in this case is $\rsol =3$, and there is indeed a significant gap between
$\lambda_{n-3}(\nabla f(\xsol))$ and $\lambda_{n}(\nabla f(\xsol))$, which verifies strict
complementarity. More details can be found in Table \ref{table: LowRankandStricComplementarity}.
\begin{table} \label{table: LowRankandStricComplementarity}
\centering
\begin{tabular}{ccc}
 	\toprule
 	Dimension $n$ & Avg. gap  & Avg. recovery error \\
 	\midrule
 	100 & 288.06  &0.0013 \\
 	200 & 505.16 & 0.00064 \\
 	400 & 961.09  & 0.00031\\
 	600 & 1358.62 & 0.00021\\
    \bottomrule
\end{tabular}
\caption{Verification of low rankness and strict complementarity. The
recovery error is measured by $\frac{\fronorm{\frac{\xsol}{\tau}-U_\natural U_\natural^\top}}{\fronorm{U_\natural U_\natural^\top}}$.
The gap is measured by $\lambda_{n-3}(\nabla f(\xsol))-\lambda_{n}(\nabla f(\xsol))$. All the results is averaged over $20$ iid trials.}
\end{table}
\paragraph{Comparison of algorithms.} We now compare the performance of
FW, G-BlockFW, and SpecFW. We follow the setting as the previous paragraph for
$n=100,200,400$, and $600$.

We set $k=4$
for both SpecFW and G-BlockFW, which is larger than $\rsol=3$.
We also set $\eta =0.4$ and
$\beta = 2.5n^2$.\footnote{This choice might
appear conservative. But we note that $a_i$ has length around $\sqrt{n}$. Hence the operator norm
of $\Amap$ is around $\sqrt{m}n$ ($\inprod{a_ia_i^\top}{X}\leq \fronorm{a_i}^2\fronorm{X}\approx n\fronorm{X}$), which suggests $L_f=\opnorm{\Amap}^2=n^2m$ as a safe choice. We have
already omitted one $m$ factor here for better algorithmic performance.}
The small-scale SDP \eqref{eq: smallksubproblem} is solved via FASTA.
We plot the relative objective value against both the time and iteration counter in Figure~\ref{fig:riskCover}. We only present the plot for the case of $n=600$ here and those for the other cases  can be found in Section \ref{sec: additionalNumerics} in the Appendix. As can be seen from Figure \ref{fig:riskCover}(a), SpecFW
converges faster in terms of both the iteration counter and the time. The oscillation in the end
may be attributed to the sub-problem solver.
\paragraph{Misspecification of $k$.} We adopt the same setting as before. In this
experiment, we set $k=2$ for both SpecFW and G-BlockFW, which is less than $\rsol=3$. As can be seen from the Figure \ref{fig:riskCover}(b),
SpecFW still converges as fast as FW (the two line coincide). G-BlockFW gets stuck around $10^{-1}$ and
stop converging to the optimal solution.

\begin{figure}[t!]
	\begin{center}
		\subfigure[$k> \rsol$]{\includegraphics[width=1\linewidth]{CorrectRank600.pdf}}
		\subfigure[$k< \rsol$]{\includegraphics[width=1\linewidth]{missspecifiedk600.pdf} }

	\end{center}
	\caption{Comparison of algorithms under different setting.
	$f^\star$ is obtained from the best value of the three methods and FASTA.}
	\label{fig:riskCover}
\end{figure}
\section{Discussion}
In this paper, we propose the Spectral Frank-Wolfe algorithm, a novel variant of the classical Frank-Wolfe algorithm, which converges sublinearly for convex smooth optimization problems and converges linearly when strict complementary is satisfied for structural convex optimization problems. We also show that the quadratic growth condition, which is essential for linear convergence of first order methods, holds under strict complementarity.

Here we discuss two potential (and hopefully interesting) extensions of the current paper:
\begin{itemize}
	\item \textbf{Total computational complexity:} The complexity of subproblem \eqref{eq: smallksubproblem} is not discussed and hence leave the total complexity unresolved. Simply using the known $\mathcal{O}(\frac{1}{\sqrt{\epsilon}})$ result of APG for the subproblem complexity seems to be too pessimistic. Is it possible to improve this complexity to $\mathcal{O}(\log(\frac{1}{\epsilon}))$?
	\item \textbf{Solving Subproblem \eqref{eq: smallksubproblem} by sub-sampling?} In many applications, $f$ is of a finite sum structure with $m$ terms, e.g., matrix completion, and quadratic sensing. The number $m$ is usually on the order $\dm \rsol$. In the subproblem \eqref{eq: smallksubproblem}, the decision variable has size $\mathcal{O}(k^2)$, which can be much smaller than $m$. It might be
	unwise to use all the $m$ terms. Can we sub-sample the $m$ terms to reduce the burden of computing gradient?
\end{itemize}

\section*{Acknowledgements}
L. Ding and Y. Fei were supported by the National Science Foundation CRII
award 1657420 and grant 1704828.
C. Yang was supported in part by DARPA Award FA8750-17-2-
0101. We would like to thank Yudong Chen, Madeleine Udell,
James Renegar, and Adrian Lewis for helpful discussions.

\bibliography{example_paper}
\bibliographystyle{icml2020}

\input appendix
\end{document}


TITLE: T and S are invertible and why (ST) is invertible too?
QUESTION [1 upvotes]: I have functions T and S such that T : V -> V  and S : V->V
and S and T are invertible.
Prove why composition of (ST) is invertible too.
I tried to figure it out by letting TS=ST, and TS and ST are linear.
but I am stuck...

REPLY [1 votes]: The proof has two distinct aspects.

If $f:A\to B$ and $g:B\to C$ are any invertible (= bijective) maps between sets, then their composition $g\circ f:A\to C$ is always also invertible. The inverse is the composition of $\def\'{^{-1}}g\':C\to B$ and $f\':B\to A$, in other words $(g\circ f)\'=f\'\circ g\'$. This part is completely general and has no specific relation to linear algebra.
If a map between vector spaces $T:V\to W$ is both linear and bijective (invertible as a map of sets), then the inverse map of sets $f\':W\to V$ is also linear. This is a pure linear algebra fact that should be one of the first things to know about invertible linear maps. It's proof looks a bit tricky, but it you think of it is quite natural (use the linearity of $f$ in the opposite sense, after inserting back-and-forth maps to make $f$ appear in the first place):
$$
  f\'(\lambda w_1+\mu w_2)
 =f\'\bigl(\lambda f(f\'(w_1))+\mu f(f\'(w_2))\bigr)
 =f\'\bigl( f\bigl(\lambda f\'(w_1)+\mu f\'(w_2)\bigr)\bigr)
 =\lambda f\'(w_1)+\mu f\'(w_2).
$$

Now all that is left is apply it to your situation: $ST$ in a bijective map (1) with inverse $T\'S\'$, and (2) this inverse is a linear map (since you checked that $ST$ is linear).


TITLE: Integral of $\frac{1}{100-x}$
QUESTION [2 upvotes]: I don't understand how the integral below:
\begin{align}
\int{\frac{1}{100-x}dx} = \ -\log|x-100| +c
\end{align}
When I integrate I get the answer:
\begin{align}
\ -\log|100-x| +c
\end{align}
I understand that it probably has something to do with the absolute value function, would someone kindly explain it to me? Thanks!

REPLY [0 votes]: $$\left|\prod_{i=1}^{n}x_i\right|=\prod_{i=1}^{n}\left|x_i\right|$$This property, which basically says that absolute value of product is same as the product of individual absolute values, implies that $\left|100-x\right|$ can be rewritten as $\left|-1\right|\cdot\left|x-100\right|$ which equals $\left|x-100\right|$.


TITLE: Solution of an integral with the interval 1, x^4
QUESTION [0 upvotes]: I want to find
$$\frac{d}{dx}\int_1^{x^4} \sec t\ dt.$$
How would one go about resolving this integral? I am having problems after I substitute $x^4$ with $u.$

REPLY [0 votes]: Let $g(x) = \int_0^x \sec(t) \,\mathrm{d}t$.  Then you want $\frac{\mathrm{d}}{\mathrm{d}x} g(x^4)$, which you should be able to do by the chain rule and the fundamental theorem of calculus (which tells you want $g'(x)$ is).

REPLY [0 votes]: It is the derivative of a composite function.
You have one function
 $$g(x)=x^4$$ and another function $$ F(x) = \int _0 ^ x \sec t dt $$
$$\frac{d}{dx}\int_0^{x^4} \sec t\, dt =  4x^3 \sec (x^4)$$
Can you figure it out using the fundamental theroem of calculus?

REPLY [0 votes]: By the Fundamental Theorem of Calculus,
$$\frac{\mathrm d}{\mathrm dx} \int_{a}^{x}f(t) \mathrm{dt} = f(x)$$
Notice that the bound involves $x$ rather than a function of $x$. When you have a function of $x$ instead, simply use the Chain Rule:
$$\frac{\mathrm dy}{\mathrm dx} = \frac{\mathrm dy}{\mathrm du} \cdot \frac{\mathrm du}{\mathrm dx}$$
Combining both gives
$$\frac{\mathrm d}{\mathrm dx} \int_{a}^{u}f(t) \mathrm{dt} = \left(\frac{\mathrm d}{\mathrm du} \int_{a}^{u}f(t) \mathrm{dt}\right) \cdot \frac{\mathrm du}{\mathrm dx} = f(u) \cdot u'$$
Here, $u = x^4$, so $u' = 4x^3$, and $f(u)$ simply becomes $\sec(u) = \sec\left(x^4\right)$.

REPLY [0 votes]: Use chain rule and Fundamental Theorem of Calculus. Differentiate the integral first then the upper bound of the integral. (i.e)
$$\int_1^{x^4} \sec (t) dt$$
When you take its derivative, this becomes
$$4x^3 \sec (x^4)$$
This happened by both Chain Rule and FTC - Part I


TITLE: Closure of a sigma algebra and complete measure spaces
QUESTION [0 upvotes]: Suppose $<X,M,\mu>$ is a measure space and $\overline{M}=\{A:\exists B,C \in M, B\subset A \subset C\ \text{and}\ \mu(C \smallsetminus B)=0\}$ is the closure of the $\sigma$-algebra $M$. I'm trying to understand the proof of this theorem: $M=\overline{M}$ if and only if $<X,M,\mu>$ is complete.
Proof
$(\rightarrow)$ Suppose $M=\overline{M}$, then, choose $E=A\cup N$ where $A \in M$ and $N$ is a null subset, then $E \in M$.
Suppose $E \subset A \in M$ and $\mu(A)=0$, take $N=A\smallsetminus E$, then $E \in M$.
Is the first line used for something?, Why $E \in M$ in the second line?

REPLY [1 votes]: Let me try to reword the argument for $(\implies)$. We are supposing $\mathcal{M} = \overline{\mathcal{M}}$, and we have to show $(X,\mathcal{M}, \mu)$ is complete.
Ok, so let $N \in \mathcal{M}$ be any set with $\mu(N) = 0$, and take any subset $A \subset N$. We have to show that $A \in \mathcal{M}$ (showing completeness means we have to show every subset of a measurable-null set is measurable). Now, notice that
\begin{align}
\emptyset \subset A \subset N \qquad \text{and} \qquad \mu(N \setminus \emptyset) = \mu(N) = 0.
\end{align}
This says exactly that $A \in \overline{\mathcal{M}}$ (I took $B = \emptyset$ and $C=N$ in the definition of $\overline{\mathcal{M}}$). So, $A \in \overline{\mathcal{M}} = \mathcal{M}$, where the last equal sign is by hypothesis. This is exactly what we had to show to prove $(X,\mathcal{M}, \mu)$ is complete.


TITLE: Can we say that this matrix is in row reduced echelon form?
QUESTION [1 upvotes]: Can we say that this matrix is in row reduced echelon form?
\begin{bmatrix}1&0&0&3&1\\0&0&1&0&0\\0&0&0&0&1\\0&0&0&0&0\end{bmatrix}
I know that, it has leading numbers as 1 and other rows are zeros.
Is there a rule to have columns which have all zeros need to occur the beginning?
Your help is highly appreciated. Thank you.

REPLY [1 votes]: No, columns of 0s don't have to appear at the beginning. There is no such rule as that. You are more interested in the rows. The only two rules are

the zero rows are at the bottom

the leading coefficient of a nonzero row is to the right of the one above it, if they were placed in the same row

Your matrix satisfies these two and thus is in row echelon form. But to get it in reduced row echelon form, it must be that

Any column that contains a pivot has 0 in all other entries.

the pivots are all 1's

So, to put your matrix in rref you subtract row 3 from row 1
$$\begin{bmatrix}1&0&0&3&0\\0&0&1&0&0\\0&0&0&0&1\\0&0&0&0&0\end{bmatrix}$$


text:
\section{Alternating Sum and Difference of r Choose k up to n}
Tags: Binomial Coefficients, Alternating Sum and Difference of r Choose k up to n

\begin{theorem}
:$\displaystyle \sum_{k \mathop \le n} \paren {-1}^k \binom r k = \paren {-1}^n \binom {r - 1} n$
\end{theorem}

\begin{proof}
{{begin-eqn}}
{{eqn | l = \sum_{k \mathop \le n} \paren {-1}^k \binom r k
      | r = \sum_{k \mathop \le n} \binom {k - r - 1} k
      | c = [[Negated Upper Index of Binomial Coefficient]]
}}
{{eqn | r = \binom {-r + n} n
      | c = [[Sum of r+k Choose k up to n]]
}}
{{eqn | r = \paren {-1}^n \binom {r - 1} n
      | c = [[Negated Upper Index of Binomial Coefficient]]
}}
{{end-eqn}}
{{qed}}
\end{proof}

config: wiki


TITLE: What exactly is a R-matrix?
QUESTION [5 upvotes]: I am a beginner trying to figure out what is a R-matrix, in relation to the Yang-Baxter Equation.
The entry at wikipedia is a little too short.
I have read that a solution to the Yang-Baxter equation satisfies:
$R_{12}R_{13}R_{23}=R_{23}R_{13}R_{12}$
Does the above relation apply to R-matrices too?
Thanks a lot.

REPLY [8 votes]: If I recall - and I seem to have misplaced my copy of Kassel - what you have written is the definition of the (quantum) Yang-Baxter equation.
What I know of this stuff is from the quantum group point of view. There's a bunch of physics that this comes from but unfortunately I know little of this.
An $R$-matrix in this setting is the following. Let $(H,\mu,\eta,\Delta,\epsilon,S)$ be a Hopf algebra. A universal R-Matrix is an invertible element $R=R^{(1)}\otimes R^{(2)}\in H\otimes H$, which satisfies the equations,
$$(\Delta \otimes 1)(R) = R_{13} \ R_{23},$$
$$(1 \otimes \Delta)(R) = R_{13} \ R_{12},$$
where $R_{13}$, for example, is given by $R^{(1)}\otimes 1\otimes R^{(2)}$. (The subscripts tell you where to "put" the components of $R$.)
One can prove, from these equations, that $R$ actually satisfies the Yang-Baxter equation. I recommend Christian Kassel's "Quantum Groups" for the proof - or if you're generally interested in this stuff.
What's cool (in my opinion) about $R$-matrices and this quantum group business (a Hopf algebra with an element $R$ as above is actually one definition of "quantum group") is that a certain subcategory of its finite dimensional representations has very interesting properties. I recommend Bakalov and Kirillov Jr.'s "Lectures on tensor categories and modular functors" if you want to know more about this, though Kassel gives a pretty good exposition of the tangle category stuff.
So... in a very roundabout way, I suppose my answer is yes, if you're talking about this stuff in the context of quantum groups. I think there are a number of ways of talking about $R$-matrices, and I can only speak for this one.
I think Hong and Kang's "Introduction to Quantum Groups and Crystal Bases" has a chapter that has a pretty good introduction to the physical stuff. XXZ or models or whatnot. It's a cool book in general, too.
Anyway, hope that helps.


TITLE: Isomorphism by restricting surjective linear mapping between finite dimensional spaces, and quotient space by null space
QUESTION [1 upvotes]: In Axler's book Linear Algebra Done Right, Section 3D, Exercise 8:
Suppose $V$ is finite-dimensional and $T:V\rightarrow W$ is a surjective linear map of $V$ onto $W$. Prove that there is a subspace $U$ of $V$ such that $\left.T\right|_U$ is an isomorphism of $U$ onto $W$. (Here $\left.T\right|_U$ means the function $T$ restricted to $U$. In other words, $\left.T\right|_U$ is the function whose domain is $U$, with $\left.T\right|_U$ defined by $\left.T\right|_U (u)=Tu$ for every $u\in U$.)
An immediate solution would be considering a basis $w_1, \dots, w_m$of $W$. Then there exists $v_1, \dots, v_m \in V$, linearly independent, and $Tv_i=w_i$. Let $U =$ span($v_1, \dots, v_m$), then we get an isomorphism $\left.T\right|_U : U\rightarrow W$.
My question is that do we have $U = V/(\operatorname{null}T)$, where $V/(\operatorname{null}T)$ is the quotient space of $V$ by null$T$? And do we have  $\left.T\right|_U = \tilde{T}$, where $\tilde{T}: V/(\operatorname{null}\to W)$ is defined by
$\tilde{T}(v+\operatorname{null}T)=Tv$?

REPLY [3 votes]: Given finite-dimensional $k$-vector spaces $V$ and $W$ with a surjective linear transformation $T : V \to W,$ by the First Isomorphism Theorem, there exists a unique linear transformation $S : V / \ker T \to W$ such that $T = S \circ P,$ where $P : V \to V / \ker (T)$ is the canonical surjection defined by $P(v) = v + \ker T.$ Consequently, your intuition is essentially correct; however, it is not technically true that $U = V / \ker T.$
We will need to do things in a slightly different order than your proof, but we will ultimately establish that $V = U \oplus \ker T$ so that $U$ can be identified (by the First Isomorphism Theorem) with the quotient space $V / \ker T.$ Recall that any linearly independent set of fewer than $\dim V = n$ vectors can be extended to a basis for $V.$ Consequently, we may extend a basis $\{v_{m + 1}, \dots, v_n \}$ of $\ker T$ to a basis $\{v_1, \dots, v_m, v_{m + 1}, \dots, v_n \}$ of $V,$ where we denote $\dim W = m.$ We may define (as you have) the subspace $U = \operatorname{span}_k \{v_1, \dots, v_m \}.$ We claim that $T(U) = W$ so that $T|_U : U \to W$ is surjective and therefore an isomorphism. Given any vector $w$ in $W,$ there exists a vector $v$ in $V$ such that $T(v) = w$ by hypothesis that $T$ is surjective. Using our basis, we may write $v = a_1 v_1 + \cdots + a_m v_m + a_{m + 1} v_{m + 1} + \cdots + a_n v_n,$ from which it follows that $$\begin{align} w = T(v) &= T(a_1 v_1 + \cdots + a_m v_m + a_{m + 1} v_{m + 1} + \cdots + a_n v_n) \\ \\ &= T(a_1 v_1 + \cdots + a_m v_m) + a_{m + 1} T(v_{m + 1}) + \cdots + a_n T(v_n) \\ \\ &= T(a_1 v_1 + \cdots + a_m v_m) \end{align}$$ by hypothesis that $v_{m + 1}, \dots, v_n$ are basis elements for $\ker T.$ We have therefore that every vector $w$ of $W$ can be written as $T(u)$ for some vector $u$ in $U$ so that $T(U) = W,$ as desired.
Last, in order to prove that $V = U \oplus \ker T,$ we must show two things: (1.) $V = U + \ker T$ and (2.) $U \cap \ker T = \{0\}.$ Considering that $\{v_1, \dots, v_m, v_{m + 1}, \dots, v_n \}$ is a basis for $V$ such that $\{v_1, \dots, v_m \}$ is a basis for $U$ and $\{v_{m + 1}, \dots, v_n \}$ is a basis for $\ker T,$ the first condition holds. Given a vector $v \in U \cap \ker T,$ we have that $v = a_1 v_1 + \cdots + a_m v_m$ and $v = a_{m + 1} v_{m + 1} + \cdots + a_n v_n,$ from which it follows that $$a_1 v_1 + \cdots + a_m v_m - a_{m + 1} v_{m + 1} - \cdots - a_n v_n = 0.$$ But this implies that $a_1 = \cdots = a_m = a_{m + 1} = \cdots = a_n = 0$ so that $v = 0,$ as desired.

Perhaps this means nothing to you at the moment, but this is a consequence of a more general notion: we say that a short exact sequence of $R$-modules $$0 \to L \xrightarrow \varphi M \xrightarrow \psi N \to 0$$ splits if there exists an isomorphism $\gamma : M \to L \oplus N$ such that $\gamma \circ \varphi : L \to L \oplus N$ is the inclusion map and $\psi \circ \gamma^{-1} : L \oplus N \to N$ is the canonical surjection into the second coordinate. Given that $R = k$ is a field, we refer to an $R$-module (or a $k$-module, as it were) as a $k$-vector space. Every $k$-vector space is free as an $R$-module, and every free $R$-module is projective. Every short exact sequence of $R$-modules that ends with a projective $R$-module splits. By the First Isomorphism Theorem, we obtain the short exact sequence $$0 \to \ker T \xrightarrow i V \xrightarrow T W \to 0,$$ where $i : \ker T \to V$ is the inclusion map. By identifying $W$ and $V / \ker T,$ we obtain the short exact sequence $$0 \to \ker T \xrightarrow i V \xrightarrow P \frac V {\ker T} \to 0.$$ Ultimately, this is all to say that this behavior you intuitively detected is predictable and always works.