text:
\section{Diagonal core sampling}\label{sec:diag_sampling}

So far, we have focused on the case when $\mathbfcal{G}$ is dense and has no particular structure. In that case, we have seen that we require at least $\sum_{i=1}^R K_i$ sensors to recover our signal with a finite MSE. In many cases of interest, $\mathbfcal{G}$ admits a structure. In particular, in this section, we investigate the case when $\mathbfcal{G}$ is a diagonal tensor. Under some mild conditions on the entries of $\{\matx{U}\}_{i=1}^R$, we can leverage the structure of $\mathbfcal{G}$ to further increase the compression. As before, we  develop an efficient and near-optimal greedy algorithm based on minimizing the frame potential to design the sampling set.

\subsection{Identifiability conditions} \label{sec:identifiability_constraints}

In contrast to the dense core case, the number of unknowns in a multilinear system of equations with a diagonal core does not increase with the tensor order, whereas for a dense core it grows exponentially. This means that when sampling signals with a diagonal core decomposition, one can expect a stronger compression.

To derive the identifiability conditions for \eqref{eq:sampling_eq_kr}, we present the result from~\cite{rank_kr} as the following theorem.
\begin{theorem}[Rank of Khatri-Rao product \cite{rank_kr}]\label{thm:rank_rk}
Let $\matx{A}\in\C^{N\times K}$ and $\matx{B}\in\C^{M\times K}$ be two matrices with no all-zero column. Then,
  \begin{equation*}
    \mathrm{rank}(\matx{A}\odot\matx{B})\geq\max\{\mathrm{rank}(\matx{A}),\mathrm{rank}(\matx{B})\}.
  \end{equation*}
\end{theorem}

Based on the above theorem, we can give the following sufficient conditions for identifiability of the system \eqref{eq:sampling_eq_kr}.
\begin{corollary}
Let $z_i$ denote the maximum number of zero entries in any column of $\matx{U}_i$. If for every $\matx{\Psi}_i(\mathcal{L}_i)$ we have $|\mathcal{L}_i|>z_i$, and there is at least one $\matx{\Psi}_j$ with $\mathrm{rank}(\matx{\Psi}_j)=K_\text{c}$, then $\matx{\Psi}(\mathcal{L})$ has full column rank.
\end{corollary}
\begin{proof}
Selecting $L_i>z_i$ rows from each $\matx{U}_i$ ensures that no $\matx{\Psi}_i$ will have an all-zero column. Then, if for at least one $\matx{\Psi}_j$ we have $\mathrm{rank}(\matx{\Psi}_j)=K_\text{c}$, then due to Theorem~\ref{thm:rank_rk} we have
  \begin{align*}
    \mathrm{rank}(\matx{\Psi}(\mathcal{L}))&\geq\max_{i=1,\dots,R}\{\mathrm{rank}(\matx{\Psi}_i)\}\\
    &=\max\left\{\mathrm{rank}(\matx{\Psi}_j),\max_{i\neq j}\{\mathrm{rank}(\matx{\Psi}_j)\}\right\}=K_\text{c}.
  \end{align*}
\end{proof}
Therefore, in order to guarantee identifiability we need to select $L_j\geq \max\{K_\text{c}, z_j+1\}$ rows from any factor matrix $j$, and $L_i\geq\max\{1, z_i+1\}$ from the other factors with $i\neq j$. In many scenarios, we usually have $\{z_i=0\}_{i=1}^R$ since no entry in $\{\matx{U}_i\}_{i=1}^R$ will exactly be zero. In those situations we will require to select at least $L=\sum_{i=1}^R L_i\geq K_\text{c} + R -1$ elements.

\subsection{Greedy method}

As we did for the case with a dense core, we start by finding an expression for the frame potential of a Khatri-Rao product in terms of its factors. The Grammian matrix $\matx{T}(\mathcal{L})$ of a diagonal core tensor decomposition has the form
\begin{align*}
  \matx{T}&=\matx{\Psi}^H\matx{\Psi}=\left(\matx{\Psi}_1\odot\dots\odot\matx{\Psi}_R\right)^H\left(\matx{\Psi}_1\odot\dots\odot\matx{\Psi}_R\right)\\
  &=\matx{\Psi}_1^H\matx{\Psi}_1\circ\dots\circ\matx{\Psi}_R^H\matx{\Psi}_R=\matx{T}_1\circ\dots\circ\matx{T}_R.
