text:
\begin{document}

\title{SWAGGER: Sparsity Within and Across Groups for General Estimation and Recovery}

\author{Charles Saunders

and Vivek K Goyal

}

\markboth{}{Saunders \& Goyal: SWAGGER}
\maketitle

\begin{abstract}
Penalty functions or regularization terms that promote structured solutions to optimization problems are of great interest in many fields. Proposed in this work is a nonconvex structured sparsity penalty that promotes one-sparsity within arbitrary overlapping groups in a vector. This allows one to enforce mutual exclusivity between components within solutions to optimization problems. We show multiple example use cases (including a total variation variant), demonstrate synergy between it and other regularizers, and propose an algorithm to efficiently solve problems regularized or constrained by the proposed penalty.
\end{abstract}

\begin{IEEEkeywords}
sparsity, structured sparsity, group sparsity, regularization, inverse problems
\end{IEEEkeywords}

\IEEEpeerreviewmaketitle

\def\figurename{Fig.}

\section{Introduction}

\IEEEPARstart{S}{parsity}-promoting regularization is an integral component of modern-day signal processing, optimization and machine learning.
The most prevalent method,
LASSO~\cite{LASSO}, uses the $\ell_1$ norm to promote solutions to optimization problems that have few nonzero coefficients.
More recently, within some application domains there has been significant interest in structured sparsity.
For instance, group sparsity aims to set entire groups of components within a vector entirely to zero and allow the components in other groups to take on any value~\cite{GLASSOthesis}.
This is often achieved by regularizing with the $\ell_{2,1}$ norm over groups,
called group LASSO (\mbox{G-LASSO})~\cite{GLASSO}.

Conversely, there is interest in sparsity penalties that promote intra-group sparsity, that is, ensuring groups within a vector are themselves sparse. Such penalties have been used to great success in areas such as deep learning~\cite{NNsparsity}, computer vision~\cite{computervision1,computervision2}, and medicine~\cite{medicineEEG,medicinefMRI}.
Previous work in this area includes elitist~\cite{ELASSO1,ELASSO2}, or exclusive LASSO (E-LASSO)~\cite{ELASSO3}
formulations that are convex and result in sparse, disjoint groups, and the nonconvex ‘sparsity within and across groups’ (SWAG)~\cite{SWAG1} plus extensions~\cite{SWAG2} that allow for overlapping groups of components.

We propose here a more general, nonconvex structured sparsity penalty that allows for sparsity within and across overlapping groups for general estimation and recovery (SWAGGER).
The SWAGGER formulation encodes mutual exclusivity between pairs of components, or a transform of the components, using an easily constructed sparsity structure matrix.
This results in one-sparse groups with minimal bias in the nonzero entries, where bias is typically an unwanted byproduct of using convex sparsity penalties such as elitist LASSO\@.
We demonstrate the utility of SWAGGER in a number of settings, including a novel total variation-style denoising in one and two dimensions and modeling occlusions plus allowing mutually exclusive discretizations in imaging problems.
Additionally, we introduce a novel algorithm to efficiently solve problems regularized or constrained by this proposed penalty.

\section{Proposed penalty}

We introduce a general structured sparsity penalty
\begin{equation}
 R(\Vecx) = \Phi(\VecB \Vecx) \transpose \VecS \Phi(\VecB \Vecx),
\label{eqn:IQ}
\end{equation}
for $\Vecx \in \mathbb{R}^N$.
For certain choices of
the matrix $\VecB \in \mathbb{R}^{M \times N}$, where $M$ is any integer,
function $\Phi : \mathbb{R}^M \rightarrow \mathbb{R}^M$,
and matrix $\VecS \in \mathbb{R}^{M \times M}$,
this penalizes deviation from a selected form of structured sparsity.
Possible prototypes for $\VecB$ include the identity matrix, finite difference matrices, or a transform to a different basis; see Section~\ref{sec:examples}.
The function $\Phi$ introduces a nonlinearity that helps to bound the penalty from below. We constrain $\Phi$ in Prop.~\ref{prop:constraints} below, and examples are discussed in Section~\ref{sec:phichoice}.
The matrix $\VecS$ is key, as it encodes the structural sparsity properties. We define $\VecS$ as:
\begin{equation}
    \VecS_{i,j} = \VecS_{j,i} = \mu,
    \label{eqn:Sdef}
\end{equation}

where $\mu \in [0,1]$ is the \emph{strength of exclusivity} between a pair of components, $\Phi(\VecB \Vecx)_i$ and $\Phi(\VecB \Vecx)_j$.
When $\mu = 0$, there is no exclusivity between the two components.
When $\mu > 0$, it indicates that the two components should not be nonzero simultaneously (with the strength of exclusivity increasing with $\mu$).
We bound $\mu$ in the [0,1] range for convenience and note that any scaling can be absorbed into a multiplicative regularization parameter.
Given this interpretation, the diagonal of $\VecS$ will be zero and hence $\VecS$ will typically be indefinite, resulting in nonconvexity. Examples for $\VecS$ are given in Section~\ref{sec:Schoice}.

In order for the penalty function to be useful in regularizing minimization problems, it must be bounded from below.
Prop.~\ref{prop:constraints} provides simple sufficient conditions for this (proof in Appendix~\ref{sec:penbounds}).

\medskip

\begin{prop}
\label{prop:constraints}
In order for \eqref{eqn:IQ} to be bounded from below, it is sufficient to require:
\begin{enumerate}
    \item $\VecS_{i,j} \geq 0 \quad \fa (i,j) \in \{1,2,\ldots,M\}^2$; and
    \item $\Phi(\Vecx) \geq 0 \; \mbox{elementwise} \; \fa \Vecx$.
\end{enumerate}
\end{prop}

The definition for $\VecS$ in \eqref{eqn:Sdef} meets condition 1) in Prop.~\ref{prop:constraints}.
Except for a discussion of extensions in Section~\ref{sec:phichoice},
we assume $\Phi(\Vecx)$ is the absolute value $|\Vecx|$, which satisfies condition 2).

\section{Properties of the SWAGGER penalty}

When $\Phi(\cdot) = |\cdot|$, the Hessian of the penalty is given by
\begin{equation*}
    \nabla^2_\Vecx R(\Vecx) = 2 \, \VecX \, \VecS \, \VecX,
\end{equation*}
where $\VecX = \diag(\sign(\Vecx))$.
The sparsity structure matrix, $\VecS$, is symmetric and has zeros along its main diagonal.
$\VecS$ must be indefinite as it has at least one positive eigenvalue (see~\cite{eigbound}) and
the sum of the eigenvalues is zero (since the trace of a symmetric matrix
is equal to the sum of its eigenvalues
and $\Tr(\VecS) = 0$).
The Hessian has the same structure and can therefore not be positive semidefinite outside of the trivial case where $\Vecx = 0$.
Thus, the penalty is \emph{always} nonconvex for practical purposes.
More analysis of the eigenvalues of matrices of this kind can be found in~\cite{hollowmatrix}.

We can compare SWAGGER with the convex E-LASSO penalty, which uses the $\ell_1$-squared norm to achieve intra-group sparsity.
In the case of a one-sparse group (see Section~\ref{sec:onesparse}), we can introduce a modified sparsity matrix, $\VecS_\eta = \mathbbm{1}\mathbbm{1}\transpose - \eta \VecI$, where scalar parameter $\eta \in [0,1]$ gives us E-LASSO for $\eta = 0$ and SWAGGER for $\eta = 1 $:
\begin{equation*}
|\Vecx| \transpose \VecS_\eta  |\Vecx| = \|\Vecx\|_1^2 - \eta  \|\Vecx\|_2^2.
\end{equation*}
When $\eta =1$, we see the introduction of the $- \eta  \|\Vecx\|_2^2$ term which both de-biases the penalty and also ensures the penalty equals zero when $\Vecx$ is one-sparse. For a more general $\VecS$, the closest convex penalty would be to replace $\VecS$ with $\VecS - c \VecI$, where $c$ takes on the value of the smallest eigenvalue of $\VecS$.

\paragraph*{Maintaining convexity of a full cost function}
There has recently been interest in so called `convex nonconvex' sparsity regularization where parameters of a nonconvex penalty are set to values that maintain convexity of the full cost function with the data fidelity, e.g.,~\cite{Selesnick2017}.
This is achievable with the SWAGGER penalty, also.
Consider the problem of minimizing a cost function of the form
$\frac{1}{2} \| \VecA \Vecx - \Vecy \|_2^2 + \lambda |\Vecx| \transpose \VecS |\Vecx|$.
One can replace $\VecS$ with $\VecS - c\VecI$, where
$c = \lambda_\text{min}(\VecS) + \frac{1}{2 \lambda}  \lambda_\text{min}(\VecA \transpose \VecA)$,
to achieve nonconvex regularization whilst maintaining the overall convexity of the problem (see derivation in Appendix~\ref{sec:cnc}).
This is only useful when the smallest eigenvalue of $\VecA \transpose \VecA$ is not too small and the regularization strength parameter $\lambda$ is not too large.
The work presented outside of this section is only focused on the use of the unmodified $\VecS$, but further analysis of the intermediate convexity paradigm may be of interest.

\section{Notable cases for $\VecS$}
\label{sec:Schoice}

\subsection{Canonical One-sparsity}
\label{sec:onesparse}
Define $\Phi(\cdot) = |\cdot|$ and $\VecB = \VecI$.
In this case, we obtain
\begin{equation}
 R(\Vecx) = |\Vecx| \transpose \VecS |\Vecx|.
\label{eqn:IQAbs}
\end{equation}
This is the `sparsity within and across overlapping groups' formulation which is introduced in~\cite{SWAG2}.
If we chose
$\VecS = \mathbbm{1}\mathbbm{1}\transpose - \VecI$,
where $\mathbbm{1}$ is a column vector of 1s of appropriate dimension,
then we see that
\begin{equation}
\begin{split}
 R(\Vecx) & = |\Vecx| \transpose \VecS |\Vecx| = |\Vecx| \transpose (\mathbbm{1}\mathbbm{1}\transpose - \VecI)|\Vecx|  \\ & = (|\Vecx| \transpose \mathbbm{1})^2 - |\Vecx| \transpose |\Vecx| = \|\Vecx\|_1^2 - \|\Vecx\|_2^2,
 \end{split}
