I Introduction
A geometric sequence is a series of numbers in which the ratio between any two consecutive terms is fixed. Recall that a geometric sequence is expressed by
where is the initial term and is the common ratio of the sequence. Depending on the common ratio, the geometric sequence can increase, decrease, or remain constant as it progresses. The sequence may also oscillate in the complex plane if the common ratio is a complex number.
Consider geometric sequences with nonidentical common ratios, . Then, assume that we have no information about the individual sequences but we can only observe a superposition of geometric sequences :
Let us pose an interesting question as follows:

How can we decompose a superposition of geometric sequences into the individual sequences in a computationallyefficient manner?
To answer the question, firstly the number of superposed sequences should be estimated. Secondly, the parameters of each sequence, i.e. the initial term and the common ratio, should be recognized.
The foremost contribution of this paper is to propose a new technique addressing the aforementioned problem. The main idea is to transform the observed sequence to a dimensional space. For this, we bring in a wellknown concept in geometry, simplex [1]. A simplex is a dimensional polytope which is the convex hull of its number of vertices. For example, a simplex means a tetrahedron in a threedimensional space. By using the concept, we develop a method which we term geometric sequence decomposition with simplexes transform (GSDST). Our method turns the complicated problem of decomposing geometric sequences into a simple rootfinding of a th order polynomial equation. The GSDST requires only samples of the superposed sequence to estimate the number of geometric sequences, , and to retrieve the parameters of each sequence. The required samples further reduce to if is known a priori.
The proposed GSDST is not only an intriguing mathematical trick, but it also has significance to wireless communications. This is because a sampling of a radio wave is indeed a geometric sequence. A radio wave is normally represented by a complexvalued function, simply in a form of , where denotes the constant value accounting for the amplitude and phase, and and are the frequency and the time, respectively. One can notice that a sampled progression of a radio wave with time interval makes a geometric sequence with the initial term of and the common ratio of . This means that, if we can decompose a superposition of geometric sequences, we can also separate multiple incoming radio waves that are nonorthogonally accumulated. Therefore, our work lays the foundation for new ways of handling wireless signals in the interferencelimited environments.
Ia Related Works
Interference is a phenomenon that multiple waves superpose to form a resultant wave of amplitude and phase. It is common in various fields dealing with waves, and thus extensive studies have been conducted to extract the desired wave or to separate all the accumulated waves. These include blind sound source separation in acoustics [2, 3], target detection in radar systems [4, 5], and wireless communications [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17].
In the wireless communication systems, the interference has been traditionally managed by orthogonalizing the signals. Intuitively, one of the easiest approaches to the orthogonality is to coordinate the multiple waves in the time domain. Thus, the timedivision multiplexing (TDM) remains as the basic principle of user scheduling in cellular networks [6, 7] and collision avoidance in WiFi systems [8, 9]. In the frequency domain, the orthogonal frequencydivision multiplexing (OFDM) has become a key element of modern broadband systems such as the IEEE 802.11 family [10, 11] and Long Term Evolution (LTE) [12].
The scarcity of radio spectrum forced the researchers to go beyond the orthogonal division of radio resources. Further, the stringent requirements of high data rate and low latency in 5G magnify the need. So, there have been numerous attempts to deal with nonorthogonal accumulation of radio waves. If we confine the discussion to the radio access where the challenge is to accommodate multiple uncoordinated requests with ultralow latency, nonorthogonal multiple access (NOMA) has been considered a practical solution [13, 14, 15, 16, 17]. This technique separates the multiple signals in the power domain by means of iterative decoding. This means that NOMA relies on the difference between the powers of received signals. Thus, its effectiveness becomes limited as the number of accumulated signals increases and the power difference decreases.
If a new method is available that can separate several randomly superposed radio waves regardless of the distribution of the received powers, it will be a powerful tool of designing radio access schemes for ultralow latency. We will demonstrate that the proposed GSDST is a strong candidate.
IB Main Contributions
Our objective is to decompose a nonorthogonal superposition of geometric sequences into the original sequences without information loss when we can only observe the superposed sequence. The superposition is a onedimensional progression, but it contains the information about sequences. Thus, we depart from an intuition that a proper transformation of the observed sequence to a dimensional space may facilitate the analysis of the overlap of geometric sequences. We develop the idea further with the concept of simplex, and propose the GSDST method. We will provide a simple numerical example and the formal methodology of GSDST in the subsequent sections.
Consider a superposed sequence . The GSDST has the three main ingredients for the decomposition of :