\end{align*}
Using this expression, the frame potential of a Khatri-Rao product becomes
\begin{equation}
  \FP{\matx{\Psi}}=\tr{\matx{T}^H\matx{T}}=\norm{\matx{T}}_F^2=\norm{\matx{T}_1\circ\dots\circ\matx{T}_R}_F^2.\label{eq:kr_fp}
\end{equation}
For brevity, we will denote the frame potential as an explicit function of the selected set as
\begin{equation}
  P(\mathcal{L})\coloneqq\FP{\matx{\Psi}(\mathcal{L})}=\norm{\matx{T}_1(\mathcal{L}_1)\circ\dots\circ\matx{T}_R(\mathcal{L}_R)}_F^2.
\end{equation}

Unlike in the dense core case, the frame potential of a Khatri-Rao product cannot be separated in terms of the frame potential of its factors. Instead, \eqref{eq:kr_fp} decomposes the frame potential using the Hadamard product of the Grammian of the factors.

\subsubsection{Submodularity of $P(\mathcal{L})$}

Since $P(\mathcal{L})$ does not directly satisfy the conditions [cf. Theorem~\ref{thm:submodular_matroid}]  required for near optimality of the greedy heuristic, we propose using the following set function $Q:2^\mathcal{N}\rightarrow\R$ as a surrogate for the frame potential
\begin{equation}
  Q(\mathcal{S})\coloneqq P(\mathcal{N})-P(\mathcal{N}\setminus\mathcal{S})
  \label{eq:set_func_2}
\end{equation}
with $P(\mathcal{N}) =\norm{\matx{T}_1(\mathcal{N}_1)\circ\dots\circ \matx{T}_r(\mathcal{N}_r)}_F^2$ and
$P(\mathcal{N}\setminus\mathcal{S}) = \norm{\matx{T}_1(\mathcal{N}_1\setminus\mathcal{S}_1)\circ\dots\circ \matx{T}_R(\mathcal{N}_R\setminus\mathcal{S}_R)}_F^2.$

\begin{theorem}\label{thm:submodular_Q}
   The set function $Q(\mathcal{S})$ defined in \eqref{eq:set_func_2} is a normalized, monotone non-decreasing, submodular function for all subsets of $\mathcal{N}=\bigcup_{i=1}^R\mathcal{N}_i$.
\end{theorem}
\begin{proof}
  See Appendix~\ref{ap:proof_Q}.
\end{proof}

Using $Q$ and imposing the identifiability constraints defined in Section~\ref{sec:identifiability_constraints} we can write the related optimization problem for the minimization of the frame potential as
\begin{equation}
\label{eq:submodular_max_kr}
\maximize_{\mathcal{S}\subseteq\mathcal{N}}  Q(\mathcal{S}) \quad \text{s. to} \quad \mathcal{S}\in \mathcal{I}_u\cap\mathcal{I}_p
\end{equation}

where $\mathcal{I}_u=\{\mathcal{A}\subseteq\mathcal{N}:|\mathcal{S}|\leq N-L\}$ and $\mathcal{I}_p=\{\mathcal{A}\subseteq\mathcal{N}:|\mathcal{A}\cap\mathcal{N}_i|\leq \beta_i\quad i=1,\dots,R\}$ with $\beta_j = N_j-\max\{K_\text{c},z_j\}$ and $\beta_i=N_i-\max\{1,z_i+1\}\;\; \text{for}\;\;i\neq j$. Here, the choice of $j$ is arbitrary, and can be set depending on the application. For example, with some space-time signals it is more costly to sample space than time, and, in those cases, $j$ is generally chosen for the temporal domain.

This is a submodular maximization problem with a truncated partition matroid constraint [cf. Example~\ref{ex:partition_matroid} from Definition~\ref{def:matroid}]. Thus, from Theorem~\ref{thm:submodular_matroid}, we know that greedy maximization of \eqref{eq:submodular_max_kr} using Algorithm~\ref{alg:greedy_matroid} has a multiplicative near-optimal guarantee.

