A pre-processing procedure for the implementation of the greedy rank-one algorithm to solve high-dimensional linear systems

1.   Introduction

Notation: For two sequences of positive constants $\{a_n, n\geq1\}$ and $\{b_n, n\geq1\}$, symbols $a_n\sim b_n$, $a_n = O(b_n)$ and $a_n = o(b_n)$ stand for $\lim a_n/b_n = 1$, $\lim a_n/b_n\in(0, \infty)$ and $\lim a_n/b_n = 0$, respectively. For simplicity, we shall write $\stackrel{\mathbb{P}}{\longrightarrow}$, $\stackrel{a.s.}{\longrightarrow}$ and $\stackrel{L^p}{\longrightarrow}$ to express the convergence in probability, the almost certain convergence and $p$-mean convergence, respectively.

The following concept of superadditive function was introduced in ^[1].

Definition 1.1. A function $\phi: R^n\rightarrow R$ is called superadditive if $\phi(\boldsymbol{x}\vee\boldsymbol{y}) +\phi(\boldsymbol{x}\wedge\boldsymbol{y}) \geq\phi(\boldsymbol{x})+\phi(\boldsymbol{y})$ for all $\boldsymbol{x}, \boldsymbol{y}\in R^n$, where $\vee$ is for componentwise maximum and $\wedge$ is for componentwise minimum.

Hu ^[2] introduced the concept of negatively superadditive-dependent (NSD) based on the above concept of superadditive function.

Definition 1.2. A random vector $\boldsymbol{X} = (X_1, X_2, \cdots, X_n)$ is said to be NSD if

where $X_1^*, X_2^*, \cdots, X_n^*$ are independent such that $X_i^*$ and $X_i$ have the same distribution for each $i$ and $\phi$ is a superadditive function such that the expectations in the above equation exists. A sequence $\{X_n, \, n\geq1\}$ of random variables is said to be NSD if for each $n\geq1$, $(X_1, X_2, \cdots, X_n)$ is NSD.

Hu ^[2] established some basic properties and three structural theorems of NSD random variables. An interesting example was also presented in ^[2], which illustrated that NSD is not necessarily negatively associated (NA, ^[3]). Christofides and Vaggelatou ^[4] showed that NA is NSD. Eghbal et al. ^[5] derived two maximal inequalities and strong law of large numbers of quadratic forms of NSD random variables. Shen et al. ^[6] studied almost sure convergence and strong stability for weighted sums of NSD random variables. Wang et al. ^[7] studied complete convergence for arrays of rowwise NSD random variables, with applications to nonparametric regression. For more research of the limit theory for NSD random variables, the author can refer the reader to ^{[8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]}.

NA random variable has been studied many times and attracted extensive attention, so it is very significant to investigate the limit theorems of this wider NSD class, which is highly desirable and of considerable significance in theory and application.

A random variable $X$ is called to be a two-tailed Pareto distribution whose density is

where $p+q = 1$.

Let $\{X_n, \, n\geq1\}$ be independent Pareto-Zipf random variables satisfying $\mathbb{P}(X_n = 0) = 1-1/n$,

and $f_{X_n}(x) = \frac{1}{(x+n)^2}\mathbb{I}(x > 0)$.

Obviously, if the random variable $X_n$ satisfies Eq (1.1) or (1.2), then $\mathbb{E}|X_n| = \infty$, $n\geq1$. Alder ^[25] considered independent and identically distributed (i.i.d.) random variables satisfying Eq (1.1) and studied the strong law of large numbers. Alder ^[26] obtained the weak law of large numbers for Pareto-Zipf random variables. For more research on laws of large numbers for i.i.d. random variables with infinite mean, the author can refer to works of Adler ^[27,28] and Matsumoto and Nakata ^[29,30,31].

Yang et al. ^[24] investigated the law of large numbers for NSD random variables satisfying Pareto-type distributions with infinite means, and obtained the following theorems which extend and improve the corresponding ones in ^[25,26]:

Theorem 1.1. Let $\{X_n, \, n\geq1\}$ be a nonnegative sequence of NSD random variables whose distributions are defined by $\mathbb{P}(X_n = 0) = 1-1/c_n$ for $n\geq1$ and the tail probability

where $\{c_n\}$ is a nondecreasing constant sequence with $c_n\geq1$ and

Then we have

Theorem 1.2. Let $\{X_n, \, n\geq1\}$ be a sequence of NSD random variables with the same distributions from a two-tailed Pareto distribution defined by Eq (1.1). Then for all $\beta > 0$ we have

In the current work, the author studies the weak and strong laws of large numbers for NSD random variables. The obtained results in this article extend and improve Theorems 1.1 and 1.2. Meanwhile, the author investigates $p$-mean convergence for NSD random variables under some appropriate conditions, which was not considered in ^[24].

Throughout this paper, the symbol $C$ denotes a positive constant which may differ from one place to another. The symbol $\mathbb{I}(A)$ denotes the indicator function of the event $A$.