Set of vertices from : this is a search space in a dimensional space, which is constructed from the elements of . For an arbitrary , we compose the following two different types of simplexes using this set of vertices.

A series of basic simplexes: this is a series of simplexes made from the set of vertices from to represent the characteristics of in a dimensional space. We will prove that the volumes of the basic simplexes constitute a single geometric sequence if and only if is the superposition of geometric sequences. This property enables us to estimate the number of superposed sequences, .

Quotients of volumes of combinatorial simplexes: once is estimated, we pick two consecutive basic simplexes to construct number of simplexes, named combinatorial simplexes. Then, we establish a polynomial equation whose coefficients are the quotients of the volumes of the combinatorial simplexes. We will prove that the roots of the equation are the common ratios of the original geometric sequences.
The entire process of GSDST requires only samples of . However, it may be prone to the effect of noise in practice. Thus, we also provide a practical denoising technique which utilizes more samples than the minimum requirement.
As discussed earlier, the decomposition of geometric sequences is equivalent to the separation of nonorthogonally overlapping radio waves. To exemplify the potential of GSDST for wireless communications, we introduce a new radio access scheme, namely nonorthogonal interferencefree radio access (NoINFRA), which allows multiple transmitters to randomly select frequencies in a continuous domain within a given signal bandwidth and to transmit simultaneously. Then, the receiver samples the mixed signal and decodes all the information with the GSDST. Contrary to the orthogonal resource division which inevitably suffers from the collisions of access requests, the NoINFRA enjoys the collisionfree access by eliminating the notion of interference.
In summary, our main contributions in this study is threefold; first, we propose a new method of GSDST for the decomposition of nonorthogonally superposed geometric sequences; second, we provide the formal methodology consisting of theorems and proofs to sustain the GSDST method; third, we introduce a new radio access scheme of NoINFRA to demonstrate how the GSDST can be applied to wireless communications.
IC Organization of the Paper
The remainder of this paper is organized as follows. In Section II, we provide a numerical example of GSDST to help the readers understand the new method. Section III presents the formal methodology of GSDST accompanied by the necessary theorems and a practical denoising process. This is followed by Section IV where we propose the NoINFRA scheme. In Section V, the performance of NoINFRA is compared with a conventional scheme of orthogonal resource division. Finally, Section VI presents the concluding remarks.
ID Notations
The following symbols will be used throughout the paper.

: an arbitrary sequence with length whose th element is .

: the number of superposed geometric sequences.

: the th geometric sequence.

: the initial term of , ().

: the common ratio of , ().

: the sequence made up of overlapping geometric sequences.

(): an arbitrary collection of lexicographically ordered indices, e.g. .

: the vertex in dimensional space, which is made by different samples of an arbitrary sequence sketched by .

: a function that returns the simplex by connecting the () number of vertices which consists of the origin and the given number of vertices, , in a dimensional space.