\begin{corollary}\label{corollary:bound_Q}
The greedy solution $\mathcal{S}_\text{greedy}$ to \eqref{eq:submodular_max_kr} obtained using Algorithm~\ref{alg:greedy_matroid} is $1/2$-near-optimal, i.e.,
$
    Q(\mathcal{S}_\text{greedy})\geq \frac{1}{2}Q(\mathcal{S}^\star).
 $
 Here, $\mathcal{S}^\star$ denotes the optimal solution of \eqref{eq:submodular_max_kr}.
\end{corollary}

Similar to the dense core case, we can also provide a bound on the near-optimality of of the greedy solution with respect to the frame potential.
\begin{theorem}
The solution set $\mathcal{L}_\text{greedy} = \mathcal{N} \setminus \mathcal{S}_\text{greedy}$ obtained from Algorithm~\ref{alg:greedy_matroid} is near optimal with respect to the frame potential as
$
    P(\mathcal{L}_\text{greedy})\leq \gamma P(\mathcal{L}^\star),
 $
 with $\gamma=0.5\left(\norm{\matx{T}_1(\mathcal{N}_1)\circ\dots\circ \matx{T}_R(\mathcal{N}_R)}_F^2{KL_{\text{\rm min}}^{-2}}+1\right)$ and $\mathcal{L}^\star = \mathcal{N} \setminus~\mathcal{S}^\star$.
\end{theorem}
\begin{proof}
Based on the proof of Theorem~\ref{thm:approx_fp}. The bound is obtained using \eqref{eq:kr_fp} instead of \eqref{eq:kron_fp} in the derivation.
\end{proof}

\subsubsection{Computational complexity}

The computational complexity of the greedy method is now governed by the complexity of computing the Grammian matrices $\matx{T}_i$. This can greatly be improved if before starting the iterations, one precomputes all the outer products in $\{\matx{T}_i\}_{i=1}^R$. Doing this has a computational complexity of $\mathcal{O}(N_\text{max}K_\text{c}^2)$. Then, in every iteration, the evaluation of $P(\mathcal{L})$ would only cost $\mathcal{O}(RK_\text{c}^2)$ operations. Further, because in every iteration we need to query $\mathcal{O}(N_i)$ elements on each domain, and we run the algorithm for $N-L$ iterations, the total time complexity of the iterations is $\mathcal{O}(RN_\text{max}^2K_\text{c}^2)$. This term dominates over the complexity of the precomputations, and thus can be treated as the worst case complexity of the greedy method.

\subsubsection{Practical considerations}

The proposed scheme suffers from the same issues as in the dense core case. Namely, it tends to empty the domains sequentially, thus producing solutions which are tight on the identifiability constraints. Nevertheless, as we indicated for the dense core, the drop in performance associated with the proximity of the solutions to the constraints can be reduced by giving some slack to the constraints.

config: arxiv


TITLE: Area that is bounded by functions
QUESTION [1 upvotes]: The functions $$f_k(x)=\frac{x+k}{e^x}$$ are given.
Let $A(u)$ be the area that is bounded by $f_1, f_3$, the $x$-axis und the line $x=u$.
I want to check the area if $u\rightarrow \infty$.
$$$$
To calculate the area $A(u)$ do we calculate the area that is bounded by $f_1$ with endpoints the intersection point of that function with the $x$-axis and $x=u$ and the the area that is bounded by $f_2$ with endpoints the intersection point of that function with the $x$-axis and $x=u$ and then we subtract these two areas?
But in that way we haven't taken into consideration that the area has to be bounded by the $x$-axis, do we?

REPLY [1 votes]: we start with finding the zeros of $f_k$.
$$\frac{x+k}{e^x}=0$$
$$\frac{x}{e^x}=-\frac{k}{e^x}$$
$$x=-k$$
so we see that
$$A(u)=\int_{-3}^{u}f_3(x)dx-\int_{-1}^{u}f_1(x)dx$$
$$A(u)=\int_{-3}^{-1}f_3(x)dx+\int_{-1}^{u}f_3(x)-f_1(x)dx$$
$$A(u)=\int_{-3}^{-1}xe^{-x}dx+3\int_{-3}^{-1}e^{-x}dx+2\int_{-1}^{u}e^{-x}dx$$
$$A(u)=-2e^3+3(e^3-e)+2(e-e^{-u})$$
$$A(u)=e^3-e-2e^{-u}$$
So $$\lim_{u\to\infty}A(u)=e^3-e$$


