text:
Show Summary Details
More options …

# Open Mathematics

### formerly Central European Journal of Mathematics

Editor-in-Chief: Gianazza, Ugo / Vespri, Vincenzo

IMPACT FACTOR 2018: 0.726
5-year IMPACT FACTOR: 0.869

CiteScore 2018: 0.90

SCImago Journal Rank (SJR) 2018: 0.323
Source Normalized Impact per Paper (SNIP) 2018: 0.821

Mathematical Citation Quotient (MCQ) 2018: 0.34

ICV 2017: 161.82

Open Access
Online
ISSN
2391-5455
See all formats and pricing
More options …
Volume 15, Issue 1

# Growth functions for some uniformly amenable groups

Janusz Dronka
/ Bronislaw Wajnryb
/ Paweł Witowicz
/ Kamil Orzechowski
Published Online: 2017-04-26 | DOI: https://doi.org/10.1515/math-2017-0049

## Abstract

We present a simple constructive proof of the fact that every abelian discrete group is uniformly amenable. We improve the growth function obtained earlier and find the optimal growth function in a particular case. We also compute a growth function for some non-abelian uniformly amenable group.

MSC 2010: 20F65; 20K21; 22D40

## 1 Introduction

A discrete group G (group G with the discrete topology) is amenable if and only if for every finite subset AG and every t > 0, there exists a non-empty finite subset UG such that |AU| ≤ (1 + t)|U| where |U| denotes the cardinality of U.

A group G is uniformly amenable if the cardinality of the set U in the definition of amenability depends only on t and on the cardinality of A and not on the particular finite set A. More precisely (see [1]).

#### Definition 1.1

A group G is uniformly amenable if there exists a growth function q : ℝ+ × ℕ → ℕ such that for every finite subset AG and every t > 0,

(*) there exists a non-empty finite subset UG, |U| ≤ q(t, |A|) and |AU| ≤ (1 + t)|U|.

The condition in Definition 1.1 is called the uniform Følner condition. There is another approach to uniform amenability due to H. Kesten. It was originally introduced while considering so called symmetric random walks on groups, which are a kind of Markov chains with G as the state space (see [2]). However, Kesten’s approach can be reformulated in a combinatorial manner involving only the group structure without referring to probabilistic issues.

Let A be a finite symmetric subset of G (that means A−1 = A). By m2n(A) we denote the number of all (ordered) 2n-tuples (a1, …, a2n) with aiA, i = 1, …,2n such that the product a1a2n equals e (the identity element of the group). The group G is uniformly amenable if and only if for any natural number k and for any A with |A| = k, $(m2n(A))12n⇉k,$

where the convergence is uniform for all symmetric subsets with the same cardinality k. This condition is called the uniform Kesten condition. The equivalence between the uniform Følner and Kesten conditions was proved by Wysoczański in [10] using ultrapowers of groups.

There is an interesting relationship between the growth function q and values of m2n, namely, according to Kaimanovich, Vershik ([3] and [4]), for a uniformly amenable group G the following inequality holds for all symmetric subsets A with cardinality k $m2n(A)≥k2nsup0

If additionally A does not contain e and elements of order two, the estimation can be refined to $m2n(A)≥k2nsup0

Uniformly amenable groups are obviously amenable. The group S of permutations of ℕ which move only a finite number of elements is an example of a group which is amenable but not uniformly. It is known ([5]) that the class of uniformly amenable groups is closed under extensions and taking subgroups.

More recently some results on uniformly amenable groups were obtained in [6].

Uniformly amenable groups are related to invariant uniform approximation in Banach spaces. We recall briefly this connection in order to motivate our results.

Let G be a compact abelian group, let Γ be the discrete abelian group of the characters of G. Let X = L1(G) be the Banach space of complex functions on G absolutely integrable functions with respect to Haar measure on G. For gX and γ ∈ Γ let $\stackrel{^}{g}\left(\gamma \right)=\int g\left(x\right)\gamma \left(x\right)dx.$ We treat ĝ as a functional on Γ. We say that X has an invariant uniform approximation property (inv. ubap) if there exists a uniform bound β : ℝ × ℕ → ℕ, such that for every ϵ > 0 and every finite subset M ⊂ Γ there exists a function gX with ∥g1 ≤ (1 + ϵ) and |supp(ĝ)| ≤ β(ϵ, |M|).

In [7], Lemma 2.1 it was proven that if Γ has a growth function q(t, k) then X has a uniform bound β(ϵ, k) ≤ q(ϵ, k)2. It was also proven that every Γ has a growth function q(t, k) = (k / t)k and therefore X has a uniform bound β(ϵ, k) ≤ (k / ϵ)2k.

J. Bourgain gave a direct proof in [8] that X has inv. ubap but his proof is difficult to understand and the result is described in terms of entropy numbers.

P. Wojtaszczyk interpreted in [9] (page 209, Theorem 13) the result of Bourgain as a uniform bound β(ϵ, k)≤ (c / ϵ)2k where c is a constant depending on the group G. He also gave a proof of this fact using functional analysis.

In the present paper we give an elementary simple proof that every discrete abelian group has a growth function $q\left(t,k+1\right)=\left(\begin{array}{c}n+k-1\\ k\end{array}\right),$ where t = k / n. By the Stirling formula this is smaller than (2e / t)k. By Lemma 2.1 in [7] it gives a universal bound β(ϵ, k) = (2e / ϵ)2(k − 1) with a small explicit constant c = 2e independant of the group G.

We prove in Lemma 2.5 that our q(t, k + 1) is the minimal growth function if k = 2. We also present an example of a group M of matrices with arbitrary ring coefficients and prove that it is uniformly amenable and we find a growth function for this group. It follows that the group G given in [10] is uniformly amenable because G is a subgroup of M.

## 2 Abelian groups

It is known that every discrete abelian group is uniformly amenable. In this section we shall give a very simple proof of this fact.

We denote by ${C}_{n}^{k}$ the binomial coefficient ${C}_{n}^{k}=\left(\begin{array}{l}n\\ k\end{array}\right).$

#### Lemma 2.1

If a group G satisfies the condition (*) for every finite subset A containing e, then it satisfies (*) for every finite subset A with the same growth function q(t, k).

#### Proof

Let A = {a1, a2, …, ak} ⊂ G and let ${b}_{i}={a}_{1}^{-1}{a}_{i}$ for i = 1, 2, …, k. Let B = {b1, b2, …, bk}. Suppose that U is a finite subset of G such that |BU| ≤ (1 + t)|U|. Then a1BU = AU has the same cardinality as BU so |AU| ≤ (1 + t)|U|.  □

We now pass to the abelian groups. We denote the composition law by + and we denote the neutral element by 0.

#### Lemma 2.2

Let G be an abelian group and let A = {0, a1, …, ak} ⊂ G. Let $U\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}=\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\left\{\sum _{i=1}^{k}{n}_{i}{a}_{i}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}:\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}{n}_{i}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\in$ {0, 1, …, n − 1}, ∑nin − 1}. Then $|\left(A+U\right)\mathrm{\setminus }U|\le \left(\frac{k}{n}\right)|U|.$

#### Proof

Consider all elements in (A + U) \ U. Every such element can be represented by a sum w = ∑nsas where 0 ≤ nsn and $\sum _{s=1}^{k}{n}_{s}=n\right\}.$ Consider such sums representing all distinct elements of (A + U) \ U. $(A+U)∖U={wi=∑s=1kni,sas:∑s=1kni,s=nfori=1,2,...,d}.$

We fix j ∈ {1, 2, …, k}. We shall prove that the elements {ui,m = wimaj : i = 1, 2, …, d, m = 1, …, ni,j} are distinct elements of U (if ni,j = 0 there are no elements ui,m.)

Since ni,j ≥ 1 and 1 ≤ mni,j the coefficients of ui,m are non-negative and their sum is at most n − 1 so the elements ui,m have the form of the elements in U and they belong to U. Suppose that ui,m = us,r for distinct pairs (i,m) ≠ (s, r). That means wimaj = wsraj. If m = r then wi = ws, which contradicts the assumption that wiws. If mr we may assume 0 < mr < ni,j. Then

ws = wsraj + raj = wimaj + raj = wi − (mr)ajU because 0 < mr < mni,j so wi − (mr)aj has the form of the elements in U. But this contradicts the assumptions that wsU. So we have at least $\sum _{i=1}^{d}{n}_{i,j}$ distinct elements in U.

This is true for j = 1, 2, …, k. On the other hand $\sum _{j=1}^{k}\left(\sum _{i=1}^{d}{n}_{i,j}\right)=\sum _{i=1}^{d}\left(\sum _{j=1}^{k}{n}_{i,j}\right)=dn.$ Therefore there exists j such that $|U|\ge \sum _{i=1}^{d}{n}_{i,j}\ge \frac{dn}{k}.$ Since |(A + U) \ U| = d we have $|\left(A+U\right)\phantom{\rule{thinmathspace}{0ex}}\mathrm{\setminus }\phantom{\rule{thinmathspace}{0ex}}U|\phantom{\rule{thinmathspace}{0ex}}\le \phantom{\rule{thinmathspace}{0ex}}\left(\frac{k}{n}\right)|U|.$  □

#### Theorem 2.3

Every abelian group is uniformly amenable with the growth function which satisfies $q\left(\frac{k}{n},k+1\right)={C}_{n+k-1}^{k}$ for natural k and n.

#### Proof

Let k and $t=\frac{k}{n}$ be given. Consider a subset A of G with k + 1 elements. By Lemma 2.1 we may assume that A = {0, a1, …, ak}. Let U be as in Lemma 2.2 for the set A. A sequence of the coefficients (n1, n2, …, nk) of a point in U represents an integer point of a simplex cut off from the non-negative cone of the Euclidean space ℝk (e.g. the non-negative quarter of the plane or the non-negative octant of the space) by the hyperplane $\sum _{i=1}^{k}{n}_{i}=n-1.$ There are ${C}_{n+k-1}^{k}$ integer points in this simplex (an easy induction argument) and therefore there are at most ${C}_{n+k-1}^{k}$ elements in U. By Lemma 2.2 we have $|\left(A+U\right)\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\mathrm{\setminus }\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}U|\le \frac{k}{n}|U|\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\text{hence}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}|A+U|\le \left(1+\frac{k}{n}\right)|U|$ as required.  □

#### Remark 2.4

For the other values of t we can choose the smallest n such that $\frac{k}{n} and let $q\left(t,k+1\right)=q\left(\frac{k}{n},k+1\right).$ We believe that the value of q(t,k + 1) in the theorem is the smallest possible. We have not enough evidence to make it a conjecture. We can prove it for k = 2.

#### Lemma 2.5

For every abelian group G (when G has elements of the infinite order or of an arbitrarily high order) the minimal growth function q(t, k) has values $q\left(\frac{2}{n},3\right)={C}_{n+1}^{2}$ (and for every uniformly amenable group G which has elements of the infinite order or of an arbitrarily high order every growth function satisfies $q\left(\frac{2}{n},3\right)\ge {C}_{n+1}^{2}$).

#### Proof

We know by Theorem 2.3 that if G is abelian, there exists a growth function with these values. Let us fix k = 2 and n. We choose an element gG of a sufficiently high order (at least of order 2n4). We choose a1 = g, a2 = n2g and A = {0, a1, a2}. Suppose U is a finite subset of G such that $|A+U|\le \left(1+\frac{2}{n}\right)|U|.$ Since 0 ∈ A we have U ⊂ (A + U) and therefore $|\left(A+U\right)\phantom{\rule{thinmathspace}{0ex}}\mathrm{\setminus }\phantom{\rule{thinmathspace}{0ex}}U|\le \frac{2}{n}|U|.$ We shall prove that |(A + U) \ U| ≥ n + 1 and therefore$|U|\ge {C}_{n+1}^{2}=\frac{n\left(n+1\right)}{2}.$

We partition the group G into cosets with respect to the cyclic subgroup H = < g > generated by the element g (the left cosets H b if G is not abelian) and we partition U into the non-empty pieces Ui contained in different cosets. Then A + Ui is contained in the same coset as Ui. If for every Ui we have $|A+{U}_{i}\right)|>\left(1+\frac{2}{n}\right)|{U}_{i}|,$ then $|\left(A+U\right)|>\left(1+\frac{2}{n}\right)|U|$ which contradicts our assumptions. Therefore for some Ui we have $|\left(A+{U}_{i}\right)|\le \left(1+\frac{2}{n}\right)|{U}_{i}|.$ We shall prove that this implies $|{U}_{i}|\ge {C}_{n+1}^{2}$ and therefore $|U|\ge {C}_{n+1}^{2}$. So we may restrict the argument to one coset and we may assume that G = < g >.