: a function that returns the volume of the simplex [18], i.e. . In addition, if the input is a series of simplexes, this function returns the series of volumes of each simplex as an output.
Ii A Simple Example of GSDST
In this section, we provide a numerical example to help the readers understand the new concept of GDSST. Consider the following three geometric sequences where is the length of the sequences:
Then, suppose that we have no information about the three sequences and we can only observe their superposition, , i.e.
Our objective is to estimate how many sequences are superposed and to obtain the parameters of each sequence.
Iia Estimation of the Number of Sequences
Let be the true number of the superposed geometric sequences, and be an estimate of . Theorem 1 in Section III states that the volumes of successively generated simplexes make a nonzero geometric sequence if and only if .
For the case that , we consider a two dimensional space where we generate 2simplexes, i.e. triangles, from the origin and consecutive values of . Let us create three triangles, namely , , and with the following coordinates:
where is the transpose of an input. Then, we examine whether the volumes of the triangles, , constitute a geometric sequence. Since , , and , it does not make a geometric sequence. Thus, we conclude that .
For the case of , we increase the dimension by one and consider 3simplexes, i.e. tetrahedrons. We create three tetrahedrons denoted again by , , and with the following coordinates:
This time, , , and , which is a geometric sequence with the common ratio of . Therefore we confirm that is a superposition of three geometric sequences.
For the greater than 3, one can easily verify that the volumes of simplexes always constitute a sequence of zeros.
IiB Obtaining Parameters of Each Sequence
Given that is correctly estimated, we can fully extract the original sequences with sampling of . The procedure is divided into five steps.
First, we pick consecutive elements from . Second, considering a dimensional space, place vertices whose coordinates are basic elements of . In this example, 4 vertices are created with the coordinates of
Third, choose out of vertices shown above. By including the origin, we can create different simplexes in the lexicographically ordered manner. This corresponds to 4 tetrahedrons in this example with the following coordinates:
Fourth, let denote the volume of th tetrahedron. Surprisingly, the following relationship holds by Theorem 2 in the next section:
Notice that these are the coefficients of a polynomial whose roots are , , and . Therefore, the common ratios of the geometric sequences can be obtained by solving the polynomial equation as below:
Finally, once the common ratios of the sequences are obtained, we can extract the initial terms by solving a simple linear system of equations.
It should be emphasized that this section illustrated a simplified example of the GSDST. The formal methodology of GSDST is more general that, for example, the required samples do not need to be consecutive.
Iii Methodology of GSDST
This section provides the general methodology of GSDST. The overall concept of GSDST is depicted in Fig. 1.
Iiia Set of Vertices to Construct the Search Space
For any two different vertices, and , we will say that they are indexdependent if they satisfy where is the index interval. Simply, if and , then and , are indexdependent. Otherwise, we will call they are indexindependent. In addition, let be the set of all vertices from that are indexindependent of one another. Now, we can construct a different search space for each vertex, , as follows.
Definition 1.
For an arbitrary , let a dimensional search space, , be the lexicographically ordered collection of all the possible vertices which are indexdependent to .
In other words, is the set of vertices which is formed by successively creating a new vertex at index intervals of starting from . This means that indexindependent vertices provide different search spaces. By the definition of geometric sequence, is a polynomial of degree consisting of the initial terms of degree one and the common ratios of degree . Thus, according to the Definition 1, the volume of any simplex made by the origin and consecutive vertices in , i.e. , becomes a homogeneous polynomial whose degree is determined by , , , and . This property of algebraic geometry supports the approaches in the following subsections.
IiiB Series of Basic simplexes to Estimate the Number of Superposed Geometric Sequences
In this subsection, we will estimate the number of superposed geometric sequences, .
For this, let us firstly look at an interesting property of the search space .
Definition 2.
Let be a series of basic simplexes for given , , and , where the th basic simplex is denoted by
Recall that denotes a series of volume of basic simplexes.
Lemma 1.
is a geometric sequence whose common ratio is .
Proof.
Regardless of , we can extract the following polynomial from each element of :
where is the th degree polynomial of which is independent of .
Consequently, for any , both th and th elements of are expressed as follows:
(1) 
(2) 
where . Based on (1) and (2), the following condition is satisfied for any :
(3) 
Thus, we can verify that is a geometric sequence. ∎
It is an interesting and useful property that nonorthogonally superposed geometric sequences can be transformed into a single geometric sequence. The fact that is a geometric sequence, regardless of and , can be utilized for the estimation of .
Theorem 1.
is a nonzero geometric sequence if and only if is .
Proof.
Lemma 1 provides that is a nonzero geometric sequence if is . In addition, we show its inverse as below:

[label=)]