2.   Some lemmas and main results

To prove our main results, we first present some technical lemmas.

Lemma 2.1. (^[2]) If $(X_1, X_2, \cdots, X_n)$ is NSD and $f_1, f_2, \cdots, f_n$ are all non decreasing, then $(f_1(X_1), \; f_2(X_2), \cdots, f_n(X_n))$ is also NSD.

As we know, moment inequalities are very important tools in establishing the limit theorems for sequences of random variables. Shen et al. ^[6] presented the following Marcinkiewicz-Zygmund inequality with exponent $2$.

Lemma 2.2. (^[6]) Let $\{X_n, \, n\geq1\}$ be a sequence of NSD random variables with $\mathbb{E}X_n = 0$ and $\mathbb{E}X_n^2 < \infty$ for $n\geq1$. Then

By means of similar methods in Shao ^[32], Wang et al. ^[7] established the following Rosenthal-type maximal inequality, which is very useful in establishing the convergence properties for NSD random variables:

Lemma 2.3. (^[7]) Let $p > 1$. Let $\{X_n, \, n\geq1\}$ be a sequence of NSD random variables with $\mathbb{E}|X_i|^p < \infty$ for each $i\geq1$. Then for all $n\geq1$,

and

Lemma 2.4. (^[6]) Let $\{X_n, \, n\geq1\}$ be a sequence of NSD random variables. If

then $\sum_{n = 1}^{\infty}(X_n-EX_n)$ almost certainly converges.

Now we state our main results and the proofs will be presented in next section.

Theorem 2.1. Let $\{X_n, \, n\geq1\}$ be a nonnegative sequence of NSD random variables whose distributions are defined by $\mathbb{P}(X_n = 0) = 1-1/c_n$ for $n\geq1$ and the tail probability

where $\{c_n, n\geq1\}$ is a nondecreasing constant sequence with $c_n\geq1$ and

Let $\{D_n, n\geq1\}$ be a sequence of constants satisfying $D_n\rightarrow \infty$ and $C_n = o(D_n)$. Then we have

where $X_{nj} = X_j\mathbb{I}(X_j\leq D_nc_j)+D_nc_j\mathbb{I}(X_j > D_nc_j)$, $1\leq j\leq n$.

Take $D_n = C_n\log C_n$, then we can obtain the following corollary which extends Theorem 1.1.

Corollary 2.1. Let $\{X_n, \, n\geq1\}$ be a nonnegative sequence of NSD random variables whose distributions are defined by $\mathbb{P}(X_n = 0) = 1-1/c_n$ for $n\geq1$ and the tail probability Eq (2.1), where $\{c_n, n\geq1\}$ is a nondecreasing constant sequence satisfying $c_n\geq1$ and Eq (2.2). Then

Remark 2.1. Yang et al. ^[24] proved that

and

which yields

Then we can find that Theorem 1.1 is a special case of Corollary 2.1 for $k = n$. Therefore, Theorem 2.1 and Corollary 2.1 extend and improve Theorem 1.1.

Theorem 2.2. Let $\{X_n, \, n\geq1\}$ be a sequence of identically distributed NSD random variables. Let $\{d_n, n\geq1\}$ be a sequence of positive constants satisfying $d_n\uparrow\infty$, and $\{c_n, n\geq1\}$ be a sequence of positive constants such that $\varphi(n)\equiv c_nd_n$ satisfies $\varphi(n)\rightarrow \infty$ as $n\rightarrow \infty$,

and

Then

where $\widetilde{X_{j}} = -\varphi(j)\mathbb{I}(X_j < -\varphi(j))+X_j\mathbb{I}(|X_j|\leq \varphi(j))+\varphi(j)\mathbb{I}(X_j > \varphi(j))$, $1\leq j\leq n$.

Remark 2.2. We will show that Theorem 1.2 is a special case of Theorem 2.2. In fact, if we assume that $\{X_n, \, n\geq1\}$ is a sequence of NSD random variables with the same distributions from a two-tailed Pareto distribution defined by Eq (1.1), and take $c_n = n\log^{2-\beta}n$ and $d_n = \log^{\beta}n$ ($\beta > 0$), then $\varphi(n) = c_nd_n = n\log^{2}n$. We can verify that $\varphi(n) = n\log^{2}n$ satisfies the conditions stated in Theorem 2.2.

First, it is clear that $\varphi(n) = n\log^{2}n$ satisfies $\varphi(n)\rightarrow \infty$ as $n\rightarrow \infty$.

Second, we have by standard calculations that

which shows that Eq (2.5) is verified.

Next, we have by Eq (1.1) and $\varphi(n) = n\log^{2}n$ that

and then Eq (2.6) is verified.

Finally, we also obtain by Eq (1.1) and $\varphi(j) = j\log^{2}j$ that