We need to prove that $|U|\ge \frac{n\left(n+1\right)}{2}$ so we may assume that |U|≤n2 − 1. If g is of a finite order, let ord(g) = r ≥ 2n4. Every element of U can be written as u = mg = n1a1 + n2a2 where 0 ≤ n1n2 − 1 and if ord(g) = r then 0 ≤ n2 and m = n1 + n2n2r − 1. So every element of U can be identified with a point (n1, n2) in the plane and different pairs (n1, n2) correspond to different elements of UG. If u = mg then the first coordinate of u is the remainder of m modulo n2.

When we translate U in G we get a different correspondence of the elements of U with the points of the plane and different set of pairs (n1, n2) corresponds to the elements of U.

If u = (n1, n2) ∈ U then a1 + u = (n1 + 1, n2) and a2 + u = (n1, n2 + 1).

Claim. After a suitable translation of U we may assume that U is not a union of two subsets U1 and U2 in the plane in a distance more than $\sqrt{2}$(we say that U is connected).

#### Proof

If subsets U1 and U2 in the plane are in a distance more than$\sqrt{2}$ from each other, then sets A + U1 and A + U2 are disjoint as subsets of the plane but some points in the plane coincide as elements of G. We shall prove that sets A + U1 and A + U2 are disjoint as subsets of G.

Since |U| < n2 not every remainder modulo n2 is equal to the first coordinate of some point in U. If G is infinite we first translate U so that the first coordinate of every point in U is different from n2 − 1. Suppose U = U1U2 as in the claim. Two distinct points in the plane (n1, n2) and (p1, p2) represent the same element of G if p1n1 = n2(n2p2), but this does not happen for the points of the sets A + U1 and A + U2.

If ord(g) = r the same claim requires an additional translation of U. We first translate U so that 0 ∈ U. Since |U| < n2 and r ≥ 2 n4 there must exist a gap of length at least 2n2 between some pair of consecutive values m1, m2 such that m1g, m2gU and m2m1 ≥ 2n2. After another translation we may assume that the gap is at the end so mgU for m > r − 2n2. After another suitable translation by less than n2 − 1 we may assume that the first coordinate of every point in U is different from n2 − 1 and mgU for mrn2. Suppose U = U1U2 as in the claim. Now two distinct points in the plane (n1, n2) and (p1, p2) represent the same element of G if either p1n1 = n2(n2p2) or p1 + n2p2n1n2n2 is a multiple of r, but none of these may happen for the points of the sets A + U1 and A + U2.

Since A + U1 and A + U2 are disjoint and $|\left(A+U\right)\phantom{\rule{thinmathspace}{0ex}}\mathrm{\setminus }\phantom{\rule{thinmathspace}{0ex}}U|\le \frac{2}{n}|U|$ we must have $|\left(A+{U}_{i}\right)\phantom{\rule{thinmathspace}{0ex}}\mathrm{\setminus }\phantom{\rule{thinmathspace}{0ex}}{U}_{i}|\le \frac{2}{n}|{U}_{i}|$ for i = 1 or for i = 2 and we may restrict the discussion to this smaller set Ui and prove that $|{U}_{i}|\ge {C}_{n+1}^{2}.$ So we may assume that U is connected.  □

We assume that U is connected. We make another translation, if necessary, to get min{n1 : (∃n2)(n1, n2) ∈ U} = 0 and min{n2 : (∃ n1)(n1, n2) ∈ U} = 0. This does not change the shape of U, it is still connected.

Let (a, b) be a point in U such that a + b is maximal. Since U is connected every vertical line n1 = c with 0 < c < a meets U and every horizontal line n2 = d with 0 < d < b meets U.

If u1 = (n1, n2) ∈ U is the rightmost element of U in its row then u1 + a1 = (n1 + 1, n2) ∈ (A + U) \ U. We call u1 + a1 a horizontal boundary point of U. If u2 = (m1, m2) ∈ U is the top element of U in its column then u2 + a2 = (m1, m2 + 1) ∈ (A + U) \ U. We call u2+a2 a vertical boundary point of U.

Observe that if u = (n1, n2)∈ U then, by the connectivity of U, there are at least n1 + 1 vertical boundary points in (A + U) \ U and at least n2 + 1 horizontal boundary points in (A + U) \ U. We need only n + 1 points therefore we may assume that n1 < n and n2 < n. If a1 + u or a2 + u is a boundary point, then its coordinates (m1, m2) still satisfy m1 < n2 and m1 + n2m2 is smaller than the order of g. It follows that distinct pairs of coordinates define distinct elements of G also for the boundary points.

We shall prove that each horizontal boundary point (n1 + 1, n2) with n2b is distinct from any vertical boundary point (m1, m2 + 1) with m1a.

Suppose (n1 + 1, n2) = (m1, m2 + 1) is a horizontal and a vertical boundary point. If n2 = b then n1 = a and m1 = n1 + 1 = a + 1. If m1 = a then m2 = b and n2 = m2 + 1 = b + 1. If n2 < b and m1 < a then there are no points of U on the vertical line above this point and on the horizontal line to the right of this point and the top right corner U1 = {(c1, c2) ∈ U : c1 > m1, c2 > n2} splits off, U is not connected.

This means that there are at least a + b + 2 points in (A + U) \ U.

Let d = |(A + U) \ U| ≥ a + b + 2. The set U lies in the triangle {(n1, n2) : 0 ≤ n1, 0 ≤ n2, n1 + n2a + b}, so $\frac{\left(a+b+1\right)\left(a+b+2\right)|}{2}\ge |U|$ and by our assumptions $|U|\ge \frac{n}{2}d\ge \frac{n\left(a+b+2\right)}{2}.$ It follows that a + b + 1 ≥ n and |(A + U) \ U| = da + b + 2 ≥ n + 1.  □

## 3 Some linear uniformly amenable groups

Let R be a commutative ring with a unit 1.

We consider the following group of matrices over R $M={A=1xz01y001:x,y,z∈R}.$

An element of M can be identified with a triple (x, y, z) of elements of R. Then the composition (the product) of the triples is defined by (x1, y1, z1)(x, y, z) = (x1 + x, y1 + y, z1 + z + x1y).

Later we shall also perform the addition of the triples as elements of RRR.

The elements (0,0, z) lie in the center of M and form an abelian normal subgroup C of M. The quotient M/C is abelian so the group M is solvable and it is known that solvable groups are uniformly amenable. We want to find a growth function q(t, k) for this group, which will also give a direct proof of the fact, that M is uniformly amenable.

This example was inspired by a paper [10] by J. Wysoczański. He considered a group G which is a direct sum of groups M over all prime fields Fp = ℤ/ pℤ. If we take for the ring R the direct sum of the fields Fp and we adjoin a unit - the element with each coordinate equal to 1 in the corresponding field we get a ring R1 with a unit. The group G is a subgroup of the group M over R1.

We now consider the group M over an arbitrary commutative ring R with a unit. Let A = {a0, a1, …, ak−1} ⊂ M where ai = (−xi, −yi, −zi) for i = 0, 1, …, k − 1.

The minus sign is for the convenience of the subsequent description where the negative coefficients play a special role.

We want to estimate the number |AU|. By Lemma 2.1 we may assume that a0 = (0, 0, 0) is the unit of the group M. For a fixed n ∈ ℕ we define UnM, $Un={u=(u1,u2,u3):u1=Σitixi,u2=Σitiyi,u3=Σitizi+Σi,jti,jxiyj}$

where i, j ∈ {1, 2, …, k − 1}, ti ∈ {0, 1, …, n − 1}, ti,j ∈ {0, 1, …, n2 − 1}.

An element of Un is determined by (k − 1)2 + (k − 1) integer coefficients. The set J of indices of these coefficients consists of integers and pairs of integers J = {i : 1 ≤ ik − 1, (i, j) : 1 ≤ i, jk − 1}.

We shall denote an element uU by u = (tα)αJ. Then, by the definition of the composition law in M, w = asu has a similar form, w = (fα), where fs = ts − 1, fs,j = ts,jtj and fα = tα for other αJ. In particular fα may be negative if α = s or α = (s, j) and fs ≥ − 1 and fs,j ≥ 1 − n.

#### Lemma 3.1

For any s ∈ {1, 2, …, k − 1} we have $|{a}_{s}{U}_{n}\phantom{\rule{thinmathspace}{0ex}}\mathrm{\setminus }\phantom{\rule{thinmathspace}{0ex}}{U}_{n}|<\left(\frac{{2}^{k}}{n}\right)|{U}_{n}|.$

#### Proof

We fix an integer s ∈ {1, 2, …, k − 1}. We consider elements of asUn \ Un and for each such element we choose one representative w = (fα). For any non-empty subset of indices I ⊂ {s,(s, 1), (s, 2), …, (s, k − 1)} we consider the set BI of all chosen representatives w = (fα) of the elements in asUn \ Un which have the negative coefficients fα exactly for αI. Suppose that BI = {w1, w2, wd}.

Let eI = (b1, b2, b3) ∈ RRR where b1 = xs, b2 = ys, b3 = zs + n(s, j) ∈ Ixsyj if sI and b1 = 0, b2 = 0, b3 = n(s, j)∈Ixsyj if sI.

We shall prove that the elements wi + meI, i = 1, 2, …, d, m = 1, 2, …,n belong to Un and are distinct. Only the coefficients fα, αI of w change. If sI then fs = −1 and it increases by m when we add meI where 1mn so fs falls into the proper range for the elements in Un. If (s, j) ∈ I then 1nfs, j ≤ −1 and fs, j increases by mn so it also falls into the proper range for the elements in Un.

Suppose that wi + meI = wj + reI for different pairs (i,m) and (j, r). If m = r then wi = wj which contradicts the assumptions. If mr we may assume that m > r. Then wj = wj + reIreI = wi + (mr)eIUn which contradicts our assumptions. Therefore |Un| ≥ nd and $|{B}_{I}|\le \frac{1}{n}|{U}_{n}|.$ There are (2k − 1) non-empty subsets of {s, (s, 1), (s, 2), …, (s, k − 1)} and each element of asUn \ Un lies in one of them so |asUn \ Un| < $\left(\frac{{2}^{k}}{n}\right)|{U}_{n}|.$  □

#### Corollary 3.2

For every commutative ring R with unit the group M is uniformly amenable with a growth function $q(ϵ,k)=(1+(k−1)(2k)ϵ)2(k−1)2+k−1$

#### Proof

For a given k and ϵ choose $n=\left[\frac{\left(k-1\right){2}^{k}}{ϵ}\right]+1.\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\text{Then}\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}\frac{\left(k-1\right){2}^{k}}{ϵ} Let A = {a0 = (0, 0, 0), a1, …, ak−1} ⊂ M. We choose the set Un as in the previous lemma. Then |Un| ≤ n2(k − 1)2+k − 1$\left(1+\frac{\left(k-1\right){2}^{k}}{ϵ}{\right)}^{2\left(k-1{\right)}^{2}+k-1}=q\left(ϵ,k\right).$ It suffices to prove that |AUn| < (1 + ϵ)|Un|. We have a0Un = Un and by the previous lemma $|A{U}_{n}|\le |{U}_{n}|+\left(k-1\right)\left(\frac{{2}^{k}}{n}\right)|{U}_{n}|<\left(1+ϵ\right)|{U}_{n}|.$  □

#### Remark 3.3