TITLE: How to use the Divergence Theorem in this question?
QUESTION [1 upvotes]: Question:
Let $r=\sqrt {x^2+y^2+z^2}$ and $\mathbf E = -\mathbf \nabla \big(\frac kr \big)$ where $k$ is a constant. Show that
$$ \iint_S \mathbf E \cdot d \mathbf S = 4\pi k$$
where $S$ is any closed surface that encloses the origin.

The hint was to first show this for $S$ being a sphere centered at origin, then use the divergence theorem to show this for general $S$.
Doing this for sphere surface was easy, but then when I tried to use the Divergence Theorem I got
$$ \iint_S \mathbf E \cdot d \mathbf S = \iiint_V \nabla \cdot \mathbf E dV =0$$
because $\nabla \cdot \mathbf E =0$, and I realized that this was because $\mathbf E$ has a blowup at the origin so that the Divergence Theorem did not apply.
Any hints as to what I should do? Is there a version of the Divergence Theorem that accounts for singularities?

REPLY [1 votes]: The divergence theorem applies to a body $B$,  its boundary $\partial B$, and a vector field $E$ sufficiently smooth on $B\cup\partial B$.
Your surface $S$ bounds a body $B$ containing the origin in its interior. Now apply the divergence theorem to the body $B':=B\setminus B_\epsilon$ and $E$, where $B_\epsilon$ is a tiny ball around the origin. The boundary of $B'$ is $S-S_\epsilon$ (minus sign intended!).


TITLE: why is the domain of $\sec^{-1} x$, $\mathbb{R}- (-1 ,1)$? why can't $x$ take a values like 0.2, 0.3, etc?
QUESTION [1 upvotes]: Why is the domain of $\sec^{-1} x$, $\mathbb{R}- (-1 ,1)$?  why can't $x$ take a values like $0.2, 0.3$ or $0$?

REPLY [1 votes]: $\sec^{-1}x=\theta \rightarrow x=\sec\theta$. Now what is the range of $\sec\theta$? Can it take values like $0,0.2,0.3$?


TITLE: The shuffle algebra over the rationals is isomorphic to the polynomial algebra in the Lyndon words
QUESTION [2 upvotes]: On this wikipedia page is stated that over the rational numbers,  the shuffle algebra (over a set $X$) is isomorphic to the polynomial algebra in the Lyndon words (on $X$). I was wondering if you can show me a proof of this or give me a reference. Ideally I am looking for an explicit isomorphism between these two algebras.

REPLY [2 votes]: This is proven in Theorem 6.3.4 of Hopf Algebras in Combinatorics
 by Grinberg and Reiner.
They call it "Radford’s theorem on the shuffle algebra" citing Theorem 3.1.1(e) of A natural ring basis for the shuffle algebra and an application to group schemes by Radford where you can find another proof.


TITLE: formula for getting the least amount in the last column
QUESTION [0 upvotes]: I'm looking for a formula, that given $x ≥ 5$ , it will split $x$ over 3 columns with the least amount in the 3rd column, however the 3rd column must be > 0.
so where $x = 5$ it would look like:
2|2|1
or $x = 16$
6|6|4

REPLY [1 votes]: If $n=3k$, split them $k|k|k$.
If $n=3k+1$, split them $k+1|k+1|k-1$.
If $n=3k+2$, split them $k+1|k+1|k$.


TITLE: Show that $A \cong \mathbb{C}^n$ with A a commutative algebra
QUESTION [3 upvotes]: Let A be a commutative algebra of finite dimension, and if $A$ has no nilpotent elements other than $0$, is true that $A \cong  \mathbb{C}^n$ ?

The question emerge to my mind, I thought that the finite dimension tell us that the scheme is Artinian (geometrically dimension 0).
I think the pattern is just a meeting of $n$ points but I have not managed to prove it.
Someone can enlighten me please ?
Thanks