By similar argument as in the proof of $H\rightarrow0$ in ^[24], we can obtain $J_1\rightarrow0$. By similar argument as in the proof of Eq (3.5) in ^[24], we can prove $J_2\rightarrow \frac{p-q}{\beta}$. Then we obtain by Eq (2.7) that

To sum up, Theorem 1.2 is a special case of Theorem 2.2 and then Theorem 2.2 extends Theorem 1.2.

Next, we present a new theorem of $p$-mean convergence for NSD random variables under some appropriate conditions, which was not considered in ^[24,25,26].

Theorem 2.3. Let $\{X_n, \, n\geq1\}$ be a sequence of NSD random variables satisfying

Let $\{d_n, n\geq1\}$ be a sequence of positive constants satisfying $d_n\uparrow\infty$, and $\{c_n, n\geq1\}$ be a sequence of positive constants such that $c_j\geq1$ and

Then for $p\in(1, \alpha)$,

where $\widehat{X_{nj}} = -d_nc_j\mathbb{I}(X_j < -d_nc_j)+X_j\mathbb{I}(|X_j|\leq d_nc_j)+d_nc_j\mathbb{I}(X_j > d_nc_j)$, $1\leq j\leq n$.

3.   The proofs

Proof of Theorem 2.1. We first observe that for every $\varepsilon > 0$,

To prove Eq (2.3), we need only to show that $H_i\rightarrow0$ as $n\rightarrow \infty$, $i = 1, 2$. For $H_1$, we have by the definition of $X_{nj}$, $C_n = o(D_n)$, Eqs (2.1) and (2.2) that

For fixed $n\geq1$, $X_{nj}$ is the nondecreasing function of $X_{j}$. Hence, it follows by Lemma 2.1 that $\{X_{nj}, \, 1\leq j\leq n\}$ is a sequence of NSD random variables. Hence we have by Markov's inequality and Lemma 2.3 with $1 < p\leq2$,

The proof is completed.

Proof of Theorem 2.2. Obviously, to prove Eq (2.7), we need only to show

and

By Eq (2.6), $d_n\uparrow\infty$ and the Borel-Cantelli lemma, we obtain

Noting that

Then

which yields Eq (3.1).

It follows by the definition of $\widetilde{X_{j}}$ that

We obtain directly by Eq (2.6) that $I_2 < \infty$. Let $F(x)$ be the distribution of $X_1$, then

Define $N(|x|) = \sharp\{j:\, \varphi(j) < |x|\}$ and $j_* = \inf\{j:\, \varphi(j)\geq|x|\}$. Hence we can obtain $N(|x|)\geq j_*-1$ and

It follows by Eqs (2.6), (3.3) and (3.4) that

Now we obtain by $I_1 < \infty$ and $I_2 < \infty$ that

Consequently, by Lemma 2.4 and Eq (3.5), we get

which implies Eq (3.2) by Kronecker's lemma, together with the condition $d_n\uparrow\infty$.

The proof is completed.

Proof of Theorem 2.3. Noting that

To prove Eq (2.10), it is sufficient to prove $J_1\rightarrow0$ and $J_2\rightarrow0$. By Lemma 2.1 and the fact that $\widehat{X_{nj}}$ is the nondecreasing function of $X_{j}$, $\{\widehat{X_{nj}}, \, 1\leq j\leq n\}$ is also a sequence of NSD random variables.

We have by Lemma 2.2 that

By $d_n\uparrow\infty$, Eqs (2.8) and (2.9), we have

Now we will show $J_3\rightarrow0$. Observing

Let $t = u^2$, then

From Eq (2.8), we know that, there exists $M > 0$ and $N_0\in {\mathrm{\textbf{N}}}$ such that

Since $d_n\uparrow\infty$ and $c_j\geq1$, while $n$ is sufficiently large, we can obtain $d_nc_j > N_0$. Hence

By $\alpha < 2$, $c_j\geq1$ and Eq (2.9), we have

and

Finally, we need only to show $J_2\rightarrow0$ as $n\rightarrow \infty$. Let

We first prove that

Observing

By Eq (3.7) and $\alpha > 1$, we have

and

which yields Eq (3.8). Therefore, we obtain by Lemma 2.3 that

By similar arguments as in the proof of Eq (3.8), we can obtain

Then

By similar arguments as the proof of $J_4\rightarrow0$, we obtain $J_2'\rightarrow0$. We also have by Eq (3.7), $p < \alpha$ and Eq (2.9) that

The proof is completed.

4.   Conclusions

In this work the author investigated the limit theorems for negatively superadditive-dependent random variables, and obtained some new results on the law of large numbers and mean convergence under some appropriate conditions. As a future work, we propose to consider some other strong convergence for sequence of negatively superadditive-dependent random variables.

Use of AI tools declaration

The author declares he has not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is supported by the Social Sciences Planning Project of Anhui Province (AHSKY2018D98).

Conflict of interest

The author declares that he has no conflict of interest.