Many of the sets BI in the proof of the previous lemma may have very small contribution to the ″boundary″ AUn \ Un. In particular if different sets of coefficients (tα) represent different elements of Un then for n large |AUn \ Un| is of order $\frac{{k}^{2}}{n}|{U}_{n}|.$ Indeed if a set I in the proof of Lemma 3.1 has only one element then |BI| is equal about n2(k − 1)2+k−2. There are k such sets for each s = 1, 2, …, k − 1. If I has more than one element then |BI| is at least n times smaller therefore for n large |A Un \ Un| is equal about k2n2(k − 1)2+k−2. Moreover |Un| = n2(k − 1)2+k − 1 therefore |A Un \ Un| is equal about $\frac{{k}^{2}}{n}|{U}_{n}|.$ In this case (when n is large and ais areindependent″) it suffices to have $n>\frac{{k}^{2}}{ϵ}and\phantom{\rule{thinmathspace}{0ex}}\phantom{\rule{thinmathspace}{0ex}}|{U}_{n}|=\left(\frac{{k}^{2}}{ϵ}{\right)}^{2\left(k-1{\right)}^{2}+k-1}.$ Probably this is the correct size of q(ϵ, k) but we cannot prove it.

## Acknowledgement

We would like to thank Marek Bożejko and Jakub Gismatulin for many helpful remarks.

## References

• [1]

Keller G., Amenable groups and varieties of groups, Illinois J.Math., 1972, 16, 257-268. Google Scholar

• [2]

Kesten P., Full Banach mean values on countable groups, Math. Scand., 1959, 7, 146-156.

• [3]

Kaimanovich V. A., The spectral measure of transition operator and harmonic functions connected with the random walks on discrete groups, LOMI, Leningrad, 1980. Google Scholar

• [4]

Kaimanovich V. A., Vershik A. M., Random Walks on Discrete Groups: Boundary and Entropy, The Annals of Probability, 1983, 11, 457-490.

• [5]

Bożejko M., Uniformly Amenable Discrete Groups, Math. Ann., 1980, 51, 1-6. Google Scholar

• [6]

Drutu C., Sapir M., Tree-graded spaces and asymptotic cones of groups, Topology, 2005, 44, 959-1058.

• [7]

Bożejko M., Pełczyński, A., An analogue in commutative harmonic analysis of the uniform bounded approximation property of Banach space, Seminaire D’Analyse Fonctionnel, 1978-79, Expose 6 No. IX. Google Scholar

• [8]

Bourgain J., A remark on entropy of abelian groups and the invariant uniform approximation property, Studia Math., 1987, 86, 79-84.

• [9]

Wojtaszczyk P., Banach spaces for analysts, Cambridge UP, 1991. Google Scholar

• [10]

Wysoczański J., On uniformly amenable groups, Proc. Amer. Math. Soc., 1988, 102, 933–938.

Accepted: 2016-12-13

Published Online: 2017-04-26

Citation Information: Open Mathematics, Volume 15, Issue 1, Pages 502–507, ISSN (Online) 2391-5455,

Export Citation


text:
# IOTA Stronghold: Beta Release

Announcements Mar 19, 2021

Stronghold is an open-source software library that was originally built to protect IOTA Seeds, but can be used to protect any digital secret. It is a secure database for working with cryptography, which ensures that secrets (like private keys) are never revealed. It provides its own peer-to-peer communication layer, so that different apps can securely communicate using the state-of-the-art Noise Protocol over libp2p. Stronghold will form a secure base for the new IOTA Firefly wallet and will be integrated into IOTA Identity.

We dubbed this Beta release “Boden Fortress”, after the fortification in Northern Sweden set up to protect the country and its transport of the “coin of industry” - iron ore - during the world wars in the first half of the 20th Century. Its utility proven, it found use continuing throughout the Cold War. Like Stronghold’s Beta release is intended to be, the Boden Fortress was a temporary solution destined to be short lived and dismantled after it’s service period. That said, the Boden Fortress was in use for almost a hundred years. We are pretty sure that Stronghold’s Beta will be much, much shorter than that.

Today, three months after the Alpha release, we are happy to announce the Stronghold Beta. This version offers guarantees about the API, client logic and snapshot format - which will only change if security vulnerabilities are found. Being at this stage qualifies Stronghold for a full external audit, the completion of which will be a milestone that Stronghold needs to reach for the publication of its stable 1.0.

If you need a refresher about how Stronghold works, our resident Meme Lord Navin from the IOTA Foundation Board made a wonderful little diagram explaining what Strongholds will (and will not) do:

Generally speaking, most people won’t ever even need to know that they have a Stronghold. Its use should be invisible, much like how visitors to common websites don’t need to know which database is used on the backend. Of course, if websites were required to disclose how they were securing our user-data, then we might actually have greater faith in their ability to protect us.

Hopefully, at some point in the not so distant future, websites, apps and even operating systems will begin to recognize the strength and utility of approaches like IOTA Identity: where we control and secure our own data; where we decide what we share; where we choose with whom we share it; where we are empowered to revoke access when it suits us.

From a systems perspective, what we face today in software is that every application feels like it should be able to use any secrets it thinks it needs, and there are rarely strong guarantees that these applications protect the secrets properly. We want the industry in general to realize that this is a highly insecure practice, and the novel approach taken by Stronghold is not only obviously more secure, but an architectural pattern worth embracing. It’s really quite easy: you can’t leak secrets you don’t know about.

## Shut up and take my money

It's never a good thing to be too confident, but at the same time we have to gain your trust by asking you to verify our faith in Stronghold. This is why, alongside the "Attack-a-thon", we are going to be running a Capture the Flag (CTF) challenge until Chrysalis (April 21st, 2021).

Somewhere, hidden in this blog page you can discover a flag (clue) that will help you to find a Stronghold Snapshot. This snapshot was created using the Stronghold CLI at git revision 93d1dfa12235f4c769a714a1cf39a4222b4ecc27. Once you find it, the rest of the CTF is 100% self-contained in that snapshot. In other words, there are no external resources available anywhere to help you, so really, do not waste your time trying to break into any other systems.

In the snapshot's store, there is a flag to prove you got inside. The vault, however, contains a current IOTA Mainnet seed in a secret vault/path that is another flag. This seed holds 3.78 GIOTA. At the time of this writing, that has a value of  ~5000 USD. The only prize is the Seed.

If you find a flag, please visit the Stronghold Discussion at GitHub for instructions on being added to the leaderboard. Good luck.

## Whats Next

Over the next several months, we will be preparing tutorials, examples, documentation and specifications as well as integrating with other IOTA Foundation projects. During this time, we will be enhancing the client with a flexible approach to Stronghold Procedural Cryptography, releasing a "version updater" for enabling the seamless upgrade of a snapshot to a new Stronghold version, and validating the communication system with a native desktop application. Finally, Stronghold will undergo a full audit and then will be marked as Stable.

## Technical Notes About the Release

Stronghold is composed of a number of libraries that all work together. These libraries have been audited vertically in the context of an external audit of Firefly and reviewed by a number of IF Rust Engineers for quality and security. These have qualified it for beta release, however before we mark Stronghold as stable, there will be a future horizontal audit of the entire codebase.

What follows is a high-level description of each one, followed by its internal release status and a link to its changelog.

Client
The Client is the only interface to Stronghold that we can recommend using. It serves as an abstraction layer to the underlying engine and communication libraries, which guarantees that even if the internal codebase changes, your interface to Stronghold will continue to work.

Status: Beta
CHANGELOG

Vault
The vault is now write-and-use-but-never-read. This means that there is no method by which the client can ever read the secrets stored in the system, and provides solid assurance that Stronghold is as secure as possible. When a secret is retrieved from a record in the vault, it is passed to the runtime, which decrypts into an advanced memory allocator that guards the secret while in use. This is why we consider the vault to be “hardened”.

Status: Beta
CHANGELOG

Store
The store is a read-write key:value storage service that, while encrypted in the snapshot, does not enjoy the same memory protection used by the vault. This is because any data that can be returned to the client cannot be classified as “truly secret”. While it is encrypted at rest, it is not encrypted in memory and as such we classify it as “private and secure” but not “hardened”.

Status: Beta
CHANGELOG

Runtime
Perhaps the largest single change since the Alpha release is the new runtime, which is entirely based on libsodium-sys and guaranteed to work on all platforms. It still protects exposed secrets in memory using classical guard pages and canaries while cryptographic operations are being undertaken. Additionally, we now provide an internal Guarded Vector type, that allows Stronghold to protect records when in use and automatically zeroizes them.

Status: Beta
CHANGELOG

Snapshot
The snapshot crate serves to decrypt the persistence file and place the data in the vault and store. It also encrypts the vault & store to update the persistence file.

Status: Beta
CHANGELOG

Communication
The communication crate is using the libp2p system with the noise protocol, which enables permissioned use of remote strongholds for creating services like remote signing and multi-factor authorization. It is not in active use with Chrysalis, but will be used by the Wallet and Identity at a later date.

Status: Alpha
CHANGELOG

crypto.rs
While not an internal dependency of Stronghold, this library does provide cryptographic primitives for Stronghold (and any other IOTA libraries that need to use Cryptography).

Status: Beta
CHANGELOG

### Tags

#### IOTA Foundation

Among with Daniel Thompson-Yvetot

Official posts from the IOTA Foundation, and migrated posts from old platforms.

format: plain


text:
# Convert CSV to Excel – How to open CSV and save as Excel

(1 votes, average: 5.00 out of 5)

CSV files are commonplace nowadays. Hence knowing how to convert CSV to Excel is a useful skill. CSV files are especially useful when wanting to save a table worth of data in a simple to read format. CSVs are also easy files to create and read from – as they are basically text files with a .csv file extension. That means they easily open in Wordpad, Notepad, Word and virtually any other text editor.

CSV (Comma-separated values) – in computing these are text files that store tabular data (numbers and text in columns):

• Each row represent a single record
• Each column represents a certain property
• Each “cell“, or in other words columns within a row, are separated by a certain delimiter. Usually a comma , character (but not only!)
• Usually the first row is the header – contains names for each column

Today I want to show how you can quickly convert a CSV file into an Excel XLSX file. I will base this tutorial on the following example of a CSV file:

## Open the file in Excel

Simply double click on the file or if needed right-click and Open with the file in Microsoft Excel. The file should open showing only a single Worksheet like shown below:

If columns in a CSV are separated by your default Windows list separator the columns will be separated automatically without needing to proceed further. Where to find you default Windows locale list separator? Control Panel->Region and Language->Additional Settings->List Separator. In my case it was a ;

## Select first column and proceed to Text to Columns

Select the entire first column where all your data should be located. Next click on the Text to Columns button in the DATA ribbon tab:

## Proceed according to Wizard instructions

This is the hard part. Text to Columns need additional information on the delimiter and format of your columns.

### Delimited or Fixed width?

CSV files are usually delimited using a specific character (like a comma or semicolon), in this case select Delimited. Sometimes however columns are fixed width, separated by spaces, in this case select Fixed width. Next click Next to proceed.

### Select delimiter

Assuming your columns are separated with a specific delimiter you need to provide this delimiter in the Wizard. Look at the Data preview to make sure your columns will be separated correctly. When finished proceed with Next

The last step is to format your columns if needed. If your columns represent Dates or you want to pull a column containing numbers/dates as text instead – be sure to format it appropriately. Usually, however, you are fine with hitting Finish:

If you have proceeded according to the steps above you should have a neatly formatted spreadsheet like the one below.

One last thing as Steve Jobs used to say… Remember to save the file as an Excel XSLX (or XLSB or similar) file:

## Convert multiple CSV to Excel with VBA

If you have multiple CSVs you want to convert or pull into an Excel file the above approach may be a big burden. So lets use some VBA macros to help.

### Import entire CSV

The below is take straight from my Read file in VBA blog post. This pulls a single file into the destRng Excel range.

Dim ws as Worksheet, destRng as Range, fileName as String
Set destRng = Range("A1")
Set ws = ActiveSheet
fileName = "C:\text.csv" 'Replace with file name
With ws.QueryTables.Add(Connection:= "TEXT;" & fileName & "", Destination:=destRng)
.FieldNames = True
.RowNumbers = False
.PreserveFormatting = True
.RefreshOnFileOpen = False
.RefreshStyle = xlInsertDeleteCells
.SaveData = True
.RefreshPeriod = 0
.TextFilePromptOnRefresh = False
.TextFilePlatform = 852
.TextFileStartRow = 1
.TextFileParseType = xlDelimited
.TextFileTextQualifier = xlTextQualifierDoubleQuote
'Select your delimiter - selected below for Comma
.TextFileConsecutiveDelimiter = False
.TextFileTabDelimiter = False
.TextFileSemicolonDelimiter = False
.TextFileSpaceDelimiter = False
.TextFileTrailingMinusNumbers = True
'This will refresh the query
End With

### Import selected CSV rows