\label{eqn:IQSc}
\end{equation}
which is equal to zero for any one-sparse $\Vecx$. Hence, this can be used to promote one-sparse solutions to optimization problems. See Fig.~\ref{fig:Smatrix}(a) for a graphical depiction.

\begin{figure}
\centerline{\includegraphics[width=\columnwidth]{Smatrix.pdf}}
\caption{\textbf{(a)} $\VecS$ matrix that promotes a one-sparse solution. \textbf{(b)} $\VecS$ matrix that promotes one-sparse groups in the solution. \textbf{(c)} $\VecS$ matrix that promotes a minimum separation distance between nonzero components in the solution. }
\label{fig:Smatrix}
\end{figure}

\subsection{Intra-group Sparsity}\label{sec:grpsparse}
Define $\Phi(\cdot) = |\cdot|$ and $\VecB = \VecI$. Consider a vector $\Vecx \in \mathbb{R}^{gn}$ where $g$ is a number of groups and $n$ is the number of components in each group.
Then, we can promote one-sparsity within each group using $\VecS \in \mathbb{R}^{gn \times gn}$ defined in blocks:
\begin{equation*}
\VecS = \begin{bmatrix} \widetilde{\VecS} & 0 & \cdots & 0 \\
                           0 & \widetilde{\VecS} & \cdots & 0 \\
                           \vdots & \vdots & \ddots & 0 \\
                           0 & 0 & 0 & \widetilde{\VecS}
          \end{bmatrix},
\end{equation*}
where $\widetilde{\VecS} = \mathbbm{1}\mathbbm{1}\transpose - \VecI_{n}$ (see Fig.~\ref{fig:Smatrix}(b)).
This is now a block-separable problem, equivalent to applying the penalty defined in Section~\ref{sec:onesparse} to different sections of $\Vecx$, i.e.,
$\sum_{k=1}^g |\Vecx_k|\transpose \widetilde{\VecS} |\Vecx_k|$,
where $k$ indexes blocks of $n$ components.
One use case for this formulation is in modeling occlusions in imaging problems, which we address with an example in Section~\ref{sec:erti}.

\subsection{Local Neighborhood Sparsity}\label{sec:LN}
Sparsity can be promoted in overlapping local neighborhoods in an ordered sequence of indexes
by restricting the nonzeros to a band around the diagonal.
This gives a symmetric Toeplitz $\VecS$ (see Fig.~\ref{fig:Smatrix}(c)).
For instance, an $\VecS$ with neighbor distance $n=1$ is given by

\begin{equation*}
\VecS = \begin{bmatrix} 0 & 1 & 0 & 0 & \hdots \\  1 &  0 & 1 & 0 & \ddots \\ 0 &  1 & 0 & 1 & \ddots \\ 0 & 0 & 1 & 0 & \ddots  \\ \vdots & \ddots & \ddots & \ddots & \ddots    \end{bmatrix}.
\end{equation*}

For a general neighbor distance $n$, $\VecS$ is given by
\begin{equation*}
\VecS_{i,j} = \begin{cases}
          \mu,  & |i - j| \leq n, \; i\neq j; \\
          0, & \text{otherwise},
       \end{cases}
\end{equation*}

where again $\mu \in [0,1]$ defines a strength of exclusivity. This imposes local-$n$-neighborhood one-sparsity, which ensures nonzeros in a solution occur with a minimum separation distance of $n$ indices.

\section{Choices for $\Phi(\cdot)$}
\label{sec:phichoice}
The typical choice for $\Phi(\cdot)$ is the absolute value $|\cdot|$.
This is the main focus of this paper and admits fast algorithms to result in one-sparse groups with a prescribed structure, with minimal bias.
However, we note that other choices can enjoy interesting properties.
For instance, using
$\Phi(\Vecx) = \text{max}(0,\Vecx)$
or
$\Phi(\Vecx) = \text{max}(0,-\Vecx)$
acts on positive or negative values only, respectively, and meets the condition outlined in Prop.~\ref{prop:constraints}.
Thus, combining two constraint terms,
\begin{equation}
 \begin{aligned}
\hat{\Vecx} =
& \argmin_{\Vecx}
& & f(\Vecx) \\
& \text{s.t.  }
& & \text{max}(0,\Vecx) \transpose \, \VecS \, \text{max}(0,\Vecx) = 0 \\
& & & \text{max}(0,-\Vecx) \transpose \, \VecS \, \text{max}(0,-\Vecx) = 0
\end{aligned}
\label{eqn:poscorr}
\end{equation}
can result in a solution where only \emph{positive} correlation is penalized, i.e., a group may contain one positive and negative component, rather than being one-sparse.
In~\cite{NNsparsity}, exclusive sparsity regularization is used to reduce redundancy in the learned kernels in convolution neural networks.
The $\Phi(\cdot) = \text{max}(0,\cdot)$ formulation could function as a relaxed approach to this, allowing more degrees of freedom in the filter kernels.

In a case where there can be a large disparity between the size of components within groups in the solution vector, one may wish to impose a nonlinear scaling and use $\Phi(\Vecx) = |\Vecx|^\kappa$ where $\kappa < 1$.
This reduces the effect of large but possibly incorrect components on other, potentially correct components. This can be seen in use in the two-dimensional local neighborhood total variation example in Section~\ref{sec:lntv}.

\section{Algorithms}

First, we note that when $\Phi(\cdot) = |\cdot|$ and $\VecB = \VecI$, the penalty can be expressed
\begin{equation}
 R(\Vecx) = |\Vecx| \transpose \VecS |\Vecx| = \|\Vecx\|_1^2 - \|\Vecx\|_2^2 - |\Vecx|\transpose(\mathbbm{1}\mathbbm{1}\transpose - \VecS - \VecI)|\Vecx|.
\label{eqn:IQ_2}
\end{equation}
An efficient algorithm to evaluate the proximal operator of the $\ell_1^2$ norm is available (see Appendix~\ref{sec:l12})~\cite{l12proof}. Hence, we can aim to efficiently solve any problem of the form:
\begin{equation}
 \begin{aligned}
\hat{\Vecx} =
& \argmin_{\Vecx}
& & f(\Vecx) \\
& \text{s.t.  }
& & |\Vecx| \transpose \VecS |\Vecx| = 0
\end{aligned}
\label{eqn:optprob}
\end{equation}
using a proximal subgradient method (Algorithm~\ref{alg:swag}).
This simply requires us to evaluate the (sub)gradient of
$f(\Vecx) - \|\Vecx\|_2^2 - |\Vecx|\transpose(\mathbbm{1}\mathbbm{1}\transpose - \VecS - \VecI)|\Vecx|$
and the proximal operator of $\|\Vecx\|_1^2$.
In practice, we find the convergence speed of this algorithm is not negatively affected by the use of a subgradient of
$-|\Vecx|\transpose(\mathbbm{1}\mathbbm{1}\transpose - \VecS - \VecI)|\Vecx|$
as this term will always aim to push the components of $\Vecx$ \emph{away} from the discontinuity in the gradient at $\Vecx = 0$.
Furthermore, in cases with no overlapping groups, this term equals zero.