REPLY [7 votes]: An artinian ring $A$ has only finitely many prime ideals, which are all maximal. Thus, by the Chinese remainder theorem,
$$A / \mathfrak{n} \cong A / \mathfrak{m}_1 \times \cdots \times A / \mathfrak{m}_r$$
where $\mathfrak{m}_1, \ldots, \mathfrak{m}_r$ are the distinct prime/maximal ideals of $A$ and $\mathfrak{n}$ is the nilradical/Jacobson radical.
In particular, if the only nilpotent element of $A$ is $0$, then $A$ is a product of finitely many fields. Moreover, if $A$ is a finite $\mathbb{C}$-algebra, then each $A / \mathfrak{m}_i$ must also be a finite $\mathbb{C}$-algebra, hence, must be (isomorphic to) $\mathbb{C}$ itself.


TITLE: Geometric morphism whose counit is epic
QUESTION [4 upvotes]: Is there a name for the class of geometric morphisms whose counits are epic (equivalently, whose direct images are faithful)?
This notably includes the class of inclusions/embeddings of toposes. By Example A4.6.2 in Johnstone's Sketches of an Elephant: A Topos Theory Compendium, all such morphisms are localic, but since Johnstone doesn't include a name there (and his cross-referencing is generally very thorough) I expect that they don't feature in the text in their own right.
If no one can dig up a reference, I would like to put forward injection as a name for this property, not only because faithfulness gives injectivity on hom-sets, but also because this is the conceptual dual of a geometric surjection, which has monic unit/faithful inverse image.
EDIT: In response to a requested example of an "injection" which fails to be an inclusion, the most obvious first place to search for non-trivial examples is to consider injections into Set, but these turn out to be disappointing. The domain must be a localic topos, and so the global sections functor sends a natural transformation $\alpha: F \to G$ to $\alpha(1)$; this is faithful if and only if every natural transformation of sheaves is determined uniquely by its value on the full space. Originally I thought discrete spaces would work, but if there exists any proper open subset, a disjoint union of two copies of the corresponding representable sheaf has a non-trivial automorphism which the global sections functor ignores, so the locale must in fact be trivial!
See Tim's comment for a more plausible example.

REPLY [1 votes]: I originally posted the following as a bunch of comments, but maybe it's better to consolidate into a not-really-an-answer:

Note that $f_*$ is faithful iff it is conservative: to see that conservative implies faithful, note that $u=v:c\to d$ if and only if $Eq(u,v)\to c$ is an isomorphism and use the fact that $f_∗$ preserves equalizers; to see that faithful implies conservative, use the fact that faithful functors reflect epimorphisms and monomorphisms, and any epic monic in a topos is an iso. (I'm not sure how much of this generalizes to ∞-topoi...). Anyway, that's another equivalent formulation to look for.
I once asked a question about (pseudo)monomorphisms of (∞)-topoi. Alexander Campbell pointed out a paper of Bunge and Lack where pseudomonomorphisms of topoi are discussed; they apparently don't know an example which is not an embedding. Which begs the question: do you know an example of an "injection" in your sense which is not an embedding? I'd also be curious about any example where $f_∗$ is not injective on isomorphism classes
Note that $f_∗$ is a pseudomonomorphism of underlying categories iff it is faithful and is a full subgroupoid inclusion on underlying groupoids -- so this might be a natural condition to add to faithfulness of $f_∗$ in case you find you need to tweak the definition in search of better properties.
Finally, note that if f is an "injection" in your sense, then so is the surjective part of its surjection / embedding factorization. So it would be of interest to study the surjective "injections". If $f: \mathcal X \to \mathcal Y$ is surjective, then $f_∗:\mathcal Y \to \mathcal X$ is comonadic. So $f$ will be an "injective" surjection iff it exhibits $\mathcal Y$ as the coalgebras for a left-exact comonad $G: \mathcal X \to \mathcal X$ such that $G$ is faithful (equivalently, conservative). I keep meaning to learn more about left exact comonads... perhaps this is a common case to be in... Anwway, an geometric morphism is then an "injection" iff it factors as coalgebras for a conservative lex comonad followed by an embedding.

Regarding the terminology: I get the sense that because inverse and direct images play rather different roles in topos theory (after all, inverse images preserve finite limits in addition to being left adjoints), it's typically not the case that taking a definition in topos theory and reversing the roles of the inverse and direct image functors yields a "similarly useful" definition. So I would be hesitant to use the term "injection" simply because of the formal duality to "surjection". That being said, I don't have anything against this terminology, but perhaps the experts might.