Now a more interesting and complex scenario – let us assume we want to import just some rows of our CSV. Fortunately Excel (as well as Access) support SQL queries. We can therefore do a simple SELECT query to upload all records or add some filtering (using WHERE clause), grouping (using GROUP BY clause) and etc.

'Assuming file looks like this. File path: C:\test.csv
'"Col1", "Col2", "Col3"
'1     , 2     , 3
'11    , 12    , 1
'2     , 5     , 6

strcon = "Provider=Microsoft.Jet.OLEDB.4.0;Data Source=C:\;" _
& "Extended Properties=""text;HDR=Yes;FMT=Delimited"";"
strSQL = "SELECT * FROM test.csv WHERE Col1 > 10"
rs.Open strSQL, strcon, 3, 3
rs.MoveFirst
Do
col1 = rs("Col1")
col2 = rs("Col2")
col3 = rs("Col3")
rs.MoveNext
Loop Until rs.EOF

The above will only pull the second row as Col1 is > 10.

## Convert CSV to Excel tips

CSV files are usually used when a file contains a large amount of data. Excel tends to bloat pretty quickly although it compresses the data pretty well. Nevertheless you might find yourself struggling with Excel performance or even experiencing an Excel crash. What to do? Save the file as an XLSB – read more here.


text:
# How to continue thick underline beyond text?

Here's my code:

\documentclass[12pt]{article}
\usepackage{soul}
\begin{document}
\setul{}{2pt}
\ul{\Huge\textbf{Some text}}
\underline{\Huge\textbf{Some text \hspace{1in}}}
\ul{\Huge\textbf{Some text \hspace{1in}}} % This line causes error
\end{document}

The command \underline{\Huge\textbf{Some text \hspace{1in}}} produces the result

I want the underline to be thicker though, so I tried using the soul package, setting the thickness, and then \ul{Some text}

This gives me the desired underline thickness

The problem occurs when I try to combine the two to get a thick line extending beyond the text. The command \ul{\Huge\textbf{Some text \hspace{1in}}} produces an error, "Missing number, treated as zero."

Any ideas why or how to fix it? Or better ways of underlining text with a bold line that extends an arbitrary distance beyond the text?

• Welcome to TeX.SX! Please help us to help you and add a minimal working example (MWE) that illustrates your problem. It will be much easier for us to reproduce your situation and find out what the issue is when we see compilable code, starting with \documentclass{...} and ending with \end{document}. – user31729 Apr 12 '15 at 0:03
• Try \protect\hspace*{1in} – user31729 Apr 12 '15 at 0:08
• Doing \ul{\Huge\textbf{Some text \protect\hspace{1in}}} fixes the error but cuts the underline off at the end of the text... produces same result as second image above – Philip Apr 12 '15 at 0:14
• \ul{\Huge\textbf{\mbox{Some text \hspace{1in}}}} – user31729 Apr 12 '15 at 0:18
• @ChristianHupfer I'm jealous. You knew the answer, I had to look it up in the package manual. :( – R. Schumacher Apr 12 '15 at 0:20

You have to read the fine print in the soul manual http://texdoc.net/texmf-dist/doc/latex/soul/soul.pdf You have to protect with \mbox{}.

\documentclass[10pt,letterpaper]{article}
\usepackage{soul}
\begin{document}
\ul{\Huge\textbf{Some text\mbox{\hspace{1in}}}}
\end{document}

• Great, that worked for me, thanks. I read that doc but didn't realize that line of the table applied. – Philip Apr 12 '15 at 0:22

Without loading any other packages, here's a command that will accomplish this using a rule.