As this penalty is nonconvex, it is prudent to start with an initial estimate of $\Vecx$ that minimizes the data fidelity.
Given this, Algorithm~\ref{alg:swag} outlines the proximal subgradient scheme used to approximately solve the problem in \eqref{eqn:optprob} by introducing a Lagrange multiplier $\lambda$.

 \begin{algorithm}
 \begin{algorithmic}[1]
 \renewcommand{\algorithmicrequire}{\textbf{Input:}}
 \renewcommand{\algorithmicensure}{\textbf{Output:}}
 \renewcommand{\algorithmicfor}{\textbf{while}}
 \REQUIRE Initial estimate $\Vecx^0 = \argmin_{\Vecx} f(\Vecx)$, $\lambda^0 = 0$, \\ $\overline{\VecS} = \mathbbm{1}\mathbbm{1}\transpose - \VecS $.
 \ENSURE  $\hat{\Vecx}$

  \FOR {not converged}
  \STATE $\Vecx^{k+1} =P_{\alpha \lambda^k}( \Vecx^{k} - \alpha(\nabla_x (f(\Vecx^k) - \lambda^k|\Vecx^k|\transpose \, \overline{\VecS} \, |\Vecx^k|))$
  \STATE $\lambda^{k+1} = \lambda^k + \alpha(|\Vecx^{k}| \transpose \VecS |\Vecx^{k}|)$
  \ENDFOR
 \RETURN $\hat{\Vecx} = \Vecx^{k+1}$
 \end{algorithmic}
  \caption{Proximal subgradient method for SWAGGER constrained problems}
  \label{alg:swag}
 \end{algorithm}

In Algorithm~\ref{alg:swag},
$P_{\alpha\lambda^k}$ is the proximal operator associated with the $\ell_1^2$ term, $\|\cdot\|_1^2$, and $\alpha$ is a step size that can be fixed or computed dynamically.
There exists an accelerated proximal gradient algorithm that is guaranteed to converge to a stationary point even for nonconvex problems~\cite{NCAPG}, which could be used here also.
The algorithm for this is outlined in Appendix~\ref{apdx:ncapg}.

When $\VecB$ is not the identity, we can instead solve a problem of the form:
\begin{equation}
 \begin{aligned}
\hat{\Vecx} =
& \argmin_{\Vecx}
& & f(\Vecx)  \\
& \text{s.t.}
& &  \VecB \Vecx = \Vecz \\
& & & |\Vecz| \transpose \VecS |\Vecz| = 0
\end{aligned}
\label{eqn:admm}
\end{equation}
using the alternating direction method of multipliers (ADMM) \cite{admm}, which also uses Algorithm~\ref{alg:swag} or an accelerated variation thereof at each iteration.

\section{Example applications}
\label{sec:examples}

\subsection{Comparison with Other Methods}
\label{sec:compare}

Three experiments were performed, where measurements $\Vecy$ were generated using $\Vecy = \VecA \Vecx$, with white Gaussian noise added to achieved a signal-to-noise radio (SNR) of 25 dB\@.
Matrix $\VecA \in \mathbb{R}^{25\times60}$ has random Gaussian entries realized for each trial.
The vector $\Vecx$ has entries $\pm U(0.5,1.5)$ and is made to fit a specific sparsity structure such that $|\Vecx| \transpose \VecS |\Vecx| \approx 0$ for some $\VecS$.
Details of how this is achieved are presented in Appendix~\ref{sec:genx}.
In the first experiment, $\VecS$ is fixed and enforces intra-group one-sparsity in ten groups (see Section~\ref{sec:grpsparse}), where
$\widetilde{\VecS} \in \mathbb{R}^{6 \times 6}$.
In the second experiment, a local neighborhood $\VecS$ (see Section~\ref{sec:LN}) is used with $n=4$.
In the third experiment, a new binary $\VecS$ is generated per trial with entries equal to zero or one with $50\%$ probability.
We compare the performance of the SWAGGER penalty with other typical sparsity regularizers, both structured and unstructured.
The problems solved are of the form
$\hat{\Vecx} = \argmin_{\Vecx} \frac{1}{2}\|\VecA\Vecx -y\|_2^2 + \lambda R(\Vecx)$,
where $R(\Vecx)$ is:
\begin{enumerate}
    \item  LASSO: $\|\Vecx\|_1$
    \item  p-shrinkage~\cite{pshrinkage}, with $p=0.5$
    \item  E-LASSO/$\ell_{1,2}$: $\sum_i\|\Vecx_{gi}\|_1^2$
\end{enumerate}
The E-LASSO penalty uses a sum of the $\ell_1$-squared term over groups.
We create one group per row in $\VecS$, where each group contains the nonzero components in each row (and the diagonal), i.e.,
$g_i = \{\, j \mid \, \VecS_{i,j} + \delta_{i-j} = 1 \,\}$.
This penalty is not designed for overlapping groups, so the results are poor in the local neighborhood and random $\VecS$ experiments.
The pseudo-inverse is used in the initialization for the nonconvex penalties, $\Vecx^0 = (\VecA\transpose\VecA)^{-1}\VecA\transpose \Vecy$.

\newcommand{\indentA}{\hspace*{2mm}}
\newcommand{\indentB}{\hspace*{6mm}}

\begin{table}
\caption{Simulated results over 1000 trials for three different sparsity structures.
Metrics are the percentage of nonzero components identified, the Jacard index (0 - 1), and the mean-squared error (MSE) where the ground truth is nonzero.
}
\label{table:testresults}
\begin{center}
\renewcommand{\arraystretch}{1.1}
\begin{tabular}{@{}lrrr@{}}
\hline
\textbf{Experiment}                                                       & \textbf{\begin{tabular}[c]{@{}r@{}}Support correct \\ (\%)\end{tabular}} & \textbf{Jacard Index}       & \textbf{\begin{tabular}[c]{@{}l@{}}MSE in \\ support\end{tabular}} \\ \hline
\textbf{Group S}                                                          & \textbf{}                                                                &                             &                                                                    \\
                                                                           \multicolumn{3}{l}{\indentA \textbf{$\lambda$ tuned for sparsity level}}                                                 &                                                                    \\
\indentB SWAGGER                                                                   & \textbf{75.69}                                                           & \textbf{0.646}              & \textbf{1.987}                                                     \\
\indentB E-LASSO                                                                   & 59.84                                                                    & 0.398                       & 4.634                                                              \\
\indentB $p$-shrinkage                                                             & 68.89                                                                    & 0.559                       & 2.564                                                              \\
\indentB LASSO                                                                     & 56.71                                                                    & 0.404                       & 3.813                                                              \\
                                                                          \multicolumn{3}{l}{\indentA \textbf{$\lambda$ tuned for Jacard index}}                                                 &                                                                    \\
\indentB SWAGGER                                                                   & 84.10                                                                    & \textbf{0.699}              & \textbf{1.633}                                                     \\
\indentB E-LASSO                                                                   & \textbf{87.38}                                                           & 0.509                       & 2.849                                                              \\
\indentB $p$-shrinkage                                                             & 77.82                                                                    & 0.638                       & 2.122                                                              \\
\indentB LASSO                                                                     & 73.91                                                                    & 0.492                       & 3.221                                                              \\ \hline
\multicolumn{2}{l}{\textbf{Local neighborhood S}}

& \textbf{}                   &                                                                    \\
                                                                          \multicolumn{3}{l}{\indentA \textbf{$\lambda$ tuned for sparsity level}}                                                &                                                                    \\
\indentB SWAGGER                                                                   & \textbf{79.89}                                                           & \textbf{0.701}              & \textbf{1.653}                                                     \\
\indentB E-LASSO                                                                   & 60.37                                                                    & 0.241                       & 5.432                                                              \\
\indentB $p$-shrinkage                                                             & 68.02                                                                    & 0.545                       & 2.671                                                              \\
\indentB LASSO                                                                     & 56.46                                                                    & 0.402                       & 3.813                                                              \\
                                                                          \multicolumn{3}{l}{\indentA \textbf{$\lambda$ tuned for Jacard index}}                                                 &                                                                    \\
\indentB SWAGGER                                                                   & \textbf{85.18}                                                           & \textbf{0.754}              & \textbf{1.328}                                                     \\
\indentB E-LASSO                                                                   & 82.18                                                                    & 0.306                       & 5.278                                                              \\
\indentB $p$-shrinkage                                                             & 76.92                                                                    & 0.625                       & 2.187                                                              \\
\indentB LASSO                                                                     & 72.10                                                                    & 0.479                       & 3.318                                                              \\ \hline
\textbf{Random S}                                                         & \textbf{}                                                                & \textbf{}                   &                                                                    \\
                                                                          \multicolumn{3}{l}{\indentA \textbf{$\lambda$ tuned for sparsity level}}                                                 &                                                                    \\
\indentB SWAGGER                                                                   & \textbf{95.32}                                                           & \textbf{0.927}              & \textbf{0.171}                                                     \\
\indentB E-LASSO                                                                   & 56.20                                                                    & 0.147                       & 3.151                                                              \\
\indentB $p$-shrinkage                                                             & 89.68                                                                    & 0.845                       & 0.461                                                              \\
\indentB LASSO                                                                     & 70.90                                                                    & 0.563                       & 1.708                                                              \\
                                                                          \multicolumn{3}{l}{\indentA \textbf{$\lambda$ tuned for Jacard index}}                                                 &                                                                    \\
\indentB SWAGGER                                                                   & \textbf{95.84}                                                           & \textbf{0.932}              & \textbf{0.151}                                                     \\
\indentB E-LASSO                                                                   & 88.64                                                                    & 0.206                       & 3.173                                                              \\
\indentB $p$-shrinkage                                                             & 93.15                                                                    & 0.888                       & 0.327                                                              \\
\indentB LASSO                                                                     & 88.26                                                                    & 0.661                       & 1.173                                                             \\ \hline
\end{tabular}
\end{center}
\end{table}

Table~\ref{table:testresults} shows the results from the three experiments.
The metrics evaluated are the percentage of components correctly identified as nonzero, the Jacard index (the intersection of the true support and estimated support divided by the union), and the mean-squared error (MSE) for the components that are nonzero in the ground truth.
We see that SWAGGER outperforms the other algorithms in almost every case.
It is unsurprising that the unstructured sparsity regularizers (LASSO and p-shrinkage) perform especially poorly in the group $\VecS$ and local neighborhood settings as the true support is not especially sparse overall,
whereas SWAGGER is agnostic to the overall sparsity level.
Furthermore, the E-LASSO ($\ell_1^2$) regularizer performs poorly when groups are overlapping, whereas SWAGGER handles this gracefully and without any additional effort required.
We also see that the MSE within the correct support is particularly low with SWAGGER, as it implicitly de-biases the solutions (this can be readily seen from the $-\|\Vecx\|_2^2$ term in (\ref{eqn:IQSc})).
Of particular interest are the results where $\lambda$ is tuned to result in the correct sparsity level.
The SWAGGER results are particularly favorable in this setting, and this is the most typical use case; it is roughly equivalent to solving the constrained SWAGGER problem in (\ref{eqn:optprob}) and hence requires no user tuning of the regularization strength.

\subsection{Local Neighborhood Total Variation}
\label{sec:lntv}
The well established total variation (TV) penalty, $\|\VecD \Vecx\|_1$ where multiplying by $\VecD$ takes finite differences, aims to sparsify the changes along the solution vector $\Vecx$.
We propose here a local neighborhood total variation (LN-TV) penalty using SWAGGER\@.
LN-TV is achieved by assigning $\VecB = \VecD$ and using an $\VecS$ that promotes sparsity in local neighborhoods as defined in Section~\ref{sec:LN}.
LN-TV simply ensures that changes in the vector occur at least some minimum distance apart, while allowing changes of any amplitude.
This is a prior which suggests the vector is piecewise-constant with a certain minimum segment length.
If a typical minimum separation distance between significant changes in a vector is known, LN-TV can outperform TV and Moreau-enhanced TV (a convex-nonconvex variation)~\cite{MTV} in a denoising setting, as seen in Fig.~\ref{fig:LNTVcompare}.

\begin{figure}
\centerline{\includegraphics[width=\columnwidth]{LNTV-compare.pdf}}
\caption{The proposed local neighborhood total variation (LN-TV) denoising, which only allows changes in the derivative to occur with some minimum separation, compared to standard total variation (TV) and Moreau-enhanced total variation (M-TV)  compared to  denoising.}
\label{fig:LNTVcompare}
\end{figure}

For more general problems, where a piecewise approximation is helpful but the segments do not necessarily have a minimum length well known \emph{a priori}, the LN-TV penalty can be combined with the traditional TV by solving a problem of the form:
\begin{equation}
\hat{\Vecx} = \argmin_{\Vecx} \frac{1}{2}\|\VecA\Vecx - \Vecy\|_2^2 + \underbrace{\lambda_1|\VecD \Vecx| \transpose \VecS |\VecD \Vecx|}_{\rm LN-TV} + \underbrace{ \lambda_2 \|\VecD \Vecx\|_1}_{\rm TV}
\label{eqn:tvcombined}
\end{equation}
where the $\lambda$'s are parameters that control the strength of the regularization. If $\VecA = \VecI$, this acts to denoise the input $\Vecy$, but different choices of $\VecA$ can be used to solve deconvolution or deblurring problems, super-resolution, and so on.
The addition of the LN-TV term can help avoid the `staircasing' artefacts that often arise when using TV, and allow for weaker TV regularization, which reduces the bias in the result.
We present an example of these favorable effects in Fig.~\ref{fig:LNTVcombined}.
Here, the $\VecS$ matrix used promotes sparsity in $\VecD \Vecx$ within five indices either side of a nonzero component. This formulation is distinct from the one discussed in (\ref{eqn:optprob}), as instead of a constraint we are using the SWAGGER term as a regularization with a strength prescribed by $\lambda_1$. This allows us to have some more nuance by having a linear ramp from 1 to 0.5 in the band around the diagonal, to make close changes less likely than ones a greater distance away.

\begin{figure}
\centerline{\includegraphics[width=\columnwidth]{LNTV-combined.pdf}}
\caption{Combining local neighborhood total variation with standard total variation can help to reduce bias and avoid `staircasing' artefacts.}
\label{fig:LNTVcombined}
\end{figure}

We can extend this formulation to a 2D setting also. Using the penalty formulation in (\ref{eqn:tv2d}), we promote horizontal and vertical differences that occur only with some minimal separation distance:
\begin{equation}
R(\Vecx) = \lambda(\underbrace{|\VecD_h \Vecx| \transpose \VecS_h |\VecD_h \Vecx|}_{\rm horizontal} + \underbrace{|\VecD_v \Vecx| \transpose \VecS_v |\VecD_v \Vecx|}_{\rm vertical} ),
\label{eqn:tv2d}
\end{equation}
where $\VecD_v$ and $\VecD_h$ are matrices that take finite differences along the vertical columns and horizontal rows, respectively, and $\VecS_v$ and $\VecS_h$ impose local neighborhood sparsity in the vertical and horizontal directions.
We choose $\Phi(\Vecx) = |\Vecx|^\kappa$ which introduces another parameter $\kappa$ as discussed in Section~\ref{sec:phichoice}.

We find that, in general, $\kappa$ should be kept somewhat smaller than 1 if the initial estimate is especially blurred or noisy, and larger than 1 if there exist hard edges in the initial estimate that should be maintained.
For the results shown in Fig.~\ref{fig:LNTV2D}, $\kappa = 0.75$.

\begin{figure}
\centerline{\includegraphics[width=0.9\columnwidth]{LNTV-2D.pdf}}
\caption{\textbf{(a)} A test image blurred with a Gaussian kernel and corrupted with Gaussian noise. \textbf{(b)} Reconstruction using total variation. \textbf{(c)} Reconstruction using local neighborhood TV only. \textbf{(d)} Reconstruction using a combination of both.}
\label{fig:LNTV2D}
\end{figure}

\subsection{Modeling Mutual Surface Occlusions in Non-Line-of-Sight (NLOS) Imaging}
\label{sec:erti}
The aim of NLOS imaging is to form reconstructions of scenes hidden from the direct line of sight of the observer. Typical methods to achieve this rely on the use of ultra-fast pulsed lasers and time-resolved single photon counting to infer the hidden geometry by measuring round-trip distances
\cite{Kirmani2009, Velten2012, Heide2014, OToole2018}.
Often, to recover a 3D scene, the hidden area will be discretized into patches or surfaces in some manner.
Some of these patches may occlude others: if a surface is actually present in the scene, light coming from others behind it may have no paths to the measurement device.
As the discretization is prescribed beforehand, the surfaces occluded by each other are known \emph{a priori}, and they should be mutually exclusive.
Therefore, we can use SWAGGER to ensure that groups of surfaces that occlude one another will be one-sparse in the recovered output.
This provides two benefits. Firstly, the recovered output will be physically plausible as surfaces that cannot contribute any light in the measurements will not be present in the solution.
Secondly, ensuring this physical constraint is met \emph{during} the optimization process should lead to better estimations overall.

This idea extends to any situation in which an ideal discretization of some physical area, field, etc., involves some mutual exclusivity between elements of the discretization.
Typically, to deal with this one may instead use a discretization that is less desirable but avoids or reduces this exclusivity requirement, use post-processing to make the recovery fit the expected structure, or simply ignore it.
Using SWAGGER can instead ensure that reconstructions both fit the expected structure prescribed by the underlying physics of the problem, and also enjoy improved estimates due to the knowledge of the structure being used within the optimization procedure.

One NLOS imaging system, Edge-Resolved Transient Imaging~\cite{ERTI}, uses a laser to illuminate the floor at numerous positions in an arc around a vertical edge, such as a doorway, to form a 3D reconstruction of the room beyond.
For each measurement position, a histogram of the arrival times of photons reaching a single photon avalanche diode (SPAD) detector is accumulated using time-correlated single photon counting.
Each subsequent laser position illuminates more of the hidden scene, and by taking differences between measurement histograms one can recover a noisy measurement containing photon arrivals originating mostly from within a single wedge in the hidden area.

\begin{figure}
\centerline{\includegraphics[width=\columnwidth]{erti.pdf}}
\caption{\textbf{(a)} Experimental measurement data containing predominantly photon returns from a single wedge in a hidden area. The data corresponds to the 18th wedge in the `Staircase' scene, Figure~4 in~\cite{ERTI}.
\textbf{(b)} The ground truth scene and the reconstruction using SWAGGER\@. The displayed reflectivity estimate is enhanced by scaling based on the amount of the surface that is occluded.
\textbf{(c)} The sparsity matrix used to model occlusion and mutual exclusivity of surfaces occupying the same space. \textbf{(d)} Reconstructions without using SWAGGER, with increasing regularization strength.
No choice of $\lambda$ gives accuracy comparable to the reconstruction using SWAGGER in (b).}
\label{fig:erti}
\end{figure}

From this difference histogram measurement, one can attempt to fit surfaces to the scene within a wedge, to reconstruct the hidden area. It is assumed that surfaces always start at the ground, extend to a certain height, and are a certain distance from the corner. We can form a reconstruction by solving the following problem:
\begin{equation}
 \begin{aligned}
\hat{\Vecx} =
& \argmin_{\Vecx \geq 0}
& & \frac{1}{2}\|\VecA\Vecx - \Vecy\|_2^2  +  \lambda_1 \| \Vecx\|_1 \\
& \text{s.t.  }
& & |\Vecx| \transpose \VecS |\Vecx| = 0
\end{aligned}
\label{eqn:}
\end{equation}
where $\Vecy$ is a difference histogram measurement and $\VecA$ is a matrix governing the light transport to and from surfaces at different distances from the edge, and with different heights.
Fig.~\ref{fig:erti} shows reconstructions of a wedge using experimental data from~\cite{ERTI}.
One reconstruction uses only the $\|\Vecx\|_1$ term and no constraints, and a second that includes the SWAGGER constraint.
In~\cite{ERTI}, a Markov chain Monte Carlo (MCMC) method was used to form the reconstructions as it could implicitly include occlusions model and needed to only estimate parameters for a small number of surfaces, rather than use a full scene discretization.
Here, we use SWAGGER and a full scene discretization to ensure that surfaces which should occlude those behind them, and vice versa, are accurately modeled.
Secondly, it permits us to use a discretization with mutually exclusive elements---surfaces in the same position but with different heights---where only one should be present in the solution.
As such, the result is a physically plausible reconstruction, which is quite accurate in support, height, and reflectivity.

\section{Conclusion}

Using SWAGGER as a constraint allows one to recover solutions to problems that fit a known sparsity structure, including any number of one-sparse overlapping groups within the solution vector or a transform thereof. This is useful in modeling a wide variety of phenomena, such as occlusions in imaging problems.
We illustrate the usefulness of the proposed penalty for some example use cases where, by simply constructing a sparsity structure matrix $\VecS$, one can ensure estimates fit known hard structured sparsity constraints derived from domain knowledge of the problem.
This results in solutions that are both physically plausible and also improved overall.
Similarly, SWAGGER can be used as a regularization term with some strength, to promote solutions that fit a sparsity structure whilst allowing more nuance, which gives rise to local-neighborhood total variation. SWAGGER can be readily combined with other priors, regularization terms and constraints to improve estimations. A proximal (sub)gradient algorithm (and accelerated algorithm) have been proposed to quickly solve SWAGGER-constrained and SWAGGER-regularized problems.

\appendix

\subsection{Proof of Proposition~\ref{prop:constraints}}
\label{sec:penbounds}

Suppose both conditions on Proposition~\ref{prop:constraints} hold.
By condition~2), every entry of $\Phi(\VecB\Vecx)$ is nonnegative.
By condition~1), every entry of $\VecS$ is also nonnegative.
Therefore, each entry in the matrix triple product
$\Phi(\VecB \Vecx) \transpose \, \VecS \, \Phi(\VecB \Vecx)$
is nonnegative,
ensuring that the result is nonnegative.

\subsection{Proximity Operator Algorithm for $\ell_1^2$}
\label{sec:l12}
Algorithm~\ref{alg:prox} reproduces the method from~\cite{l12proof}
to compute
the proximal operator for the $\ell_1^2$ norm (with $O(N \log N)$ complexity).
\begin{algorithm}[H]
 \caption{Proximity operator of $\ell_1^2$}
  \label{alg:prox}
 \begin{algorithmic}[1]
 \renewcommand{\algorithmicrequire}{\textbf{Input:}}
 \renewcommand{\algorithmicensure}{\textbf{Output:}}
 \renewcommand{\algorithmicfor}{\textbf{while}}
 \REQUIRE $\Vecz \in \mathbb{R}^N$, $\lambda \geq 0$
 \ENSURE  $\hat{\Vecz} = \argmin_\Vecq \|\Vecz - \Vecq\|_2^2 + \frac{1}{2} \lambda \|\Vecq\|_1^2$

 \STATE sort entries of $|\Vecz|$ into $\Vecy$ s.t. ($\Vecy_1 \geq \cdots \geq \Vecy_N)$
 \STATE set $\rho = \max \{ j \in \{1...N\} \, | \, \Vecy_j - \frac{\lambda}{1+j\lambda} \sum_{r=1}^j \Vecy_r > 0 \}$

 \RETURN $\hat{\Vecz} = \max \left(|\Vecz| - \tau, 0 \right)\text{sign}(\Vecz)$ \\ where $\tau = \frac{\lambda}{1+j\lambda} \sum_{r=1}^\rho \Vecy_r$
 \end{algorithmic}
 \end{algorithm}

\subsection{Accelerated SWAGGER Algorithm}
\label{apdx:ncapg}

In~\cite{NCAPG}, a monotonic accelerated proximal gradient method is outlined that is guaranteed to converge to a stationary point for nonconvex problems.
Algorithm~\ref{alg:swagaccel} applies this acceleration to Algorithm~\ref{alg:swag},
where $\alpha_x$, $\alpha_y$ and $\alpha_\lambda$ are step sizes that can be fixed or computed dynamically with a back-tracking scheme. The convergence proof requires that $f(\Vecx)$ is a proper function with Lipschitz continuous gradients (e.g., the least squares loss), and the SWAGGER penalty is proper and lower semicontinuous, which is the case for $\Phi(\Vecx) = |\Vecx|$.

 \begin{algorithm}[H]
 \caption{Accelerated proximal subgradient method for SWAGGER}
  \label{alg:swagaccel}
 \begin{algorithmic}[1]
 \renewcommand{\algorithmicrequire}{\textbf{Input:}}
 \renewcommand{\algorithmicensure}{\textbf{Output:}}
 \renewcommand{\algorithmicfor}{\textbf{while}}
 \REQUIRE $\Vecz_1 = \Vecx_1 = \Vecx_0$, $t_1 = 1$, $t_0 = 0$, $\overline{\VecS} = \mathbbm{1}\mathbbm{1}\transpose - \VecS $.
 \ENSURE  $\hat{\Vecx}$

  \FOR {not converged}
  \STATE $\Vecy^k = \Vecx^k + \frac{t^{k-1}}{t^k}(\Vecz^k - \Vecx^k) + \frac{t^{k-1}-1}{t^k}(\Vecx^k - \Vecx^{k-1})$
  \STATE $\Vecz^{k+1} = P_{\alpha_y \lambda^k}( \Vecy^{k} - \alpha_y(\nabla_y ( f(\Vecy^k) - \lambda^k|\Vecy^k|\transpose \, \overline{\VecS} \, |\Vecy^k|))$
  \STATE $\Vecv^{k+1} = P_{\alpha_x \lambda^k}( \Vecx^{k} - \alpha_x(\nabla_x (f(\Vecx^k) - \lambda^k|\Vecx^k|\transpose \, \overline{\VecS} \, |\Vecx^k|))$

\STATE  $\Vecx^{k+1} = \begin{cases}
          \Vecz^{k+1}, & F(\Vecz^{k+1}) \leq F(\Vecv^{k+1}); \\
          \Vecv^{k+1}, & \text{otherwise}
       \end{cases}$

  \STATE $t^{k+1} = \frac{1}{2}(\sqrt{4(t^k)^2 + 1} + 1)$

  \STATE $\lambda^{k+1} = \lambda^k + \alpha_\lambda(|\Vecx^{k}| \transpose \VecS |\Vecx^{k}|)$
  \ENDFOR
 \RETURN $\hat{\Vecx} = \Vecx^{k+1} $
 \end{algorithmic}
 \end{algorithm}

\subsection{Generating Test Vectors}
\label{sec:genx}
For the experiments in Section~\ref{sec:compare}, we must generate a test vector $\Vecx$ for each trial which fits the sparsity structure described by a specific $\VecS$ matrix.
To do so we use Algorithm~\ref{alg:genx},
where in Step 4,
$\Vecu_j$ is drawn from the continuous uniform distribution on $[0.5,1.5]$.

 \begin{algorithm}[H]
 \caption{Generate a vector $\Vecx_S$ s.t. $|\Vecx^i|\transpose \VecS |\Vecx^i| \approx 0$}
  \label{alg:genx}
 \begin{algorithmic}[1]
 \renewcommand{\algorithmicrequire}{\textbf{Input:}}
 \renewcommand{\algorithmicensure}{\textbf{Output:}}
 \renewcommand{\algorithmicfor}{\textbf{while}}
 \REQUIRE $\Vecx^0 \sim N(0, 1)$, $\VecS$, $\mu \ll 1$
 \ENSURE  $\Vecx_S$

  \FOR { $|\Vecx^i|\transpose \VecS |\Vecx^i| \geq \mu$}
  \STATE $\Vecx^{i+1} = \argmin_\Vecx \|\Vecx^{i} - \Vecx\| + |\Vecx|\transpose \VecS |\Vecx|$

  \ENDFOR
 \RETURN $\Vecx_{S,j} = \begin{cases}
          0, & \Vecx^{i+1}_j = 0 ; \\
          \text{sign}(\Vecx^{i+1}_j) \Vecu_j, & \Vecx^{i+1}_j \neq 0
       \end{cases}$
 \end{algorithmic}
 \end{algorithm}

 \subsection{The Choice of $c$ for Convex Nonconvexity}
 \label{sec:cnc}

The Hessian of the cost function
\begin{equation*}
  \hat{\Vecx} = \argmin_{\Vecx} \frac{1}{2}\|\VecA\Vecx - \Vecy\|_2^2 + \lambda|\Vecx| \transpose \VecS |\Vecx|
\end{equation*}
is given by $\VecA \transpose \VecA + 2\lambda \VecX\VecS\VecX$
(where $\VecX = \text{diag}(\text{sgn}(\Vecx))$). We introduce a term $c \VecI$ to the $\VecS$ matrix:
\begin{eqnarray*}
  \VecA \transpose \VecA + 2\lambda \VecX(\VecS - c \VecI)\VecX
  & = & \VecA \transpose \VecA + 2\lambda \VecX\VecS \VecX - 2\lambda c \VecX\VecI\VecX \\
  & = & \VecA \transpose \VecA + 2\lambda \VecX\VecS \VecX  - 2\lambda c \VecI.
\end{eqnarray*}
To maintain convexity, we wish to have
\begin{equation*}
   \lambda_{\text{min}}(\VecA \transpose \VecA + 2\lambda \VecX\VecS \VecX) - 2\lambda c \geq 0,
\end{equation*}
or equivalently
\begin{equation*}
   2\lambda c \leq \lambda_{\text{min}}(\VecA \transpose \VecA + 2\lambda \VecX\VecS \VecX).
\end{equation*}

Since $\VecA \transpose \VecA$ and $2\lambda \VecX\VecS \VecX$ are both
Hermitian,
\begin{equation*}
\lambda_{\text{min}}(\VecA \transpose \VecA + 2\lambda \VecX\VecS \VecX)  \geq \lambda_{\text{min}}(\VecA \transpose \VecA) + \lambda_{\text{min}}(2\lambda \VecX\VecS \VecX)
\end{equation*}
by Weyl's inequality~\cite{weyl}.
Finally, we note
\begin{equation*}
   \min_\VecX \lambda_{\text{min}}(2\lambda \VecX\VecS \VecX)) = 2\lambda \, \lambda_\text{min}(\VecS),
\end{equation*}
providing us with a bound for the choice of $c$:
\begin{equation*}
c \leq \frac{1}{2\lambda}\lambda_{\text{min}}(\VecA \transpose \VecA) + \lambda_{\text{min}}(\VecS ).
\end{equation*}

\section*{Acknowledgment}

We thank Y. Ma for comments on the manuscript, and S. W. Seidel, J. Rapp, J. Murray-Bruce and I. Selesnick for discussions.

\bibliography{lit}
\bibliographystyle{IEEEtran}

\end{document}


TITLE: What are the boundary conditions for the electron in a hydrogen atom?
QUESTION [3 upvotes]: From what I understand, the wave equation for an electron can be constructed using the "particle in a box" model in three dimensions. However, what would be the boundary conditions in this case? In other words, what are the potential energy barriers?

REPLY [3 votes]: Obviously the potential varies smoothly so there are no "barriers" so to speak. (as far as I'm aware there are no discontinuous potentials in reality)
Examples of boundary conditions in the case of the hydrogen atom would be that the radial wavefunction should go to zero at the origin and at infinity, and that the angular wavefunction should be periodic with period $2 \pi$.


TITLE: Heating with tea candles using pot vs. not using a pot
QUESTION [0 upvotes]: With all the concern about loosing regular heating this winter I have been looking at alternative emergency ways to heat up a room. One common suggestion is to use tea lights. So you put six (or so) tea lights on a plate or something. You are then recommended to put a flower pot up-side-down over the tea lights.
In this video (he uses a cooking pot instead of a flower pot) the person explains that putting the pot over the candles will better heat up the room because it heats up the pot that then radiates the heat instead of heating using convection from the candles alone.
This doesn't make sense to me. My thinking would be that the candles put out the same amount of heat no matter what.
Can someone explain this?

REPLY [3 votes]: My thinking would be that the candles put out the same amount of heat
no matter what.

Unless the placement of the pot somehow increases the rate of combustion of the candles, then you are right that the rate of heat transfer to the room should be the same.
But there is also the question what type of heating provides more comfort, radiant or convection heating. According to following link, radiant heating provides more comfort; https://energy-com.co.uk/service/radiant-heats-vs-convection-heat/. So if the percentage of the total heat transfer by radiation is greater
with the pot in place then without it, the pot would theoretically provide more comfort for the same total amount of heat.
Hope this helps.

REPLY [0 votes]: Because essentially it's about the heat dispassion, the candle flame induced an upward air which resulted a large dispassion through the air, and the air molecular got cooled down much easily. It basically reduced to a linear relation to the exchange rate of the air which might say rather fast.
The pot solution was the black body radiation so the thermal residue could be maintained much longer as it falls off exponentially, and the fact that it's achieve the "warm" by provide the radiative thermal background and not necessarily heat up the air direly.(You might have seen some comment about the energy efficient heaters, etc. That's basically what they were talking about.)
Anyway none of those worked because it had to do with the infrastructure as in the thermal insulation, almost none of the Eurasia or America's houses could retain a heat background with a few tea candle. In an apartment complex, the thermal transfer through the walls were actually more meaningful.


TITLE: How can I plot a 2D figure in MATLAB by "connecting the dots"?
QUESTION [0 upvotes]: I'm an amateur at MATLAB and I know how to do the basic stuff such as plotting functions, writing M files, functions, for loops, etc but I've be tasked to do something I have never done before.
I have to draw this figure which resembles a Tree or Home (2D childs drawing), and I know all of its points: (6,1), (8,1), (6, 3) (8,3) makes the base of the house (and the diagonals are drawn too) and then the points (6,3), (7,4), (8,3) make the roof.
How do I connect the points in a way that it resembles what I'm looking at?
Thanks.

REPLY [1 votes]: points = [
   6 1
   8 1
   6 3
   8 3
   7 4];

sequence = [1 2 4 3 1 4 2 3 5 4];
plot(points(sequence, 1), points(sequence, 2), '-o')
set(gca, 'XLim', [5, 9], 'YLim', [0, 5],'DataAspectRatio', [1 1 1])
figure(gcf)

Perhaps more idiomatically:
points = [
   6 1
   8 1
   6 3
   8 3
   7 4];

sequence = [1 2 4 3 1 4 2 3 5 4];
u = points(sequence, :);
plot(u(:, 1), u(:, 2), '-o')
set(gca, 'XLim', [5, 9], 'YLim', [0, 5],'DataAspectRatio', [1 1 1])
figure(gcf)


TITLE: Why $\mathbf n\cdot(\mathbf L^T\mathbf n)=\mathbf n\cdot(\mathbf D\mathbf n)$?
QUESTION [5 upvotes]: The deformation gradient $\mathbf F$ describes how material line elements change their length and orientation during deformation; the velocity gradient $\mathbf L$ describes the rate of these changes.
We can write $\mathbf L=\mathbf D+\mathbf W$, where $\mathbf D=(\mathbf L+\mathbf L^T)/2$ (thus symmetric) and $\mathbf W=(\mathbf L-\mathbf L^T)/2$ (thus skewsymmetric).
In words, $\mathbf D$ is the Eulerian strain-rate tensor and $\mathbf W$ is the body spin.
Now suppose $\mathbf n$ is a unit vector field.
We have $\mathbf n\cdot(\mathbf L^T\mathbf n)=\mathbf n\cdot(\mathbf D^T\mathbf n)+\mathbf n\cdot(\mathbf W^T\mathbf n)=\mathbf n\cdot[(\mathbf D^T+\mathbf W^T)\mathbf n]=\mathbf n\cdot(\mathbf D\mathbf n)$.
But I do not understand why the last equation is true.
I would appreciate any help or hint. Thank you.

REPLY [4 votes]: It's because $\mathbf W$ is skew symmetric:
$\mathbf n·\mathbf W^T\mathbf n=-\mathbf n·\mathbf W^T\mathbf n=0$
But $\mathbf D$ is symmetric, so is $\mathbf D=\mathbf D^T$, and it follows.
Added
$$\mathbf m·\mathbf W^T\mathbf n=\mathbf n·\mathbf W\mathbf m$$
And because skew symmetric
$$\mathbf n·\mathbf W\mathbf m=-\mathbf n·\mathbf W^T\mathbf m$$
With $\mathbf n=\mathbf m$, $2\mathbf n·\mathbf W^T\mathbf n=0$


TITLE: How is the angular momentum conserved in this case?
QUESTION [0 upvotes]: So imagine we have a mass attached to a string and spin it. If angular momentum is conserved then why does the object not have a tendency to move in a curved path if the mass is suddenly let go off. Linear momentum appears to be conserved in this case at an instantaneous point where the mass $M$ would have velocity $v$ at any given point and hence a linear momentum of $Mv$ which presumably dies out due to gravity and drag. Where is the angular momentum gone?

REPLY [0 votes]: The angular momentum goes nowhere (assuming no external torques are applied while leaving the string). The angular momentum of a point mass (I am assuming the ball to be a point mass, but angular momentum is conserved even when you assume the ball to be a rigid body) can be expressed as
$$\mathbf L=m(\mathbf r\times \mathbf v)$$
Thus, while the ball was going in the circle of radius, its angular momentum was
$$L_{\rm initial}=mvR$$
where $R$ is the radius of the circular path. Just after you leave the string, the body continues going with the same velocity as before. It is easy to see that the value of the cross product ($\mathbf r\times\mathbf v$) does not change, thus the angular momentum stays the same as before, i.e.
$$L_{\rm final}=mvR$$


TITLE: Asymptotics of Generating Functions
QUESTION [1 upvotes]: Given a generating function $A(x)$, are there any general techniques for finding the asymptotics of the associated sequence? For example, given the generating function satisfying $A(x) = 1 + x\cdot A\left(\frac{x}{A(-x)}\right)$, is there anything we can say about how fast the coefficients grow?

REPLY [3 votes]: I don't really understand the significance of your example, but the univariate version of the question is covered very thoroughly in Flajolet-Sedgewick's Analytic Combinatorics, while the (much harder) multivariate version is covered in "Analytic Combinatorics in Several Variable", by Robin Pemantle and Mark Wilson.


TITLE: Graph that maximizes minimum hitting time?
QUESTION [6 upvotes]: Let $G$ be some connected bidirectional (or undirected) graph. We define a random walk as a walk that begins at a vertex chosen uniformly at random, and at each step proceeds to one of its current vertex's neighbors uniformly at random. The expected hitting time for a vertex $v$ is the time it takes, on average, for the walk to reach $v$.
For what family of graphs is the minimum of all expected hitting times as large as it can be?

REPLY [9 votes]: It is well known that a barbell graph (two cliques of size $n/3$ connected by a path of length $n/3$) has average hitting time $\Omega(n^3)$, but I believe the same applies to minimum hitting time (for uniform or stationary distribution). Whatever vertex you choose as the one that you think is easiest to hit, you have constant probability of starting in the far clique from that vertex, after which it will take $\Omega(n^3)$ time in expectation before you traverse the connecting path to your chosen vertex.


TITLE: Existence of solutions for inhomogeneous Helmholtz Equation
QUESTION [1 upvotes]: Lets say I have a bounded domain $\Omega$ in 2D. If I consider the inhomogeneous Helmholtz equation with Dirichlet Boundary conditions along the Boundary $\delta\Omega$:
$u_{xx}(x,y) + u_{yy}(x,y) + \eta^2(x,y) u(x,y) = g(x,y)$ on $\Omega$
$u = f$, on $\delta\Omega$
What can I say about the existence of solutions in function of $\eta(x,y)$? Note that my $\eta$ is not necessarily constant, but at least always positive.
Regularity requirements are no issue for me. If everything needs to be smooth, that's fine. If the above problem does not have a solution, which restrictions do I need to consider to get a solution?
I'm also thankful for references to Textbooks/Papers that state the existence of solutions.

REPLY [0 votes]: Have a look at Melenk's PhD Thesis: On Generalized Finite Element Methods
You can download it here:
http://www.asc.tuwien.ac.at/~melenk/publications/publications.html
In section 8.1 he discusses existence and uniqueness for the Helmholtz equation. Maybe recall Fredholm's Theorems before hand.


TITLE: Lagrangian subspace is preserved by almost complex structure
QUESTION [0 upvotes]: I have a Lagrangian subspace $L$ of $\mathbb{R}^{2n}$ (i.e. $L^{\perp_{\omega_0}} = L$ where $\omega_0$ is the natural symplectic form.
I want to show that, given the natural almost complex structure $J_0$ on $\mathbb{R}^{2n}$, $J_0(L) = L^\perp$ (where here, $\perp$ is the orthogonal space using the euclidian metric).
if $n = 1$, this is clear. However, for $n = 2$, it is less clear.
Indeed, if $n = 2$, the Lagrangian condition reduces to
$$v_1w_2+v_3w_4 = w_1v_2+w_3v_4$$
for $v,w\in L$.
and $J_0(v)\cdot w$ for $v,w\in L$ reduces to
$$v_3w_1+v_4w_2-v_1w_3-v_2w_4$$
How can these two equations be linked?

REPLY [2 votes]: Use the formula $\omega(x,J_0(y))=b(x,y)$ where $b$ is the Euclidean metric.
If $x,y\in L$, $\omega(x,J_0(J_0(y))=b(x,J_0(y))=-\omega(x,y)=0$ since $J_0^2=-Id$. This implies that $J_0(L)$ is orthogonal to $L$.


TITLE: Formal derivation of the Fourier transform of Dirac delta using a distribution
QUESTION [1 upvotes]: The Fourier transform of Dirac delta is often naively calculated by considering Delta function as a function that makes sense within an integral and by using its fundamental property:
$$
\int_{-\infty}^{+\infty} f(x) \delta(x-x_0)dx = f(x_0)
$$
Then the Fourier transform of Dirac delta function can be evaluated to be $\hat{\delta(p)} = \frac{1}{\sqrt{2\pi}}$ simply by applying such property to the definition of Fourier transform.
However, here I am seeking for a formal proof using theory of distributions. In particolar, we know that the succession $D_n(x) := nD(nx)$ approximates Dirac delta $\delta(x)$, with $D(x) = \frac{1}{\sqrt{\pi}} e^{-x^2}$.
My objective is to derive the same result above discussed using this approach.
The Fourier transform of a Gaussian-like function is known from theory, therefore it is straightforward that:
$$
\mathcal{F} [ D(x) ]
= \mathcal{F} \left[ \frac{e^{-x^2}}{\sqrt{\pi}} \right]
= \frac{e^{-\frac{p^2}{4}}}{\sqrt{2\pi}}
$$
But this doesn't itself give me directly the solution, as there's still the term  $e^{-\frac{p^2}{4}}$; how should I proceed to prove my thesis formally?

REPLY [0 votes]: You forgot to rescale the Gaussian. For $D_n(x)= n D(nx)$, we have that
$$\tag{1}\mathcal F[D_n](p)=\mathcal F[D]\left(\frac p n\right), $$
so, applying the formula mentioned in the question, we see that
$$\tag{2}
\mathcal F[D_n](p)=\frac{ e^{-\frac{p^2}{4n^2}} }{\sqrt{2\pi}}\to \frac{1}{\sqrt{2\pi}}$$
as $n\to \infty$, as expected.
The convergence in (2) is in the sense of tempered distributions. Indeed, letting $\phi$ denote a Schwartz function, we have that
$$
\int_{-\infty}^\infty \frac{ e^{-\frac{p^2}{4n^2}} }{\sqrt{2\pi}}\phi(p)\, dp \to \int_{-\infty}^\infty \frac{ 1 }{\sqrt{2\pi}}\phi(p)\, dp$$
by dominated convergence. The right-hand side is exactly the pairing of the constant function $\frac{1}{\sqrt{2\pi}}$ with the test function $\phi$, which proves that the convergence in (2) holds in the sense of tempered distributions.
Conclusion. This answer contains a rigorous proof that $\mathcal{F}(\delta)=\frac{1}{\sqrt{2\pi}}$ using rescaled Gaussian, as requested.
Remark. We used a Gaussian but that is not necessary. Any integrable $D=D(x)$ such that $\mathcal F[D](0)=1$ will do, by the exact same reasoning.


TITLE: Given $Y$, suppose that $X|(Y = y)$ is a number picked at random in $[0, y]$. What is $P(X ≤ 1/2)$?
QUESTION [1 upvotes]: Question: Let $Y$ be a number picked a random in $[0, 1]$. Given $Y = y$, suppose that $X$ is a random variable such that $X|(Y = y)$ is a number
  picked at random in $[0, y]$. What is $P(X ≤ 1/2)$?

I am really stuck on how to start this one. Well I know that the definition of the conditional probability of two joint random variables is this:
$$f_{X|Y}(x|y) = \frac{f_{XY}(x,y)}{f_Y(y)}$$
but I am not sure how to define the joint probability $f(x,y)$, I think it will involve the uniform distribution?

REPLY [1 votes]: You were told the distributions of $Y$, and $X$ given a certain $Y$.
$$\begin{align}Y~\sim~\mathcal U(0;1) \quad\iff & \quad f_Y(y) = \mathbf 1_{y\in(0;1)}\\[1ex]X\mid Y=y ~\sim~\mathcal U(0;y) \quad \iff & \quad f_{X\mid Y}(x\mid y) = \tfrac 1 y~\mathbf 1_{x\in(0;y)}\end{align}$$
So, you know there joint distribution is:
$$\begin{align}f_{X,Y}(x,y) ~ =  & ~ f_{X\mid Y}(x\mid y)~f_Y(y) \\[1ex] ~= & ~ \dfrac 1 y\cdot\mathbf 1_{0\leq x\leq y}\cdot \mathbf 1_{0\leq y\leq 1}\end{align}$$
You can now find $\mathsf P(X\leq 1/2)$.

! $$\begin{align}\mathsf P(X\leq 1/2) ~= & ~ \iint\limits_{x\leq 1/2} f_{X\mid Y}(x\mid y)~f_Y(y)\operatorname d (x,y)
\\[2ex] = & ~ \int_0^{1}\int_0^{\min(y,1/2)} \frac 1 y~\operatorname d x\operatorname d y & = ~ \int_0^{1/2}\int_x^1 \dfrac 1 y~\operatorname d y\operatorname d x\end{align}$$


TITLE: Finding one sided derivative
QUESTION [0 upvotes]: I need a simple question answered.
for derivative $\dfrac{f(x+h) - f(x)}{h}$ and the equation is $\dfrac{1}{x}$ and I want to find the right side of the derivative at (1,1).
Would I just plug in $1$ for $x$ as $h$ approaches zero from the right? Thanks

REPLY [0 votes]: Yes, it is the general procedure:
$$
f'(1)=\lim_{h,0}\frac{f(h+1)-f(h)}{h}=\lim_{h,0}\frac{\frac{1}{h+1}-\frac{1}{h}}{h}=\lim_{h,0}\left(\frac{h}{h+1}-1\right)=\frac{0}{1}-1=-1
$$


TITLE: If $x_0 \in X$ and not in the closure of $M$, then there exists $T \in X^{\ast}$ such that $Tx_0 \neq 0$ and $T_{|M} = 0$
QUESTION [0 upvotes]: Let $X$ be a normed linear space, $M$ a linear subspace of $X$.  The following proposition

If $x_0 \in X$ and not in the closure of $M$, then there exists $T \in X^{\ast}$ such that $Tx_0 \neq 0$ and $T_{|M} = 0$

is mentioned as a corollary of this version Hahn-Banach theorem:

If $S$ is a bounded linear functional on $M$, then there exists $T \in X^{\ast}$ such that $Tx = Sx$ for all $x \in M$, and $||T|| = ||S||$.

Why is this? I don't see why I can't just argue this directly.  If $x \not\in \overline{M}$, then I can find a complement $W$ to $\overline{M}$ such that $X = W \oplus \overline{M}$ such that $x \in W$, a bounded linear functional $S$ on $W$ for which $Sx \neq 0$, and then extend $S$ to all of $X$ by defining $S(0,m) = 0$ for $m \in M$.

REPLY [1 votes]: One does not always have a complement $W$ (If it does, even the Hahn Banach Theorem is trivial). See a counterexample here.
To prove this, consider $M' = M \oplus \langle x\rangle$. This is a closed subspace of $X$. Define $T(m + ax) =a$ on $M'$ and use Hahn Banach Theorem to extend this $T$ to $X$.


TITLE: Prove that the integral of a nonnegative lebesgue measurable function h is the integral of measures m({h>a} over [0,\infty).
QUESTION [0 upvotes]: The problem is to prove that a nonnegative, Lebesgue measurable function $h$ satisfies the following equality: $\int h (x)dx=\int\chi_{[0,\infty)}m(${h>b}$)$ $ db$ where {h>b} inside $m$ represents the set {$x\in R^d:h(x)>b$}. Can someone please teach me how to prove this? I was thinking of first proving this when $h$ is a simple function but I am stuck even on this simplification. Also $\chi$ represents the characteristic function.

REPLY [1 votes]: Let the sequence of simple functions be
$$f_n(x)=\sum_{k=1}^{N(n)}\phi_{n,k}\mathbb{I}_{A_{n,k}}(x),\,A_{n,k}\cap A_{n,j}=\emptyset,\,\forall n $$
As $f_n \uparrow f$ we have $\{f_n>t\}\subseteq \{f> t\},\,\forall n\in \mathbb{N}$ and $\{f_n> t\}\subseteq \{f_{n+1}> t\}$ and we have
$$\{f > t\}=\Big\{\sup_{n \in \mathbb{N}} f_n > t\Big\}=\bigcup_{n \in \mathbb{N}}\{f_n>t\}$$
So by measure continuity
$$\lambda(\{f > t\})=\lim_{n \to \infty}\lambda(\{f_n>t\})$$
We have
$$\lambda(\{f_n>t\})=\sum_{k:\phi_{n,k}>t}\lambda(A_{n,k})=\sum_{k=1}^{N(n)}\mathbb{I}_{\{\phi_{n,k}>t\}}(k)\lambda(A_{n,k})$$
Also
$$\mathbb{I}_{\{\phi_{n,k}>t\}}(k)=\begin{cases}1& \phi_{n,k}> t\\
0& \phi_{n,k}\leq t\end{cases}=\mathbb{I}_{[0,\phi_{n,k})}(t)$$
Therefore
$$\lambda(\{f>t\})=\lim_{n \to \infty}\sum_{k=1}^{N(n)}\mathbb{I}_{[0,\phi_{n,k})}(t)\lambda(A_{n,k})$$
As $\lambda(\{f_n>t\})\leq \lambda(\{f_{n+1}>t\})$ we use MCT
$$\int_{[0,\infty)}\lambda(\{f>t\})dt=\lim_{n \to \infty}\sum_{k=1}^{N(n)}\phi_{n,k}\lambda(A_{n,k})=\int_\mathbb{R} f\,d\lambda$$


TITLE: Separation of two pointed polyhedral cones using hyperplanes generated by facets
QUESTION [2 upvotes]: Let $C_1$ and $C_2$ two pointed (that is, with vertex in $0$) polyhedral cones in $\mathbb{R}^n$ with $\dim(C_1)=\dim(C_2)=n$. If
$$\mbox{relative interior}(C_1)\cap \mbox{relative interior}(C_2)=\emptyset,$$
then it is clear that there exists a hyperplane that separates $C_1$ and $C_2$. My question is: Does there exist a $n-1$-dimensional face $F$ of $C_1$ or $C_2$ such that $F$ generates a hyperplane $H$ that separates $C_1$ and $C_2$? That is, is it possible to take as hyperplane of separation one of the hyperplanes generated by the faces of dimension $n-1$ of $C_1$ or $C_2$?
The answer is yes if $C_1\cap C_2$ has dimension $n−1$, since $C_1\cap C_2$ is then included in some face of dimension $n−1$ of $C_1$ or $C_2$. But if $C_1\cap C_2$ has dimension $<n−1$ then it is not clear.

REPLY [3 votes]: Yes for dimension 2 (pick the cone with larger angle; one of its sides fits). No for larger dimensions.
For a counterexample in dimension $3$, let $C_1$ be a positive orthant, and let $C_2$ be a negative orthant rotated by $\pi/3$ around $x=y=z$. (Note that you need to check just the faces of $C_1$, since the cones can be swapped by an orthogonal transform.)
There are similar examples in any higher dimension.


TITLE: What is the physical reason for Heisenberg uncertainty?
QUESTION [1 upvotes]: When send in a small opening particle acquire the spread of impulse p. E.g. there can be sometimes a huge value of p, which the particle doesn't have initially. So is with Energy too.
The question is where do these surplus energy and momentum come from? I never encountered that in books. I think there is no other place where it can come from except the atoms of the opening. But in that case follows the question what if the opening is cooled down to near -273? Take into account that one can have very slow particles so they don't deliver much energy but must take away. So they will cool down the opening and the whole barrier but not under -273,16.

REPLY [1 votes]: The Heisenberg principle is related to uncertainties of measurements. The particle is in a QM-state, described by a wave function. If we make some measurement that tells us that it is confined in a very small location, there is a limitation in my max. accuracy of knowledge about its momentum.
For example, it is necessary a electronic microscope to be sure about where things are, for small distances. But that means that electrons collide on whatever is being observed, and the device manages to form an image on the screen from the scattered electrons. Electrons are used instead of photons exactly because they have smaller wave lengths, what also means bigger momentum.
So, we can say that the source of the momentum of the observed particles is the momentum of the incoming ones, that must be greater and greater for smaller accuracy of the location.


TITLE: Linear Dependence Of A Sum
QUESTION [1 upvotes]: I had to prove the following notation: if $u1,u2,u3$ are linear depended then $u1+u2,u2+u3,u3+u1$ are also linear depended.
I tried to contradict saying that I assume that P is right but Q is wrong as for $u1,u2,u3$ are linear depended and $u1+u2,u2+u3,u3+u1$ are not linear depended.
I choose $u1 =(0,0,1), u2= (1,1,0), u3=(2,2,1)$ and show that both $u1,u2,u3$  and $u1+u2,u2+u3,u3+u1$   are linear depended.

Is my proof is right?
what is the reason that the notation is right?

Thanks a lot!!

REPLY [0 votes]: Hint:
Let $S = \{u_1, u_2, u_3\}$ be the set containing the given vectors.  Now, consider $\rm{span}\{S\}$.  Since $S$ is linearly dependent, it follows that the basis of $\rm{span}\{S\}$ is a proper subset of $S$ (that is, a subset of $S$ with fewer elements).
Now, what are the possible dimensions of $\rm{span}\{S\}$?  How do they compare to the size of the set $\{u_1+u_2, u_2+u_3, u_1+u_3\}$?


TITLE: Suppose that $|x-4|\leq1 $
QUESTION [1 upvotes]: EDIT: Okay I got it now.
Take original:
$-1\leq x-4\leq1$
Times by $(x+4)$ on all sides
$-(x+4)\leq x^2-16 \leq x+4$
The most $x+4$ can be is 9 so,
$|x^2-16| \leq 9$

Word for word:

Suppose that $|x-4|\leq 1$.
(a) What is the maximum possible value for $|x+4|$?
(b) Show that $|x^2-16|\leq 9$

My main trouble is with (b).
For (a) I did this:
$|x-4|\leq1$
$-1\leq x-4\leq1$
Add 8 to all sides:
$7\leq x+4\leq9$
So the greatest possible value is 9. How do I solve (b) though?
EDIT: I changed the inequality on (b)

REPLY [1 votes]: It seems to me that (b) is impossible.
$$|x-4|\le 1 \implies 3\le x\le 5$$
$$\implies 9\le x^2 \le 25$$
$$\implies -7 \le x^2-16 \le 9 $$
$$\implies 7 \le |x^2-16|\le 9 $$


TITLE: Positive invertible element of a C*- algebra
QUESTION [0 upvotes]: The following is  Theorem 2.2.5 of Murphy's C*-algebras and operator theory:
Let $A$ be an unital C*-algebra and $a,b$ are positive invertable elements, if $a\leq b$, then $0\leq b^{-1}\leq a^{-1}$.
To show it, firstly the author claims if $c\geq 1$ then $c$ is invertable and $c^{-1}\leq 1$.
While I think the following is a counterexample for this claim.
Let $A=C([2,4])$, then $f(x) = x+1 $ is a positive invertable function in $A$, and $f\geq 1$. Also $f^{-1}(x) = x-1$ but $f^{-1}\not \leq 1$.
Please tell me where  my mistake is and also give me a proof for the claim. Thanks in advance.

REPLY [1 votes]: For the proof of the author's claim, note that $c \geq 1 = c ^{-1} c$ if and only if $1 \geq c^{-1}$.
This example doesn't quite work since it doesn't meet the hypotheses set out by the author. Let's consider the C*-algebra $A := C([2,10])$ and the same function $f$, which you defined above. There are various notions of invertibility in the C*-algebra you're examining. In this setting, the operations are defined pointwise and so the inverse of your function should really be $1/(x+1)$, which does satisfy the required property.


TITLE: Endomorphism as a ring
QUESTION [1 upvotes]: Let V be a vector space over the field K. Show that $(\text{End}_K(V),+,\circ)$ is a ring.
I know that an endomorphism is a homomorphism from V to V. So for example i should show that + is associative with $\forall a,b,c \in \text{End}_K(V) : a+(b+c)=(a+b)+c$ but how do i do that with endomorphisms??

REPLY [1 votes]: First of all, $\operatorname{End}_K(V)$ is the set consisting of all endomorphisms of $V$, that is, $K$-linear maps from $V$ to $V$.
The addition $+$ in the first line is defined as follows: For $f, g \in \operatorname{End}_K(V)$, the sum $f + g \in \operatorname{End}_K(V)$ is defined by
$$ (f + g)(v) = f(v) + g(v) $$
for every $v \in V$. In other words, the sum of endomorphisms is carried over from that of the ground field $K$. Hence associativity, for example, is now a trivial stuff.


TITLE: Select Candidates based on votes count permutations
QUESTION [0 upvotes]: I have a question i am not sure which formulae fit for such scenario
Twenty people are voting for one of 5 candidates. They have secret ballot, each voter votes for one of 5 candidates. The result of an election is the number of votes for each of the candidate. How many possible results can this vote have?

REPLY [1 votes]: Remember that the following are equivalent:

The number of integer solutions of
$$x_1+x_2+...+x_n=r, \ \ \ \ \  x_i\geq0$$
Number of selections, with repetition, of size $r$ from a collections of size $n$.
Number of ways $r$ identical objects can be distributed among $n$ distinct containers.

Let each candidate be $x_i$ for $i \in \{1,2,3,4,5 \}$.
Then you are looking for the number of nonnegative integer solutions for
$$x_1+x_2+x_3+x_4+x_5 = 20.$$
This is equivalent to finding the number of selections, with repetition, of size $20$ from a collection of size $5$, which is given by
$$\binom{5+20-1}{20} = \binom{24}{20} = 10,626.$$
So you have $10,626$ possible results for the election.
This is because you are not taking into account the identity of the voters, so the $20$ votes are counted as identical objects to be distributed among $5$ distinct "containers", which, in this case, would refer to the candidates.


TITLE: Is an reflexive relation also antisymetric?
QUESTION [2 upvotes]: I've already seen a similar question here:
Is an Anti-Symmetric Relation also Reflexive?
But my question is rather, if you know that a relation is reflexive, then, can this relation also be antisymetric?
As far as I know, by definition, a relation is antisymetric if for two elements in R, xRy and yRx then x=y. For this to be true, I should only need x=y to be true for the relation to be antisymetric. In that case, the relation is antisymetric if we know it is reflexive already.
Am I wrong?

REPLY [4 votes]: Reflexivity does not imply anti-symmetry.
Consider a relationship defined over just $2$ elements: $a$ and $b$. And suppose that we have $aRa$, $aRb$, $bRb$, and $bRa$. Then $R$ is reflexive (since we have both $aRa$ and $bRb$), but $R$ is not anti-symmetric: we have $aRb$ and $bRa$, but it is not the case that $a = b$


TITLE: Prove $2^{2n} = \sum_{k=0}^{n}\binom{2n+1}{k}$
QUESTION [9 upvotes]: I'm trying to prove the following equation above. So far I have:
\begin{align}
2^{2n} &= (1+1)^{2n}\\
&= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{n-k} = \sum_{k=0}^{2n}\binom{2n}{k} & \text{(By the Binomial Theorem)}
\end{align}
I know I have to use the following identity somehow:
$$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$
How do I split my summation to get what I'm looking for? Thanks!
EDIT: HERE IS MY SOLUTION
\begin{align*}
2^{2n} &= (1+1)^{2n}\\
&= \sum_{k=0}^{2n}\binom{2n}{k}1^k1^{2n-k} & \text{(By the Binomial Theorem)}\\
&= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{k}\\
&= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=n+1}^{2n}\binom{2n}{2n-k} & \text{(Binomial Symmetry)}\\
&= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=0}^{n-1}\binom{2n}{k}\\
&= \sum_{k=0}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\
&= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n}{k} + \sum_{k=1}^{n}\binom{2n}{k-1}\\
&= \binom{2n}{0} + \sum_{k=1}^{n}\binom{2n+1}{k} & \text{(By Identity listed above)}\\
&= \sum_{k=0}^{n}\binom{2n+1}{k}
\end{align*}

REPLY [5 votes]: $$\sum_{k=0}^{n}\binom{2n+1}{k}=\frac{1}{2}\sum_{k=0}^{2n+1}\binom{2n+1}{k}=\frac{2^{2n+1}}{2}=2^{2n}$$
Using the relation $$\binom{2n+1}{k}=\binom{2n+1}{2n+1-k}$$ for $0 \le k \le n$.

REPLY [4 votes]: $$ 2^{2n}=\frac12\cdot 2^{2n+1}=\frac12\sum_{k=0}^{2n+1}{2n+1\choose k}=\frac12\sum_{k=0}^n\left({2n+1\choose k}+{2n+1\choose 2n+1-k}\right)$$

REPLY [1 votes]: I would suggest to use induction:
For $n=1$:
$2^2 = \binom{3}{0}+\binom{3}{1}$, true.
For $m=n+1$:
$2^{2n+2}=4\cdot 2^{2n} = \sum_{k=0}^{n}\binom{2n+1}{k} + \binom{2n+2}{n+1} = 2^{2n} + \binom{2n+2}{n+1} = 2^{2n} + \frac{(2n+2)!}{(n+1)!^2}$