: if an arbitrary sequence is a geometric sequence, then the following holds for any :
Thus, we can easily verify with a simple calculation that

: simplexes cannot be represented by number of linearly independent bases, and so the corresponding volumes become zero, i.e. is an allzero sequence.
∎
Next, we derive the minimum number of samples to estimate , i.e. the minimum required .
Corollary 1.
For given , the minimum required to estimate is .
Proof.
First, set to . Next, with the increment of , set in Theorem 1. ∎
IiiC Combinatorial simplexes to Extract Initial Terms and Common Ratios
After estimating in the observed sequence, we can specify the search space for extracting and .
Definition 3.
For an arbitrary , let the th series of combinatorial simplexes, , be the output of the following process:

[label=)]

Fix the search space to and construct over .

Pick any two consecutive basic simplexes such as and in .

Paste these two simplexes to create a new polyhedron having vertices, which we call the th union polyhedron ^{1}^{1}1These two consecutive basic simplexes can be attached because they share the coface made by number of vertices based on the definition of ..

Extract lexicographically ordered number of simplexes out of the th union polyhedron.
We further define the volume quotients of combinatorial simplexes with the th union polyhedron, , as follows:
(4) 
Theorem 2.
For given , is unique regardless of and .
Proof.
For , is given by
where
is independent of , and it is included in for any . Thus, can be derived as follows:
(5) 
Therefore, all possible are identical to each other. ∎
By Theorem 2, is unique for given , and thus can be simplified as . This uniqueness is a strong property because it implies that all of search spaces contain the same information regardless of the selection of the initial vertex. Based on the information of , we can make a polynomial equation for as follows:
(6) 
The roots of (6) are the common ratios which we look for. In addition, the minimum number of samples for extracting can be described as below.
Corollary 2.
Given , the most compact sampling for extracting is to take consecutive samples of sequence .
Proof.
Set in Theorem 2. ∎
After estimating , it is trivial to obtain by the simple matrix pseudoinversion: , where is the matrix constructed by satisfying for , and is the pseudoinverse operation. Each pair of initial term and common ratio is matched through this matrix operation, and thus there is no paring problem between the initial terms and the common ratios.
In summary, starting from an arbitrary vertex, , we estimate the number of superposed geometric sequences by verifying that a series of volume of basic simplexes, , is a geometric sequence. Then, we obtain common ratios, , through the volume quotients of combinatorial simplexes, . Finally, initial terms, , are obtained by a simple matrix operation.
Let the method of GSDST be denoted by . Then,
(7) 
where is a nonlinear function including the entire process of estimating and extracting . In addition, we define the inverse of GSDST, , as follows:
(8) 
Based on Corollary 1 and Theorem 2, is equivalent to when and . Algorithm 1 summarizes the steps of GSDST consisting of two phases: estimation of and extraction of and .
IiiD GSDST with Noisy Samples
So far, we have assumed that the observation of is flawless. However, the observed sequence may be prone to noise particularly in wireless communications. Thus, we present the practical ways of mitigating errors in in this section. Let us define such that
where
denotes a sequence of random variables representing additive white Gaussian noise (AWGN). The fundamental approach of the denoising process is to utilize more samples than the minimum requirement, i.e. to consider
.IiiD1 Estimation of the number of sequences with noise
We can design an approximated algorithm to estimate by utilizing Theorem 2, i.e. all possible are identical when and . To extract the informative part of , is defined as since for any , where is the operator of set minus.
Now, we will use the wellknown method based on Euclidean distance to check the similarity among the all possible . Let and be two different among the all possible cases. Then, the similarity function is defined as follows:
(9) 
where is the Euclidean norm of an input. Let be minimizing and we will determine it as . Here, is the upper bound of , which corresponds to where is the operator of floor calculation. For given , denotes the number of all possible , . Thus,
is the geometric mean of the similarity values for all possible
. Consequently, if and , then goes to zero.Let be the number of Euclidean distances to be computed. It is given by
(10) 
The computation of is demanding for a large number of . Thus, we define two simplified similarity functions, and , as follows:

[label=)]