\documentclass{article}
\makeatletter
\newlength\ae@tmp@length
\newcommand\aeunderline[2][]{%%
\settowidth\ae@tmp@length{#2}%%
\makebox[0pt][r]{#2}%%
\hspace{-\ae@tmp@length}%%
\rule[\dimexpr-0.25ex-4pt]{\dimexpr\ae@tmp@length+#1+0pt\relax}{4pt}}

\makeatother

\pagestyle{empty}
\begin{document}

\aeunderline[2in]{Hello World} and this is what follows.

\end{document}

## plain TeX based

A solution with underline based on plain TeX means only:

\documentclass{article}
\begin{document}
\leavevmode
\vtop{
\Huge
\hbox{\textbf{Some text \hspace{1in}}}
\kern.5ex % space between text and line
\hrule height 2.5pt % rule thickness
}
\end{document}

## TikZ based

The following example uses TikZ, which offers more options regarding the line style. For example, this version shows round line caps:

\documentclass{article}
\usepackage{tikz}
\begin{document}
{\Huge
\tikz[
baseline=(text.base),
node font=\bfseries,
inner sep=0pt,
line width=2.5pt,
line cap=round, % also decorations, ...
]
\draw
node (text) {Some text}
(text.south east) ++(1in, -.5ex) coordinate (tmp)
-- (text.south west |- tmp)
;}
\end{document}

Just for completeness of the answers to this question, if you are using luatex, there is an unfinished package that underlines: luauline. (It is usable, it just isn't ready enough for CTAN since it has no documentation and needs a few performance improvements.)

If you download this package and place it in your local TeX tree, you can load it and produce the desired result with the following:

\documentclass[12pt]{article}
\usepackage{luauline}
\setluaunderlineheight{2pt}  % set thickness of the underline
\begin{document}
\uline{\Huge\textbf{Some text\hspace*{1in}}}
\end{document}


text:
# Error in .Internal(as.vector(x, "symbol")) : 'x' is missing

3 posts / 0 new
Offline
Joined: 10/19/2009 - 15:38
Error in .Internal(as.vector(x, "symbol")) : 'x' is missing

maybe it is too late at night, but am befuddled by this error message:

> model1 <- mxModel(model1,
+ mxAlgebra(name="fvalMZ", expression = weight * (MZ@data@observed - MZ$zpreMZ) * + (MZ@data@observed - MZ$zpreMZ)))
Error in .Internal(as.vector(x, "symbol")) : 'x' is missing

full code attached

AttachmentSize
1.15 KB
Offline
Joined: 07/31/2009 - 15:24
Oops, my apologies. There was

Oops, my apologies. There was an error in our error handling! The error message should have been:

Unknown matrix operator or function '@' in mxAlgebra(name = "fvalMZ", expression = weight * (MZ@data@observed - MZ$zpreMZ) * (MZ@data@observed - MZ$zpreMZ))

There are two things going on here: the '@' operator is not allowed inside mxAlgebra() expressions. Inside a mxAlgebra(), it is legal to reference any MxMatrix or MxAlgebra by name, along with any combination of supported matrix operators or functions (see list). We also allow numeric literals and the names of free parameters in an MxAlgebra expression, but those are automagically translated into 1 x 1 matrices.

I think the more useful piece of advice is that if you'd like to evaluate an algebra that is based on data, the trick we use for now is to duplicate the contents of the data and place it inside a MxMatrix with an arbitrary name, like "matrixData" or something, with no free parameters.

I think you want to replace the '^' operator with the '%^%' operator. The former requires that the two arguments have equal dimensions, and the later does not. Thanks to R's misguided operator overloading, the '^' operator performs matrix exponentiation when both arguments are matrices, but it performs kronecker exponentiation when the second argument is a scalar value. Since in OpenMx everything is a matrix, you need to use the kronecker exponent to have the desired effect.

Offline
Joined: 10/19/2009 - 15:38
muchas gracias!

muchas gracias!


text:
# Convergence of the Forward-Backward Algorithm: Beyond the Worst Case with the Help of Geometry

We provide a comprehensive study of the convergence of forward-backward algorithm under suitable geometric conditions leading to fast rates. We present several new results and collect in a unified view a variety of results scattered in the literature, often providing simplified proofs. Novel contributions include the analysis of infinite dimensional convex minimization problems, allowing the case where minimizers might not exist. Further, we analyze the relation between different geometric conditions, and discuss novel connections with a priori conditions in linear inverse problems, including source conditions, restricted isometry properties and partial smoothness.

## Authors

• 2 publications
• 70 publications
• 10 publications
05/01/2016

### Further properties of the forward-backward envelope with applications to difference-of-convex programming

In this paper, we further study the forward-backward envelope first intr...
03/19/2021

### Forward and Backward Bellman equations improve the efficiency of EM algorithm for DEC-POMDP

Decentralized partially observable Markov decision process (DEC-POMDP) m...
05/28/2020

### Variational regularisation for inverse problems with imperfect forward operators and general noise models

We study variational regularisation methods for inverse problems with im...
12/31/2013

### Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint

We consider forward-backward greedy algorithms for solving sparse featur...
12/15/2019

### Symplectic Runge-Kutta discretization of a regularized forward-backward sweep iteration for optimal control problems

Li, Chen, Tai E. (J. Machine Learning Research, 2018) have proposed ...
09/19/2018

### Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation

The Rapidly-exploring Random Tree (RRT) algorithm has been one of the mo...
02/14/2019

### Geometry of Arimoto Algorithm

This paper aims to reveal information geometric structure of Arimoto alg...
##### This week in AI

Get the week's most popular data science and artificial intelligence research sent straight to your inbox every Saturday.

## 1 Introduction

Splitting algorithms based on first order descent methods are widely used to solve high dimensional convex optimization problems in signal and image processing [26], compressed sensing [30]

, and machine learning

[68]. While an advantage of these methods is their simplicity and complexity independent of the dimension of the problem, a drawback is their convergence rates which are known to be slow, in the worst case. For instance, the gradient method applied to a smooth convex function converges in values as [29, 77]. We refer to these results as worst case since no particular assumption is made aside from existence of a solution. Clearly this allows for convex functions with wild behaviors around the minimizers [19], behaviors that might hardly appear in practice. It is then natural to ask whether improved rates can be attained under further regularity assumptions.

Strong convexity is one such assumption and indeed it is known to guarantee linear convergence rates [43, 78]. In practice, strong convexity is too restrictive and one would wish to relax it, while retaining fast rates. In this paper, we are consider geometric conditions that, roughly speaking, describe convex functions that behave like

 \rm dist\,p(⋅,\rm argmin\,f), (1)

for some and on some subset which is typically a neighborhood of the minimizers and/or a sub-level set. The intuition behind this kind of assumptions is clear: the bigger is , the more the function is “flat” around its minimizers, which in turns means that a gradient descent algorithm shall converge slowly. The idea of exploiting geometric conditions to derive convergence rates has a long history dating back to [73, 76], see the literature review in Section 2.3. Recently, there has been a renewed interest, since in practice splitting methods can have fast convergence rates. Plenty of similar convergence rates results have been derived under different yet related geometrical properties, see Section 3.1.

The goal of this paper is to provide a comprehensive study of the convergence rates of forward-backward algorithm for convex minimization problem geometric conditions such as (1). We collect in a unified view a variety of results scattered in the literature, and derive several novel results along the way. After reviewing basic (worst-case) convergence results for the forward-backward algorithm, we recall and connect different geometric conditions. In particular, we study the conditioning and Łojasiewicz properties, and provide a sum rule for conditioned functions. The central part of our study is devoted to exploiting the -Łojasiewicz property to study the convergence of the forward-backward algorithm and a broader class of first-order descent methods. We show that the convergence is finite if , superlinear if , linear if and sublinear if . We further show that -conditioning is essentially equivalent to the linear convergence of the forward-backward algorithm. Then, we consider the case of convex functions being bounded from below but with no minimizers. Indeed, we show that in this case the -Łojasiewicz property with provides sharp sublinear rates for the values, from to .

Our setting allows to consider infinite dimensional problems and in particular linear inverse problems with convex regularizers. Indeed, an observation that motivated out study is that many practical optimization problems are often derived from estimation problems, such as inverse problems, defined by suitable modeling assumptions. It is then natural to ask if these assumptions have a geometric interpretations in the sense of condition (

1). This is indeed the case and we provide two main examples. First, we show that classical Hölder source conditions in inverse problems [40] correspond to the -Lojasiewicz property, with , on some dense affine subspace. Second, we consider sparse regularized inverse problems for which we observe that the restricted injectivity condition [24], which is key for exact recovery, induces a

-conditioning of the problem over a cone of sparse vectors. More generally, we consider inverse problems with partially smooth regularizing functions

[46], and show that the restricted injectivity condition induces a -conditioning of the problem over an identifiable manifold. Studying the above connections required considering geometric conditions like (1) on general subsets , rather than sublevel sets as typically done in the literature.

The rest of the paper is organized as follows. We set the notation, introduce the forward-backward algorithm and discuss worst-case convergence in Section 2, as well as related results in Subsection 2.3. In Section 3, we define and connect different the geometric conditions: -conditioning, -metric subregularity, and -Łojasiewicz property. This section contains in addition examples, and a new sum rule for -conditioned functions. Convergence rates of the forward-backward algorithm are in Section 4. Section 5 is devoted to discussing the special case of linear inverse problems.

## 2 The forward-backward algorithm: notation and background

### 2.1 Notation and basic definitions

We recall a few classic notions and introduce some notation. Throughout the paper is a Hilbert space. Let and . and denote respectively the open and closed balls of radius centered at . and are used to denote and . The distance of from a set is , and stands for , with the convention that . If is closed and convex, is the projection of onto , and and respectively denote the relative interior and the strong relative interior of [11]. Given a bounded self-adjoint linear operator , we denote by

the set of eigenvalues of

[40], and , are defined as and , respectively. Let be the class of convex, lower semi-continuous, and proper functions from to . For and , denotes the (Fenchel) subdifferential of at [11]. We also introduce the following notation for the sublevel sets of :

 (∀r∈[0,+∞]) Sf(r):={x∈X | f(x)−inff

The following assumption will be made throughout this paper.

###### Assumption 2.1.

is a Hilbert space, , and is differentiable and convex, with -Lipschitz continuous gradient for some and we set

Splitting methods, such as the forward-backward algorithm, are extremely popular to minimize an objective function as in Assumption 2.1. To have an implementable procedure, we implicitly assume that the proximal operator of can be easily computed (see e.g. [26]):

 (∀λ>0)(∀x∈X)\rm proxλg(x)=\rm argmin\,u∈X{g(u)+12λ∥u−x∥2}. (2)

If Assumption 2.1 is in force, we introduce the Forward-Backward (FB) map for :

 Tλ:x∈X⟼Tλx:=\rm proxλg(x−λ∇h(x))∈X, (3)

so that the FB algorithm can be simply written as .

### 2.2 The Forward-Backward algorithm: worst-case analysis

The following theorem collects known results about the convergence of the FB algorithm. This is a “worst-case” analysis, in the sense that it holds for every satisfying Assumption 2.1. The main goal of Section 4 is to show how these results can be improved taking into account the geometry of at its infimum.

###### Theorem 2.2 (Forward-Backward - convex case).

Suppose that Assumption 2.1 is in force, and let be generated by the FB algorithm. Then:

1. (Descent property) The sequence is decreasing, and converges to .

2. (Féjer property) For all , the sequence is decreasing.

3. (Boundedness) The sequence is bounded if and only if is nonempty.

Suppose in addition that is bounded from below. Then

1. (Subgradients convergence) The sequence converges decreasingly to zero, with

Moreover, if , we have:

1. (Weak convergence) The sequence converges weakly to a minimizer of .

2. (Global rates for function values) For all ,

 f(xn)−inff≤C\rm dist\,(x0,% \rm argmin\,f)22λn, with C={1 if λ≤L−1,1+2(λL−1)(2−λL)−1 otherwise.
3. (Asymptotic rates for function values) When ,

Theorem 2.2 collects various convergence results on the FB algorithm. Item i appears in [77, Theorem 3.12] (see also [44]). Item ii is a consequence of the nonexpansiveness of the FB map (see (3)) [56, Lemma 3.2]. Item iii, which is a consequence of Opial’s Lemma [72, Lem. 5.2], can be found in [77, Theorem 3.12]. Item 1 follows from Lemma A.5.ii in the Annex. Item 1 is also a consequence of Opial’s Lemma, see [56, Proposition 3.1]. Items 2 and 3 are proved in [29, Theorem 3] (see also [16, Proposition 2] and [12, Theorem 3.1]).

###### Remark 2.3 (Optimal results in the worst-case).

The convergence results in Theorem 2.2 are optimal, in the sense that we explain below. First, the iterates may not converge strongly: see [8, 44] for a counterexample in . Even in finite dimension, no sublinear rates should be expected for the iterates. To see this, apply the proximal algorithm to the function , whose unique minimizer is zero. When , then (see e.g. the discussion following [69, Proposition 2.5]):

 (∃C>0)(∀n∈N)∥xn∥≥Cn−1/(p−2),wherelimp→+∞1p−2=0. (4)

The estimate (4) provides also a lower bound for the rates on the objective values:

 f(xn)−inff≥Cpn−p/(p−2). (5)

Note that the lower bound on the objective values approach when . This fact was also observed in [29, Theorem 12] on an infinite dimensional counterexample. When is bounded from below, but has no minimizers, the values go to zero but no rates can be obtained in general. To see this, consider for any the function defined by

 f:R→R:f(x)=x−α  if  x≥1, −αx+1+α  otherwise. (6)

This function is a differentiable convex function with -Lipschitz gradient. Let be the sequence obtained applying the gradient algorithm to this function. Then

 (∃C>0)(∀n∈N)f(xn)−inff≥C−αn−α/(2+α),

and the lower bound on the objective values approach for .

### 2.3 Beyond the worst case: previous results

To derive better convergence rates for the FB algorithm additional assumptions are needed. In this paper, we consider several geometric assumptions, namely the -conditioning, the -metric subregularity and the -Łojasiewicz property, see Section 3.
The first111If we discard the “classic” strong convexity assumption. result exploting geometry to derive fast convergence rates dates back to Polyak [73, Theorem 4], showing that the gradient method converges linearly (in terms of the values and iterates) when the objective function verifies the -Łojasiewicz inequality. Improved convergence rates for first-order descent methods were then obtained in [76], considering notions slightly stronger than -metric subregularity, and proving finite convergence of the proximal algorithm for , and linear convergence for . These results are improved and extended in [67], analyzing for the first time convergence rates for the iterates of the proximal algorithm using metric subregularity for general . The results in [67] recovers those in [76] (see also [79, 80]), but also derive superlinear rates for , and sublinear rates for . Roughly speaking, the results in [67] show that the bigger is the slower is the algorithm. In the early 90’s, some attention was devoted to the study of -conditioned functions. in particular for (some authors call this property superlinear conditioning, sharp growth or sharp minima property). In this context, [41, 55, 23] showed that the proximal algorithm terminates after a finite number of iterations. For , Polyak [74, Theorem 7.2.1] obtained the finite termination for the projected gradient method. The -conditioning was also used to obtain linear rates for the proximal algorithm in [60].
In [3] it was observed that the -Łojasiewicz property could be used to derive precise rates for the iterates of the proximal algorithm. The authors obtain finite convergence when , linear rates when , and sublinear rates when . Similar results can be found in [4, 69]. Such convergence rates for the iterates have been extended to the forward-backward algorithm (and its alternating versions) in [21], and similar rates also hold for the convergence of the values in [27, 42]. More recently, various papers focused on conditions equivalent (or stronger) than the -conditioning, to derive linear rates [58, 63, 39, 65, 38, 52]. Some effort has also been made to show that the Łojasiewicz property and conditioning are equivalent [19, 20], and to relate it to other error bounds appearing in the literature [52]. See also [70] for a fine analysis of linear rates for the projected gradient algorithm under conditions belonging between strong convexity and -conditioning (see also Subsection 4.3).

As clear from the above discussion the literature on convergence rates under geometric conditions is vast and somewhat scattered. The study that we develop in this paper provides a unified treatment, complemented with several novel results and connections.

## 3 Identifying the geometry of a function

### 3.1 Definitions

In this section we introduce the main geometrical concepts that will be used throughout the paper to derive precise rates for the FB method. Roughly speaking, these notions characterize functions which behave like around their minimizers.

###### Definition 3.1.

Let , let with , and . We say that:

1. is -conditioned on if there exists a constant such that:

 ∀x∈Ω∩missingdomf,γf,Ωp\rm dist\,(x,\rm argmin\,f)p≤f(x)−inff.
2. is -metrically subregular on if there exists a constant such that:

 ∀x∈Ω∩missingdomf,γ∂f,Ω\rm dist\,(x,\rm argmin\,f)p−1≤∥∂f(x)∥_.
3. is -Łojasiewicz on if such that the Łojasiewicz inequality holds:

 ∀x∈Ω∩missingdomf,(f(x)−inff)1−1p≤cf,Ω∥∂f(x)∥_.

We will refer to these notions as global if , and as local if for some and .

The notion of conditioning, introduced in [81, 88], is a common tool in the optimization and regularization literature [6, 71, 57, 84, 20]. It is also called growth condition [71], and it is strongly related to the notion of Tikhonov wellposedness [35]. The -metric subregularity is less used, generally defined for or [36, 58], and is also called upper Lipschitz continuity at zero of in [28], or inverse calmness [34]. The Łojasiewicz property goes back to [66], and was initially designed as a tool to guarantee the convergence of trajectories for the gradient flow of analytic functions, before its recent use in convex and nonconvex optimization. It is generally presented with a constant which is equal, in our notation, to [66, 1, 17, 20], or [69, 45, 42]. The main difference between Definition 3.1 and the literature is that we consider an arbitrary set , which will prove to be essential for the analysis of inverse problems (see more details in Section 5).

The notions introduced in Definition 3.1 are close one to the others. Indeed, for convex functions, -conditioning implies metric subregularity, which implies the Łojasiewicz property. Under some additional assumptions, it is possible to show that the reverse implications hold. For instance, metric subregularity implies conditioning when , [85, Theorem 4.3]. Similar results can also be found in [2, 7, 39, 37], and [28, Theorem 5.2] (for ). Also, it is shown in [20, Theorem 5] that the local Łojasiewicz property implies local conditioning. The next result, proved in Annex A.1, extends the mentioned ones, and states the equivalence between conditioning, metric subregularity, and Łojasiewicz property on -invariant sets (see Definition A.1 in Annex A.1).

###### Proposition 3.2.

Let , let , and let be such that . Consider the following properties:

1. is -conditioned on ,

2. is -metrically subregular on ,

3. is -Łojasiewicz on .

Then i ii iii. One can respectively take and . Assuming in addition that is -invariant, we also have iii i with .

The two next propositions show that these geometric notions are stronger when is smaller, and are meaningful only on sets containing minimizers (their proof follow directly from Definition 3.1 and are left to the reader).

###### Proposition 3.3.

Let be such that , , and .

1. If is -conditioned (resp. is -metrically subregular) on , then is -conditioned (resp. is -metrically subregular) on for any .

2. If is -Łojasiewicz on , then is -Łojasiewicz on for any .

###### Proposition 3.4.

Let be such that . If is a weakly compact set for which , then is -conditioned on for any .

### 3.2 Examples

In this section, we collect some relevant examples.

###### Example 3.5 (Uniformly convex functions).

Suppose that is uniformly convex of order . Then, there exists such that

 (∀(x1,x2)∈missingdom∂f2)(∀x∗1∈∂f(x1))f(x2)−f(x1)−⟨x∗1,x2−x1⟩≥γp∥x2−x1∥p.

This implies that is globally -conditioned, with . Moreover, the global -Łojasiewicz inequality is verified with . In the strongly convex case, when , the -Łojasiewicz inequality holds with the constant , which is sharp. Examples of uniformly convex functions of order are [11, Example 10.14].

###### Example 3.6 (Least squares).

Let be a nonzero bounded linear operator between Hilbert spaces, and , for some . Then, the conditioning, metric subregularity, and Łojasiewicz properties, with and , are equivalent to verify on , respectively:

 γf,X∥x∥2≤⟨A∗Ax,x⟩,  γ∂f,X∥x∥≤∥A∗Ax∥,  and  ⟨A∗Ax,x⟩≤2c2f,X∥A∗Ax∥2.

If holds, one can see that the above inequalities hold with

 γf,X=γ∂f,X=1/(2c2f,X)=σ∗min(A∗A),

meaning in particular that is globally -conditioned. Since is equivalent for to be closed, it is in particular always true when has finite dimension. If instead holds, [45] shows that cannot satisfy any local -Łojasiewicz property, for any . This is for instance the case for infinite dimensional compact operators. Nevertheless, we will show in Section 5, that the least squares always satisfies a -Łojasiewicz property on the so-called regularity sets, for any .

###### Example 3.7 (Convex piecewise polynomials).

A convex continuous function is said to be convex piecewise polynomial if can be partitioned in a finite number of polyhedra such that for all , the restriction of to is a convex polynomial, of degree . The degree of is defined as . Assume . Convex piecewise polynomial functions are conditioned [61, Corollary 3.6]. More precisely, for all , is -conditioned on its sublevel set , with In general, the constant (which depends on ) cannot be explicitly computed. This result implies that polyhedral functions () are -conditioned (in agreement with [23, Corollary 3.6]), and that convex piecewise quadratic functions () are -conditioned. More generally, convex semi-algebraic functions are locally -conditioned [18].

###### Example 3.8 (L1 regularized least squares).

Let , for some linear operator , and . As observed in [20, Section 3.2.1], is convex piecewise polynomial of degree , thus it is -conditioned on each level set . The computation of the conditioning constant is rather difficult. In [20, Lemma 10] an estimate of is provided, by means of Hoffman’s bound [49].

###### Example 3.9 (Regularized problems).

Let be an Euclidean space, , where is a linear operator, , and is a strongly convex function. Then is -conditioned on any level set , , if

1. with , (see [87, Corollary 2]),

2. with , (see [38, Theorem 4.2]),

3. is the nuclear norm of the matrix , provided the following qualification condition holds222We mention that this result was originally announced in [51, Theorem 3.1] without the qualification condition, but then corrected in [86, Proposition 12], in which the authors show that this condition is necessary. (see [86]): such that .

4. is polyhedral (see [86, Proposition 6]).

Note that in [86, 87], the authors do not prove directly that the functions are -conditioned, but that they verify the so-called Luo-Tseng error bound, that is known to be equivalent to -conditioning on sublevel sets [38]. Note that in items ii-iv), the strong convexity and assumptions on can be weakened (see [86] and [38, Theorem 4.2]).

###### Example 3.10 (Distance to an intersection).

Let be two closed convex sets in such that and the intersection is sufficiently regular, i.e. . Let . Clearly, , and . Then is -conditioned on bounded sets [10, Theorem 4.3]. Let . From , it follows that the function is -conditioned on bounded sets.

### 3.3 A sum rule for p-conditioned functions

Let , and assume that they are respectively and -conditioned. What can be said about their sum ? We present in Theorem 3.11 a partial answer to this question, under the assumption that they remain conditioned under linear perturbations (see Remark 3.13). This extends [38, Theorem 4.2], which deals with the sum of -conditioned functions.

###### Theorem 3.11 (Sum rule for conditioning).

Let , where , is a bounded linear operator with closed range, and is of class on . Let . Assume that there exists such that, for and ,

 g−⟨A∗¯v,⋅⟩ is p1-conditioned on Ω⊂X and h+⟨¯v,⋅⟩ is p2-conditioned on AΩ⊂Y. (7)

Suppose that the following qualification conditions are satisfied:

 0 ∈ \rm sri\,(∂g∗(A∗¯v)−A−1∂h∗(−¯v)), (8) 0 ∈ \rm sri\,(A∂g∗(A∗¯v)−∂h∗(−¯v)). (9)

Let . Then, for any , is -conditioned on .

###### Proof.

Let be defined by . Since , [11, Theorem 15.23] yields that strong duality between and holds, meaning that . Differentiability of on implies strict convexity of [11, Proposition 18.10], therefore is nonempty [11, Corollary 15.23]. Moreover, since , [11, Proposition 19.3] applied to the dual problem, yields with for any . Using now [11, Corollary 19.2], we conclude that

 \rm argmin\,f=∂g∗(A∗¯v)∩A−1∂h∗(−¯v). (10)

So, it remains to prove that, for all , there exists such that:

 (∀x∈Ω∩δBX)f(x)−inff≥γ% \rm dist\,p(x,∂g∗(A∗¯v)∩A−1∂h∗(−¯v)). (11)

Fix , , set and . It follows from Proposition 3.3 that and are -conditioned on and , respectively. Moreover, , and . According to (10), and , therefore, for all ,

 g(x) ≥ g(¯x)+⟨A∗¯v,x−¯x⟩+(γ~g,Ωδ/p)\rm dist\,p(x,∂g∗(A∗¯v)), h(Ax) ≥ h(A¯x)+⟨¯v,A¯x−Ax⟩+(γ~h,AΩδ/p)\rm dist\,p(Ax,∂h∗(−¯v)).

Summing these two last inequalities gives, for all :

 f(x)−inff≥C1(\rm dist\,p(x,∂g∗(A∗¯v))+\rm dist\,p(Ax,∂h∗(−¯v))),

with . Since on , we deduce that

 (∀x∈Ωδ)f(x)−inff≥C1max{\rm dist% \,(x,∂g∗(A∗¯v)),\rm dist\,(Ax,∂h∗(−¯v))}p,

It remains to lower bound the right hand side by the distance to . By Example 3.10, thanks to the qualification condition (8) and the fact that is bounded, we derive from (10) that there exists such that

 (∀x∈Ωδ)\rm dist\,(x,\rm argmin\,f)≤C2max{\rm dist\,(x,∂g∗(A∗¯v)),\rm dist% \,(x,A−1∂h∗(−¯v))}. (12)

Fix , and define , which is well defined since we assumed to be closed. Let be defined by . Since , necessarily , so we deduce from Example 3.6 that

 (∀u∈X)ϕy(u)≥(σ∗min(A∗A)/2)\rm dist% \,2(u,\rm argmin\,ϕy). (13)

On the one hand, we have . On the other hand, the definition of implies . Thus, it follows from (13) that

 (∀x∈Ωδ)\rm dist\,(Ax,R(A)∩∂h∗(−¯v))≥σ∗min(A)\rm dist\,(x,A−1∂h∗(−¯v))).

Since this is true for any , we can combine it with (12) to get for all

 \rm dist\,(x,\rm argmin\,f)≤C3max{\rm dist\,(x,∂g∗(A∗¯v)),\rm dist\,(Ax,R(A)∩∂h∗(−¯v))}, (14)

with . To end the proof, note that the qualification condition (9) implies that , so we can use again Example 3.10 to get some such that for all ,

 \rm dist\,(Ax,R(A)∩∂h∗(−¯v)) ≤ C4max{\rm dist\,(Ax,R(A)),\rm dist\,(Ax,∂h∗(−¯v))} = C4\rm dist\,(Ax,∂h∗(−¯v)).

The above inequality, combined with (14) and (11), concludes the proof. ∎

###### Remark 3.12 (On the qualification conditions).

It is worth noting that the conclusion of Theorem 3.11 may not hold if the qualification conditions (8) and (9) are removed, as proved in [86, Section 4.4.4]. Nevertheless, these conditions are automatically satisfied whenever and are uniformly convex functions. Also, if both and have finite dimension and is strictly convex, then (8) and (9) become equivalent to (see [11]).

###### Remark 3.13 (On tilt-conditioned functions).

Following the terminology in [75, 39, 38], we say that a function is -tilt-conditioned on if for all , the function is -conditioned on whenever its set of minimizers is not empty. Clearly, tilt-conditioning is a much stronger assumption than conditioning, but such function has the advantage of verifying (7) without any knowledge on . Tilt conditioning is strongly related to the metric regularity of (see e.g. [7]). Moreover, many relevant conditioned functions are tilt-conditioned. For instance, the -norm , and more generally polyhedral functions are -tilt-conditioned on Euclidean spaces, -uniformly convex functions are -tilt-conditioned on , and convex piecewise polynomials of degree 2 are -tilt-conditioned on their sublevel sets. See [86, Proposition 11] for the proof that the nuclear norm is -tilt-conditioned on bounded sets, and [38, Section 4] for more examples of -tilt-conditioned functions.

## 4 Sharp convergence rates for the Forward-Backward algorithm

In this section, we present sharp convergence results for the forward-backward algorithm applied to -Łojasiewicz functions on a subset , building on the ideas in [5]. We extend the analysis to the case where is an arbitrary set, which will allow us to deal with infinite dimensional inverse problems (see Section 5.1), or structured problems for which all the information is encoded in a manifold (see Section 5.2).

### 4.1 Refined analysis with p-Łojasiewicz functions

###### Theorem 4.1 (Strong convergence, p≥1).

Suppose that Assumption 2.1 is in force, and that is bounded from below. Let be generated by the FB algorithm. Assume that:

1. (Localization) for all , ,

2. (Geometry) is -Łojasiewicz on , for some .

Then the sequence has finite length in , meaning that , and converges strongly to some .

###### Proof.

We first show that has finite length. Since , , and it follows from Lemma A.5 that

 a∥xn+1−xn∥2 ≤ rn−rn+1, with a=12λ(2−λL)>0, (15) ∥∂f(xn+1)∥_ ≤ b∥xn−xn+1∥, with b=λ−1. (16)

If there exists such that then the algorithm would stop after a finite number of iterations (see (15)), therefore it is not restrictive to assume that for all . We set and , so that the Łojasiewicz inequality at can be rewritten as

 (∀n∈N)1≤cφ′(rn)∥∂f(xn)∥_. (17)

Combining (15), (16), and (17), and using the concavity of , we obtain for all :

 ∥xn+1−xn∥2 ≤ bcaφ′(rn)(rn−rn+1)∥xn−xn−1∥≤bca(φ(rn)−φ(rn+1))∥xn−xn−1∥.

By taking the square root on both sides, and using Young’s inequality, we obtain

 (∀n≥1)2∥xn+1−xn∥≤bca(φ(rn)−φ(rn+1))+∥xn−xn−1∥. (18)

Sum this inequality, and reorder the terms to finally obtain

 (∀n≥1)n∑k=1∥xk+1−xk∥≤bcaφ(r1)+∥x1−x0∥.

We deduce that has finite length and converges strongly to some . Moreover, from (16) and the strong closedness of , we conclude that . ∎

Now we will provide explicit rates of convergence, for both the iterates and the values.

###### Theorem 4.2 (Rates of convergence, p≥1).

Suppose Assumption 2.1 is in force. Suppose that , and let be generated by the FB algorithm. Assume that:

1. (Localization) for all , ,

2. (Geometry) is -Łojasiewicz on , for some .

Then converges strongly to some . Moreover, there exists some constants , explicitly computable (see equations (21) and (23)), such that the following convergence rates hold, depending on the value of , and of :

1. If , then for every .

2. If , the convergence is superlinear: for all ,

 f(xn+1)−inff≤(f(xn)−inffκ)p2(p−1) and ∥xn+1−x∞∥≤Cp(f(xn)−inff)1/2,
3. If , the convergence is linear: for all ,

 f(xn+1)−inff≤11+κ(f(xn)−inff) and ∥xn+1−x∞∥≤C2(f(x0)−inff)1/2(1+κ)−n/2.
4. If , the convergence is sublinear: for all ,

 f(xn)−inff≤(C′p)p/(p−2)n−pp−2 % and ∥xn+1−x∞∥≤Cp(C′p)1/(p−


text:
# Tag Info

For bounded operators on a given Hilbert space, C*-algebras characterize topologically closed subalgebras of ${\mathcal B}({\mathcal H})$ (in operator norm), also closed under taking the adjoint operator. C*-algebras are at the heart of (non-commutative-geometry) and are extensively used in (mathematical-physics).


text:
Waiting for answer This question has not been answered yet. You can hire a professional tutor to get the answer.

QUESTION

# The barometric pressure in Breckenridge, Colorado (elevation 9600 feet) is 580 mm Hg. How many atmospheres is this?

Well it is certainly less than the pressure at sea level.

One atmosphere at sea level can support a column of mercury "760 mm" high.

We make the the calculation: "580 mm Hg"/("760 mm Hg"*atm^-1), approx, 3/4 of an atmosphere. I can remember hiking (slowly!) at those altitudes, and it certainly was difficult to get your breath given the reduced concentration of oxygen at these altitudes.


text:
## FANDOM

1,861 Pages

The Writing expressions with exponents word problems exercise appeared under the 6th grade (U.S.) Math Mission, but was removed by Khan Academy. This exercise uses word problems to encourage practice with translating expressions using exponents.

## Types of Problems

There is one type of problem in this exercise:

1. Write the expression: This problem has a word problem in which there is at least one need for an exponential expression. The student is expected to write a correct numerical expression representing the expression in the available space.

## Strategies

This exercise is easy to get accuracy badges with knowledge of the basic vocabulary of arithmetic. The speed badges are easy because the numbers are reasonably small and there are good strategies to accomplish them quickly listed below.

1. The numerical expression will be accepted in several forms, as long as they are numerically equivalent.
2. A fast way to get solutions with smaller numbers is to use the numerical expression of the "answer."

## Real-life Applications

1. An kind of indirect example of using exponents is when one talks about extremely tiny or extremely big quantities. For example, the term "nanometer" means $10^{-9}$ meter. The prefix "nano" means the number $10^{-9}$, which is an extremely small decimal number (0.000000001).


text: You can also send assets to other Injective wallets using the wallet. Note that Injective supports the memo field, so please be reminded to check whether your recipient requires this detail to be filled before transferring assets.


text:
Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals
Search results

Search: MSC category 55M35 ( Finite groups of transformations (including Smith theory) [See also 57S17] )

 Expand all        Collapse all Results 1 - 2 of 2

1. CMB 2007 (vol 50 pp. 206)

Golasiński, Marek; Gonçalves, Daciberg Lima
 Spherical Space Forms: Homotopy Types and Self-Equivalences for the Group $({\mathbb Z}/a\rtimes{\mathbb Z}/b) \times SL_2\,(\mathbb{F}_p)$ Let $G=({\mathbb Z}/a\rtimes{\mathbb Z}/b) \times \SL_2(\mathbb{F}_p)$, and let $X(n)$ be an $n$-dimensional $CW$-complex of the homotopy type of an $n$-sphere. We study the automorphism group $\Aut (G)$ in order to compute the number of distinct homotopy types of spherical space forms with respect to free and cellular $G$-actions on all $CW$-complexes $X(2dn-1)$, where $2d$ is the period of $G$. The groups ${\mathcal E}(X(2dn-1)/\mu)$ of self homotopy equivalences of space forms $X(2dn-1)/\mu$ associated with free and cellular $G$-actions $\mu$ on $X(2dn-1)$ are determined as well. Keywords:automorphism group, $CW$-complex, free and cellular $G$-action, group of self homotopy equivalences, Lyndon--Hochschild--Serre spectral sequence, special (linear) group, spherical space formCategories:55M35, 55P15, 20E22, 20F28, 57S17

2. CMB 1997 (vol 40 pp. 108)

Schaer, J.
 Continuous Self-maps of the Circle Given a continuous map $\delta$ from the circle $S$ to itself we want to find all self-maps $\sigma\colon S\to S$ for which $\delta\circ\sigma = \delta$. If the degree $r$ of $\delta$ is not zero, the transformations $\sigma$ form a subgroup of the cyclic group $C_r$. If $r=0$, all such invertible transformations form a group isomorphic either to a cyclic group $C_n$ or to a dihedral group $D_n$ depending on whether all such transformations are orientation preserving or not. Applied to the tangent image of planar closed curves, this generalizes a result of Bisztriczky and Rival [1]. The proof rests on the theorem: {\it Let $\Delta\colon\bbd R\to\bbd R$ be continuous, nowhere constant, and $\lim_{x\to -\infty}\Delta(x)=-\infty$, $\lim_{x\to+\infty}\Delta (x)=+\infty$; then the only continuous map $\Sigma\colon\bbd R\to\bbd R$ such that $\Delta\circ\Sigma=\Delta$ is the identity $\Sigma=\id_{\bbd R}$. Categories:53A04, 55M25, 55M35

© Canadian Mathematical Society, 2014 : http://www.cms.math.ca/


text:
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

One of the simplest options strategies is known as the covered call. For this strategy, an investor who already owns a stock elects to sell (or write) an option contract to surrender that stock at a specified price (known as the strike) at some point in the future (also known as expiration). The sale of the contract generates income for the investor, not unlike when an insurance company receives premiums from selling an insurance contract.

It is called “covered” because the investor owns the stock, as opposed to “naked” when the investor does not, and thus has the capacity to deliver the stock should the contract be exercised. The strategy is also often referred to as “buy-write” in that the investor buys the underlying stock while simultaneously selling a call option in one transaction. If the investor does not own the stock, he or she will execute a buy-write. But if the investor already owns the stock, he or she will execute a covered call.

In terms of risk/reward, the maximum loss on the covered call strategy is the amount paid for the asset less any premiums received from selling the contract. The maximum gain is the difference between the strike price of the option contract and the amount paid for the stock plus premiums received. In effect, the investor is willing to cap his upside potential in return for receiving a guaranteed premium.

Why would anyone want to cap his upside while only modestly improving his downside? For one, most stocks are unlikely to go to zero unless they’re Enron or Theranos. Similarly, most stocks don’t move up in a straight line steadily over time, so there is a chance that, like insurance, the event that would force the investor to surrender the stock never occurs, allowing him or her to pocket the premium. Additionally, depending on how far away the strike is placed relative to the stock price, the likelihood the stock could get “called away” (a contractually obligated surrender) declines at an accelerating rate. Throw in the time factor and writing covered calls looks very similar to writing insurance premiums.

From an investor perspective, then, writing covered calls is often considered a yield-enhancing strategy. For example, say the annual expected price return on a stock is 7% with an annualized standard deviation of 12%. If the investor could sell a call that expires one-year hence, at 12% above the current stock price, and receive a credit from the sale equivalent to a 1% of the current stock price, then the investor theoretically has a 70% chance of improving his return to 8%. But, that’s the most the stock can return.

Alternatively, the investor could sell calls that expire sooner but are less than 12% away since the range of probable moves in a less than 12-month period would be less than 12%. Say the investor sells calls that expire in a month that are 3% above the current stock price and yield 0.5% in premium. That investor could generate an additional 6% in yield on an annual basis!

Unfortunately, things don’t work that way. Nonetheless, covered call writing is a popular strategy. Popular enough that the Chicago Board of Options (CBOE) publishes a “buy-write” index, known as the “BXM”, on the strategy. It also publishes other indices, all of which provide us with a treasure trove of data to analyze. In the ensuing posts, we’ll look at a number of these strategies.

In this post we’ll begin looking at the buy-write or BXM index. Later, we’ll examine some of the findings from pubished reports on the covered call strategy. You can find information on the CBOE buy-write strategy here and some of the studies we’ll look at here and here.

## Call to cover

To begin let’s look at the index and execute some exploratory data analysis. Here’s a graph of the S&P500 index vs. the CBOE buy-write index. We’ll be using BXM or buy-write interchangeably.

A couple points worth noting is that the indices don’t start on the same basis, and, the buy-write index includes dividends. So we should normalize this and compare the buy-write to the S&P500 total return index. Doing all that we arrive at the following.

Wow! What a difference scaling makes. Almost makes us want to go out and invest right now. But wait. It’s an index so it isn’t investable.

A couple of things that first jump out. The shape of both curves is relatively the same, as would be expected since the BXM is based on the S&P. Some of the outperformance seems to be weighted toward the beginning of the time series. It’s also not so easy to tell whether the BXM is more or less volatile from this long series. So we’ll have to look at those points individually.

Here’s a yearly bar chart of cumulative returns

What should be readily apparent is the BXM doesn’t seem to outperform the S&P too much. When it does, the S&P is usually having a bad year. Furthermore, when the S&P outperforms the BXM, it does so by a great deal, usually on the positive side. In total, BXM only outperformed the S&P 16 times out of 34 for the years we have data — 1986-2019.

If the BXM seems to underperform only modestly on a yearly basis, what causes the cumulative outperformance? The nature of returns. The BXM generally outperforms when the S&P suffers a down year. By experiencing less severe declines in a few bad years, the BXM has less ground to make up to get back to flat. When the S&P lost 35% in 2008, the BXM only lost 26%. Even though the BXM did not rebound as much in 2009, it was sufficient to keep it ahead of the S&P for that year. The table below shows the average returns of the BXM and the S&P 500 when the BXM’s return exceeds or trails the S&P 500

Table 1: Average over and underperformance of the buy-write index relative to the S&P500 total return
Performance BXM return (%) S&P 500 return(%)
Outperformance 1.1 -3.4
Underperformance 13.3 19.9

Another reason that the covered-calls attract investors is the assumption that it lowers volatility. Why would this be the case? Since one collects some cash from selling the call, the downside is less severe while the upside is, of course, capped. Hence, in any one year the covered-call strategy is likely to see both higher lows and lower highs than simply owning the stock. That narrowed range of outcomes means volatility (the traditional measure of risk) is lower, hence risk-adjusted returns are better. Let’s see if that holds based on the data. In the bar chart below we present the annualized volatility by year for the buy-write index and the S&P 500.

Apparently, this assumption holds because there appears to be no year in which the BXM is more volatile than the S&P. But that lower volatility does come at price, since, as we noted, the upside is capped. Whether an investor is being adequately compensated for limiting his upside potential or whether this narrowe range of outcomes is an appropriate measure of risk will be left for later discussions.

In our next post, we’ll examine some claims made by one report on the buy-write strategy; namely, that it was found to have higher growth, lower volatility, and better risk-adjusted returns. Until then, here is the underlying code:

library(tidyquant)

# Get data and process

cboe <- cboe %>%
rename("date" = X__1,
"BXM" = BXMSM,
"BXY" = BXYSM,
"CLL" = CLL*,
"VIX" = VIX®) %>%
mutate(date = ymd(date))

colnames(cboe) <- tolower(colnames(cboe))

# Graph data

# Graph indices
cboe %>%
gather(key, value, -date) %>%
filter(key %in% c("bxm", "spx")) %>%
ggplot(aes(date, value, color = key)) +
geom_line(lwd = 1.1) +
scale_color_manual("", labels = c("Buy-write index", "S&P500"),
values = c("blue", "black"))+
theme(legend.position = "top",
legend.text = element_text(size = 10),
axis.title = element_text(size = 10)) +
labs(x = "Date",
y = "Index",
title = "S&P 500 vs. buy-write index")

# Graph return of buy-write vs S&P
cboe %>%
gather(key, value, -date) %>%
# mutate(value = as.numeric(value)) %>%
filter(key %in% c("bxm", "spx")) %>%
group_by(key) %>%
mutate(value = (value/value[1]-1)*100) %>%
ggplot(aes(date, value, color = key)) +
geom_line(lwd = 1.1) +
scale_color_manual("", labels = c("Buy-write index", "S&P500"),
values = c("blue", "black"))+
theme(legend.position = "top",
legend.text = element_text(size = 10),
axis.title = element_text(size = 10)) +
labs(x = "Date",
y = "Return (%)",
title = "S&P 500 total return vs. buy-write index")

# Yearly returns
cboe %>%
gather(key, value, -date) %>%
filter(key %in% c("bxm", "sptr")) %>%
mutate(year = year(date)) %>%
group_by(key, year) %>%
mutate(value = ROC(value)) %>%
summarise(value = Return.cumulative(value)) %>%
ggplot(aes(year, value*100, fill = key)) +
geom_bar(stat = "identity", position = "dodge") +
scale_fill_manual("", labels = c("Buy-write index", "S&P500"),
values = c("blue", "darkgrey"))+
theme(legend.position = "top",
legend.text = element_text(size = 10),
axis.title = element_text(size = 10)) +
labs(x = "Date",
y = "Return (%)",
title = "Cumulative returns by year, S&P500 total return vs buy-write index")

# How many times does bxm outperform
perf <- cboe %>%
gather(key, value, -date) %>%
filter(key %in% c("bxm", "sptr")) %>%
mutate(year = year(date)) %>%
group_by(key, year) %>%
mutate(value = ROC(value)) %>%
summarise(value = Return.cumulative(value)) %>%
count(bxm > sptr)

# Average returns
cboe %>%
gather(key, value, -date) %>%
filter(key %in% c("bxm", "sptr")) %>%
mutate(year = year(date)) %>%
group_by(key, year) %>%
mutate(value = ROC(value)) %>%
summarise(value = Return.cumulative(value)) %>%
mutate(perf = bxm - sptr,
opf = ifelse(perf > 0, "Outperformance", "Underformance")) %>%
group_by(opf) %>%
summarise(bxm_ret = round(mean(bxm),3)*100,
sptr_ret = round(mean(sptr),3)*100) %>%
rename("Performance" = opf,
"BXM return (%)" = bxm_ret,
"S&P 500 return(%)" = sptr_ret) %>%
knitr::kable(caption = "Average over and underperformance of the buy-write index
relative to the S&P500 total return")

# Volatility by year
cboe %>%
gather(key, value, -date) %>%
filter(key %in% c("bxm", "sptr")) %>%
mutate(year = year(date)) %>%
group_by(key, year) %>%
mutate(value = ROC(value)) %>%
summarise(vol = sd(value, na.rm = TRUE)*sqrt(12)*100) %>%
ggplot(aes(year, vol, fill = key)) +
geom_bar(stat = "identity", position = "dodge") +
scale_fill_manual("", labels = c("Buy-write index", "S&P500"),
values = c("blue", "darkgrey"))+
theme(legend.position = "top",
legend.text = element_text(size = 10),
axis.title = element_text(size = 10)) +
labs(x = "Date",
y = "Return (%)",
title = "Annualized volatility by year, S&P500 total return vs buy-write index")


text:
# 1. Introduction

In this article we explain how to infer the posterior marginals of the hidden state variables in a HMM from a sequence of observations/emissions.  The algorithm makes use of the principle of dynamic programming (i.e. it breaks down the problem into simpler ones) during two passes over the data. The first pass goes forward in time while the second goes backward in time; hence the name forward–backward algorithm.

(We assume fixed parameters please see the article on Baum Welch Algorithm for ways to estimate the parameters.)

We will build up the full algorithm incrementally by

• Deriving conditional independence assumptions on the underlying graphical model
• Applying Bayes sequentially to incorporate previous observations (forward pass)
• Adding a backward pass so that we condition on past and previous observations

Our presentation is to great extent based on [2] from which we also adopted large parts of notation.

# 2. Forward-Backward Algorithm

## 2.1 Preliminaries

A first order Hidden Markov Model has hidden variables $\inline&space;h_t$ and visible variables $v_t$ corresponding to observed data.

Figure 13.4 from (Barber, 2014)

Recall that we can factorize any joint distribution  $p(x_{1:V})$ as

$p(x_{1:V})&space;=&space;p(x_1)&space;p(x_2&space;|&space;x_1)&space;p(x_3&space;|&space;x_{1:2}),&space;\ldots&space;p(x_V&space;|&space;x_{1:V-1})&space;$

(This is sometimes called "chain rule of probability", the Matlab like notation $i:j$ denotes the ordered index set $\{i,&space;i+1,&space;i+2,&space;i+3,&space;\ldots,&space;j-1,&space;j\}$)

Applying the rule to our model the joint probability of hidden and observed variables is given by

$p\left[h_{1:T},v_{1:T}\right]=&space;p\left(h_1\right)&space;p\left(v_1|h_1\right)&space;\prod&space;_{t=2}^T&space;p\left(h_t|h_{t-1}\right)&space;p\left(v_t|h_t\right)$

To simplify the factored expressions we want to establish conditional independence relations. While these can be formally shown by D-Separation ([4], sec. 10.5.1) or tedious algebraic manipulations a more intuitive way to assert independence graphically is given by the Bayes ball rules.

Figure 10.9 from ([4], 2012)

The rules drawn above show the most important rules in a Hidden Markov Model. As blocked paths (filled cycles) render the corresponding nodes independent, $h_{t+1}$ is independent of $h_{t-1}$ given $h_t$ as well as $v_{t-1}$ and $v_{t}$ and$v_{t+1}$ are.

## 2.2 Forward Filtering

The goal in forward filtering is to calculate $\alpha(h_t)&space;:=&space;p(h_t,&space;v_{1:t})$ that is the joint probability of the hidden state at the current time $t$ together with all previous observations

To this end we first marginalize over the previous states

$p\left[h_t,v_{1:t}\right]\to&space;\sum&space;_{h_{t-1}}&space;p\left[h_t,h_{t-1},v_{1:t}\right]$

and apply the chain rule to obtain

$p\left[h_t,v_{1:t}\right]\to&space;\sum&space;_{h_{t-1}}&space;p\left[v_t|v_{1:t-1},h_t,h_{t-1}\right]p\left[h_t|}v_{1:t-1},h_{t-1}\right]p\left[v_{1:t-1},h_{t-1}\right]$

Using the conditional independence assumptions of the Markov model we can simplify this equation to read

$p\left[h_t,v_{1:t}\right]\to&space;\sum&space;_{h_{t-1}}&space;p\left(v_t|h_t\right)p\left(h_t|h_{t-1}\right)p\left[v_{1:t-1},h_{t-1}\right]$

This corresponds to a recursive formulation of the joint probability $\alpha(h_t)&space;:=&space;p(h_t,&space;v_{1:t})$

$p\left[h_t,v_{1:t}\right]\to&space;\alpha(h_t)&space;\to&space;p(v_t&space;|&space;h_t)&space;\sum\limits_{h_{t-1}}&space;p(h_t&space;|&space;h_{t&space;-&space;1})&space;\alpha(h_{t-1})&space;\quad&space;t&space;>&space;1&space;$

The base case is

$\alpha&space;\left(h_1\right)\to&space;p\left(h_1,v_1\right)\to&space;p\left(h_1\right)&space;p\left(v_1|h_1\right)$

### Interpretation

The $\alpha$-Recursion can be understood as a predictor corrector method

$\alpha(h_t)&space;\to&space;\underbrace{p\left(v_t|h_t\right)}_{\text{Corrector}}\underbrace{\sum&space;_{h_{t-1}}&space;p\left(h_t|h_{t-1}\right)&space;\alpha&space;\left(h_{t-1}\right)}_{\text{Predictor}}$

The filtered distribution $\alpha(h_{t-1})$ from the previous timestep is propagated forwards by the dynamics for one timestep to reveal a prior distribution at time $t$. This distribution is then modulated by the observation $v_t$, which serves to incorporate the new evidence into a posterior distribution.

## 2.3 Backward Smoothing

If we do not only take into account previous observations but process the data offline we can possibly obtain a better (smoother) estimate. Parallel smoothing incorporates information from past and future using the fact that ( when observed ) $h_t$ d-separates the past from the future.  Formally that is

$p\left[h_t,v_{1:T}\right]\to&space;p\left[h_t,v_{1:t},v_{t+1:T}\right]\to&space;\underbrace{p\left[h_t,v_{1:t}\right]}_{\alpha({h_t})}\underbrace{p\left[v_{t+1:T}|h_t\right]}_{\beta(h_t)}$

We see that the desired posterior $p(h_t,&space;v_{1:T})$ can be factored into the past and future contribution $\alpha(h_t)&space;:=&space;p(h_t,&space;v_{1:T})$ and $\beta(h_t)&space;:=&space;p(v_{t&space;+&space;1&space;:&space;T}&space;|&space;h_t)$

A recursive update formula for $\beta(h_t)$ can be derived as follows

$p\left(v_{t:T}|h_{t-1}\right)\to&space;\sum&space;_{h_t}&space;p\left[v_t,v_{t+1:T},h_t|h_{t-1}\right]$

Repeatedly applying the chain rule we have

$p\left(v_{t:T}|h_{t-1}\right)\to&space;\sum&space;_{h_t}&space;p\left[v_t|v_{t+1:T},h_t,h_{t-1}\right]p\left[v_{t+1:T},h_t|h_{t-1}\right]&space;$

and

$p\left(v_{t:T}|h_{t-1}\right)\to&space;\sum&space;_{h_t}&space;p\left(v_t|h_t\right)p\left[v_{t+1:T}|h_t,h_{t-1}\right]p\left(h_t|h_{t-1}\right)&space;$

So that we can identify the recursion

$\beta&space;\left(h_{t-1}\right)&space;\leftarrow&space;\sum&space;_{h_t}&space;p\left(v_t|h_t\right)&space;\beta&space;\left(h_t\right)&space;p\left(h_t|h_{t-1}\right)&space;\quad&space;2&space;\leq&space;t&space;\leq&space;T$

with initialisation $\beta(h_T)&space;\leftarrow&space;1$

## 2.5 Complete Forward Backward Algorithm

Together the $\alpha-\beta$ recursions make up the forward backward algorithm and the smoothed posterior distribution is given by

$p\left[h_t|v_{1:T}\right]\text{:=}&space;\frac{\alpha&space;\left(h_t\right)&space;\beta&space;\left(h_t\right)}{\sum&space;_{h_t}&space;\alpha&space;\left(h_t\right)&space;\beta&space;\left(h_t\right)}&space;$

## 3. Illustration

As an illustrative toy example take a look at the "dishonest casino HMM" described by ([4] respectively [3])

Figure 10.9 from ([4])

Imagine a dishonest casino which may occasionally use a loaded (L) die skewed towards $6$.  (For a fair (F) die the emission probabilities are given by a uniform distributions over the integers $\{1:6\}$, for the loaded die the probablity is much higher e.g. $\inline&space;\frac{1}{2}$ in our example) Our filtering / smoothing task in this setting would be to infer whether this is the case just by considering a sequence of games.

Typical emissions in that setting may look as follows:

Rolls: 664153216162115234653214356634261655234232315142464156663246

the corresponding (hidden) ground truth would be:

Die:   LLLLLLLLLLLLLLFFFFFFLLLLLLLLLLLLLLFFFFFFFFFFFFFFFFFFLLLLLLLL

The resulting output $p(h_{t}&space;|&space;v_{1:t})$ after forward filtering is

Figure 10.9a from ([4], 2012)
After forward-backward filtering we obtain $p(h_{t}&space;|&space;v_{1:T})$:

Figure 10.9b from (Murphy, 2012)

We see that forwards-backwards smoothing gives indeed a better (smoother) estimate. If we threshold the estimates at $0.5$ and compare to the true sequence, we find that the filtered method makes $71$ errors out of $300$, and the smoothed method makes $49/300$

# 3. Discussion

• As both forward and backward recursion involve repeated multiplication with factors $\leq&space;1$ it is advisable to work in the log domain.  Alternatively if one is only interested into the posteriors normalization at each stage such that $\sum&space;_{h_t}&space;\beta&space;\left(h_t\right)=1$ is also a viable approach.
• An alternative to the parallel approach presented here is correction smoothing (Barber 2014, sec. 23.2.4) which forms a direct recursion for the posterior $\inline&space;\gamma&space;\left(h_t\right)=\sum&space;_{h_{t+1}}&space;p\left[h_t|h_{t+1},v_{1:t}\right]\gamma&space;\left(h_{t+1}\right)$.  This procedure also referred to as Rauch-Tung-Striebel method is sequential because since the $\alpha$ recursions must be completed before the $\gamma$ recursions may be started.
• In relation to the Viterbi-Decoding which computes maximum a posteriori state sequence (MAP) $\operatorname{argmax}_{h_{1:T}}p(h_{1:T}|v_{1:T})$ the approach presented can be used to compute the maximizer of the posterior marginals (MPM) $\left[\operatorname{argmax}_{h_{1}}p(h_{1}|v_{1:T}),&space;\ldots,&space;\operatorname{argmax}_{h_{T}}p(h_{T}|v_{1:T})\right]$.  The advantage of the joint MAP estimate is that it is always globally consistent which is desireable if we have the requirement that data should be explained by a single consistent (e.g. lingualistically plausible) path.  On the other hand the MPM is more robust since for each node we average over the values of its neighbour rather than conditioning on a specific value (see (Murphy 2012, sec. 17.4.4.1)) for additional details.  With regards to time and space complexity both algorithms generally are of order $O(K^2&space;T)$ and $O(K&space;T)$.

[1]: Christopher Bishop, Pattern recognition and machine learning,  Springer,  2006.

[2]: David Barber, Bayesian reasoning and machine learning, Cambridge University Press, 2014.

[3]: Richard Durbin, Biological sequence analysis: probabilistic models of proteins and nucleic acids, Cambridge University Press, 1998.

[4]: Kevin Murphy, Machine Learning - A probabilistic perspective, MIT Press, 2012.


text:
# Statnet

Statnet is a suite of R packages for the analysis, simulation and visualization of network data focused around Exponential-family Random Graph Models. It is developed by Pavel Krivitsky, Mark S. Handcock, David R. Hunter, Carter T. Butts, Chad Klumb, Steven M. Goodreau, and Martina Morris plus contributors (whom I enjoy beeing).

# lspline

Linear splines with convenient parametrisations for use with R modeling functions such as lm() or glm().