,

.
The simplification for comes from fixing as in (10). Furthermore, is the simplest way that executes only one calculation of Euclidean distance with an arbitrary and .
IiiD2 Extraction of initial terms and common ratios with noise
The denoising of is essentially a process of separating and . Here, is an indexwise correlated sequence with of parameters of interest, whereas is a sequence of random variables. We focus on the fact that has number of nonidentical bases. Further, each basis is made by only one parameter, i.e. the common ratio, from the nature of geometric sequence. From this perspective, the denoising of can be handled by suppressing of the number of bases for to .
Thus, we utilize the iterative
truncated singular value decomposition (SVD)
[19] for only taking the largest singular values and their corresponding vectors. Let be the denoised sequence which is the output of the following process:
[label=)]

Make a matrix, , from satisfying the condition:
where .

Execute truncated SVD of .

Reconstruct using tuples of the singular values and vectors.

Transform onto a new by averaging the values with the same index, i.e.
where if , and otherwise.

Repeat the above fourstep process with the stopping criterion until converges to .
The above denoising process for is equivalent to making the bases of for both row space and column space identical to each other, aiming to minimize the number of parameters in . Then, we extract and by using . Algorithm 2 summarizes the process of GSDST with noisy samples.
Iv Application of GSDST to Nonorthogonal Interferencefree radio Access
Iva Potential of GSDST for Wireless Communications
The ability to decompose geometric sequences opens up a new possibility of separating the nonorthogonally superposed radio waves. This means that, even if the overlapping radio waves are not linearly orthogonal, they can be decomposed as if there were no interference through just sampling with a rate faster than the highest frequency component. Theoretically, GSDST enables the infinitely many users to share a limited bandwidth if each user randomly picks its frequency.
To harness this advantage, we propose a novel technique, namely NoINFRA, as an application of GSDST to radio access networks. It strives to eliminate the effect of collisions of multiple access attempts by letting each user randomly select its frequency within a limited bandwidth and by employing GSDST for the demodulation process. The following onetoone correspondences between GSDST and NoINFRA hold, and thus we will use these terms interchangeably.

Number of geometric sequences () Number of signals containing independent messages.

Nonorthogonally superposed geometric sequences with noise () Sampled signal at the receiver.

Initial term of the th geometric sequence () Symbol of the th message.

Common ratio of the th geometric sequence () Subcarrier carrying the th messages.
IvB Design of NoINFRA
Let denote the frequency of the transmitted signal of the th transmitter. We consider that
follows the uniform distribution,
, for any , where and are the symbol duration and signal bandwidth, respectively. Each transmitter uses a single subcarrier to deliver information. For a continuous time duration , the baseband signal of the th transmitter, , can be expressed as: . Here, is a modulated symbol containing the information transmitted by the th baseband signal, where . Then, for a discrete sampling domain , the discrete baseband sequence at the receiver is given by(11) 
where and are the sampling interval and the number of samples, respectively. In addition, is the factor of power attenuation from the th transmitter to the receiver, and we assume that it is known to the receiver. The factor of power attenuation and modulated symbol, i.e. and , are integrated into the initial term of the th sequence, . Further, and are integrated into the common ratio of the th sequence, . The procedure for NoINFRA is described in Algorithm 3.
V Performance Analysis
In this section, we evaluate the performance of the proposed NoINFRA mainly in terms of symbol error rate (SER). The result is based on Monte Carlo simulation experiments. We assume that the symbol duration and the signal bandwidth are 1 msec and 30 kHz, respectively. Also, we set that the sampling rate at the receiver is equivalent to the signal bandwidth, i.e.
. Furthermore, we assume that the signaltonoise ratio (SNR) of each signal follows a normal distribution,
, in dB scale.Va Effect of Denoising Process
Firstly, we examine the impact of the denoising process on the performance of GSDST. Fig. 2 shows the performance of denoising in terms of normalized mean square error (NMSE) between the original sequence and the observed/reconstructed sequences when is known. We set to zero, which means that all sequences undergo the same . The convergence speed of denoising is also presented to indicate its complexity. Each transmitter picks the frequency of subcarrier through a continuous uniform distribution in the range . We set the stopping criterion () and the maximum number of iterations () as and 30, respectively.
Fig. 1(a) suggests that the denoising is an appropriate preprocessing of the GSDST. Notice that the NMSE of the observed sequence is inverseproportional to the SNR. As expected, reconstruction of the sequence through GSDST incurs more errors without the denoising. Conversely, the denoising makes the reconstructed sequence even closer to the original one. The gap between the GSDST with denoising and the observed sequence remains almost constant regardless of , which indicates that the denoising is effective in the whole range of SNR. Hence, we will keep employing the denoising in the subsequent experiments.
The computational complexity required for denoising is derived as based on the complexity of truncated SVD [20], where and is the number of iterations. Thus, the distributions of for different values are shown in Fig. 1(b) to represent the complexity of denoising and its convergence tendency. It is observed that the denoising converges faster in high SNR regime. When , the denosing process fails to converge for 9.35 of the cases. On the contrary, the denoising finishes in a relatively short time for high SNR, e.g. 11.33 iterations when .
VB Comparison with Conventional Scheme in Random Access
In this subsection, the SER performance of NoINFRA is shown as functions of the SNR distribution (), the number of transmitters (), and the modulation order () under the assumption that is known. In our simulation, quadrature amplitude modulation (QAM) is adopted for modulation. For a performance comparison, we choose an orthogonal random access with successive interference cancellation (ORA+SIC) [15, 16]
. It consists of two steps for demodulation: the fast Fourier transform (FFT) in the time domain and the SIC in the power domain. The same symbol duration and the signal bandwidth as NoINFRA yield 30 orthogonal subcarriers. However, even a few transmitters may experience interference due to collisions inevitably incurred by the uncoordinated nature of random access. For the case of collision, SIC is employed to reduce the SER.
Fig. 3 illustrates the SER of the NoINFRA and the ORA+SIC schemes with regard to under the setting of and . This figure shows that the performance of ORA+SIC is saturated even in the high SNR regime. In the case of , the average signaltointerferenceplusnoise ratio (SINR) is about 0 dB if a collision occurs. Thus, no matter how large the value of , the interference between signals remains dominant, resulting in the saturation of SER performance. It is obvious that this tendency is more severe for the case of where the average SINR is almost 5 dB. Contrarily, NoINFRA shows the excellent SER performance over a region where interference is dominant compared to noise. That is, NoINFRA responds more strongly to weaker noise power than ORA+SIC. Therefore, despite the poor average SINR, the SER of NoINFRA exhibits a linear decline in the loglog scale as increases. NoINFRA starts to outperform ORA+SIC at when . Furthermore, when , NoINFRA shows superior performance in the interval of , and the gap becomes wider as increases.
Next, the SER of NoINFRA and ORA+SIC is depicted in Fig. 4 regarding with the fixed . When , NoINFRA outperforms ORA+SIC regardless of . In addition, when , NoINFRA shows higher performance than ORA+SIC when the dispersion of between the transmitters is relatively small. With the increment of , the received powers fluctuate more, which gives NOMA higher opportunity to be effective. However, from , the SER of ORA+SIC worsens because the SINR of the weaker transmitter tends to be insufficient, thus ending up only demodulating the stronger one. In fact, this phenomenon also occurs to NoINFRA. Since the largest singular values are selected during the denoising process, the increment of forces the small singular values to be buried in the noise.
Fig. 5 shows that NoINFRA is more robust to the increase in the number of transmitters than ORA+SIC. In most cases NoINFRA has superior performance in terms of SER. When , NoINFRA gives lower SER than ORA+SIC on average. In addition, NoINFRA shows about of SER when , even though it takes only 30 samples and the average SINR is almost dB. On the other hand, ORA+SIC gives the SER of in the same environment.
Next, we compare the SER of the NoINFRA and ORA+SIC schemes under the variation of modulation order, , in Fig.
Comments
There are no comments yet.