{'fraction_non_alphanumeric': 0.04487445528117867, 'fraction_numerical': 0.012372898941689147, 'mean_word_length': 4.654590789087709, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Over-the-Air Computation via Reconfigurable Intelligent Surface

Over-the-air computation (AirComp) is a disruptive technique for fast wireless data aggregation in Internet of Things (IoT) networks via exploiting the waveform superposition property of multiple-access channels. However, the performance of AirComp is bottlenecked by the worst channel condition among all links between the IoT devices and the access point. In this paper, a reconfigurable intelligent surface (RIS) assisted AirComp system is proposed to boost the received signal power and thus mitigate the performance bottleneck by reconfiguring the propagation channels. With an objective to minimize the AirComp distortion, we propose a joint design of AirComp transceivers and RIS phase-shifts, which however turns out to be a highly intractable non-convex programming problem. To this end, we develop a novel alternating minimization framework in conjunction with the successive convex approximation technique, which is proved to converge monotonically. To reduce the computational complexity, we transform the subproblem in each alternation as a smooth convex-concave saddle point problem, which is then tackled by proposing a Mirror-Prox method that only involves a sequence of closed-form updates. Simulations show that the computation time of the proposed algorithm can be two orders of magnitude smaller than that of the state-of-the-art algorithms, while achieving a similar distortion performance.


I. INTRODUCTION
Driven by the increasing advancement of wireless communication technologies and the decreasing manufacturing costs, Internet of Things (IoT) is expected to support ubiquitous connectivity and automatic transmission for billions of devices equipped with sensing and communication capabilities [2]. With limited spectrum resources, it is generally challenging to achieve efficient wireless data aggregation over a large volume of IoT devices, which is critical for unleashing the potential of the distributed sensory data. The conventional "transmit-then-compute" approach requires an access point (AP) to successfully receive the data from each IoT device and then compute a specific function (e.g., arithmetic mean) of the received data. This is, however, not spectrum-efficient, especially when the number of IoT devices is large. Fortunately, over-theair computation (AirComp), which integrates the communication and computation processes, has the potential to achieve ultra-fast wireless data aggregation in IoT networks. This is accomplished by enabling the concurrent data transmissions from all IoT devices over the same radio channel and exploiting the waveform superposition property of multiple-access channels (MACs) at the AP [3], [4], yielding a revolutionary paradigm of "compute when communicate".
The study of AirComp can be traced back to the seminal work [5], which showed that a fast function computation can be achieved by enabling concurrent analog transmissions. There is a growing body of studies concentrated on the transceiver design for AirComp to enable efficient wireless data aggregation [6]- [10]. In particular, the authors in [6], [7] proposed optimal transmit power control strategies for AirComp in single-input single-output (SISO) wireless networks with energy-constrained IoT devices. The authors in [8] studied AirComp in multiple-input single-output (MISO) wireless networks, where a novel uniform-forcing transmit design was proposed to compensate the non-uniform channel fading among IoT devices. By integrating multiple-input multiple-output (MIMO) with AirComp, the authors in [9] and [10] investigated the transceiver design for multi-function computation and multi-modal sensing, respectively.
Meanwhile, the authors in [11] proposed a blind MIMO AirComp scheme to reduce the signaling overhead for channel state information (CSI) estimation. By calibrating the transmission timing of each IoT device, the synchronization issue of AirComp can be addressed. In case of nonstrict synchronization, the authors in [12] proposed an efficient matched filtering and sampling scheme to facilitate misaligned AirComp. More recently, the authors in [13]- [15] exploited the advantages of AirComp to develop a fast model aggregation scheme to accelerate the convergence of federated learning. According to the aforementioned studies, AirComp requires the magnitudes of the signals to be aligned at the AP; thus, the performance of AirComp is bottlenecked by the worst channel between the IoT devices and the AP.
Reconfigurable intelligent surface (RIS) is an emerging technology, which has recently been proposed to tackle unfavorable channel conditions by reconfiguring the radio propagation environment [16]- [26]. An RIS is a man-made flat surface composed of many passive reflecting elements, each of which can independently shift the phase of the impinging waves in a controllable way [16], [17], thereby constructing a favorable wireless radio propagation environment.
The authors in [18]- [20] demonstrated that RIS has the ability to significantly enhance the energy efficiency and spectral efficiency of wireless networks. Owing to the aforementioned features, RIS has been integrated with various wireless technologies, e.g., non-orthogonal multiple access (NOMA) [21], massive IoT device connectivity [22], massive MIMO [23], millimeter-wave communications [24], unmanned aerial vehicle communications [25], and wireless power transfer [26], to further enhance the network performance and promote emerging applications.
To leverage the advantages of RIS for enhancing the quality of the worst channel between the IoT devices and the AP and in turn mitigating the performance bottleneck of AirComp, the authors in [1], [27] proposed an RIS-assisted AirComp system. In these two studies, the alternating semi-definite relaxation (SDR) algorithm and the alternating difference-of-convex (DC) algorithm were proposed to jointly optimize the receive beamforming vector at the AP and the phase-shift matrix at the RIS. However, both algorithms suffer from high computational complexity as they need to iteratively solve the semi-definite programming (SDP) problems.
Moreover, the optimization of the phase-shift matrix in [1], [27] involves feasibility detection that cannot be accurately tackled by the SDR and DC algorithms. Hence, both algorithms are not guaranteed to achieve monotonic convergence. This motivates us to develop a computationally efficient algorithm with convergence guarantee to achieve efficient wireless data aggregation in RIS-assisted AirComp systems.

A. Contributions
In this paper, we consider an RIS-assisted IoT network, where a multi-antenna AP aggregates the sensory data from multiple IoT devices by using AirComp with the assistance of an RIS. We evaluate the performance of AirComp in terms of the computation distortion, which is measured by the mean-squared-error (MSE). The main objective is to develop a low-complexity algorithm with convergence guarantee to minimize the MSE of RIS-assisted AirComp systems. To this end, it is necessary to jointly optimize the transmit scalars at the IoT devices, the receive beamforming vector and the denoising factor at the AP, and the phase-shifts at the RIS. The main contributions of this paper are summarized as follows: • We formulate an MSE minimization problem for RIS-assisted AirComp systems, where the transmit scalars at the IoT devices, the receive beamforming vector and the denoising factor at the AP, and the phase-shift matrix at the RIS are jointly optimized. To tackle the scalability and convergence issues of existing studies, we transform the original problem into an equivalent min-max optimization problem. It turns out to be a highly intractable non-convex optimization problem due to the non-convex objective function and the coupled optimization variables.
• We propose an alternating minimization (AlterMin) framework to alternately optimize the receive beamforming vector and the phase-shift vector. For each optimization problem in the alternating procedure, we iteratively construct a convex surrogate for the non-convex objective function by utilizing the successive convex approximation (SCA) technique. We prove that the proposed framework is guaranteed to converge, which is a key difference from the existing studies. As the subproblem in each SCA iteration is a non-smooth convex problem, the conventional algorithms suffer from high computational complexity.
• As the objective function involves the pointwise maximum of affine functions, we equivalently transform the resulting non-smooth convex problem into a smooth convex-concave saddle point problem by using the primal-dual transformation. Subsequently, we adopt the Mirror-Prox method to solve the aforementioned saddle point problem and derive a closedform expression for each update. As a result, the proposed Mirror-Prox based AlterMin SCA algorithm enjoys a very low computational complexity.
We conduct extensive simulations to demonstrate the monotonic convergence and the superior performance of the proposed algorithm for RIS-assisted AirComp systems. Results will show that the computational time of the proposed algorithm can be two orders of magnitude smaller than that of the alternating SDR and alternating DC algorithms [1], [27], while achieving a similar data aggregation distortion performance in terms of MSE as these state-of-the-art algorithms.
Moreover, the performance gain of the proposed algorithm in terms of the computation time increases when the dimensions of the system parameters (e.g., number of IoT devices, AP's antennas, and RIS's reflecting elements) become larger.

B. Organization and Notations
The reminder of this paper is organized as follows. Section II describes the system model and the problem formulation. Section III presents an AlterMin SCA framework for solving the formulated problem. Section IV provides the Mirror-Prox method to solve the subproblems in each SCA iteration. The performance of the proposed algorithm is illustrated in Section V.
Finally, we conclude this paper in Section VI.
Notations: Matrices, vectors, and scalars are denoted by boldface upper-case, boldface lowercase, and lower-case letters, respectively. (·) H and (·) T stand for conjugate transpose and transpose of a matrix or a vector, respectively. · 1 , · , and · ∞ denote the l 1 , l 2 , and l ∞ norm operators, respectively.
[·] and [·] represent the real and imaginary parts of a complex matrix, vector, or scalar, respectively. E [·] denotes the expectation of a random variable.

II. SYSTEM MODEL AND PROBLEM FORMULATION
In this section, we first present the system model of an RIS-assisted AirComp system and formulate an AirComp distortion minimization problem that requires the joint optimization of the transmit scalars at the IoT devices, the receive beamforming vector and the denoising factor at the AP, and the phase-shift matrix at the RIS. Subsequently, we discuss the limitations of the existing methods, which motivate us to reformulate an equivalent min-max optimization problem.

A. System Model
We consider the uplink transmission of an RIS-assisted single-cell IoT network consisting of K single-antenna IoT devices, an AP with M antennas, and an RIS equipped with N passive reflecting elements, as shown in Fig. 1. We denote K = {1, 2, . . . , K} as the index set of IoT devices. We consider the scenario that the AP, as a fusion center, is interested in receiving an aggregation (e.g., geometric mean, arithmetic mean) of the sensory data (e.g., temperature, humidity) from all IoT devices, rather than the individual data from each IoT device [9]. This process is generally referred to as wireless data aggregation in IoT networks. By integrating the computation and communication processes via exploiting the waveform superposition property of MACs, AirComp is adopted in this paper to achieve ultra-fast data aggregation by enabling concurrent transmissions from multiple IoT devices. We denote z k ∈ C as the representative information-bearing data at IoT device k. Before transmission, IoT device k normalizes data z k as information symbol s k ∈ C. Without loss of generality, we assume that {s k } K k=1 have zero mean and unit power, and are independent of each other, i.e., [7]. The target function that the AP aims to recover is the summation of the data from all IoT devices, i.e., Based on the principle of AirComp, we assume that all IoT devices are synchronized and transmitted concurrently to the AP [9]. With universal frequency reuse, the signal received at the AP from all IoT devices is given by where w k ∈ C denotes the transmit scalar of IoT device k, Θ = diag e jθ 1 , e jθ 2 , . . . , e jθ N denotes the diagonal phase-shift matrix of RIS with and h r,k ∈ C N ×1 denote the channel coefficients of the links from device k to the AP, from the RIS to the AP, and from device k to the RIS, respectively, and n ∼ CN (0, σ 2 I M ) is the additive white Gaussian noise (AWGN) with zero mean and variance σ 2 . Each device has a maximum transmit power, denoted as P . Hence, we have |w k | 2 ≤ P, ∀ k ∈ K. As various effective channel estimation methods have been proposed for RIS-assisted wireless networks [28], [29], we assume that perfect CSI is available in our work, as in [1], [18]- [27]. Besides, we consider block-fading channels, where the channel gain of each link remains invariant within one time slot but varies independently across different time slots. The estimated function at the AP is given by [13] where m ∈ C M and η denote the receive beamforming vector and the denoising factor at the AP, respectively.
We adopt MSE to measure the distortion between the estimated function (i.e.,ĝ) and the target function (i.e., g), which quantifies the performance of AirComp, given by Motivated by [8], [9], [30], we adopt the following zero-forcing design 1 to determine the transmit scalars of IoT devices Due to the maximum transmit power constraint of IoT devices, i.e., |w k | 2 ≤ P , η can be set as Therefore, the MSE at the AP can be further written as The MSE given in (7) is determined by the transmit signal-to-noise ratio (SNR) P σ 2 , the receive beamforming vector m at the AP, and the composite channel coefficients h d,k + GΘh r,k , ∀ k. Remark 1. According to (7), the MSE of AirComp is bottlenecked by the worst channel between the IoT devices and the AP. Without RIS, i.e., Θ = 0, the channel quality is only determined by the direct link. In this case, we can only adjust the transmit power of IoT devices to tackle the detrimental effects of severe channel fading and path loss. With the assistance of RIS, the composite channel condition of each link (e.g., h d,k + GΘh r,k ) can be adaptively adjusted by reconfiguring the phase-shift matrix Θ, which is able to enhance the channel quality of the link with the worse channel condition. As a result, the ability of RIS to reconfigure the propagation environment can be exploited to effectively mitigate the performance bottleneck of AirComp.
Our goal is to jointly optimize the phase-shift matrix Θ and the receive beamforming vector m to minimize MSE(m, Θ) in (7). It is formulated as the following problem . Given m and Θ, the equality is achieved when {w k } K k=1 are set according to (5), which enforces k∈K to be zero.

Problem (8) can be equivalently expressed as
Since Θ is a diagonal matrix and h r,k is a vector, we rewrite h d,k + GΘh r,k as h d,k + P is a constant, problem (9) is further equivalent to the following problem in the sense of having the same optimal solution

B. Limitations of State-of-the-Art Methods
Most of the existing studies [1], [21], [27] on the joint design in RIS-assisted wireless networks adopted the alternating SDR and alternating DC algorithms. According to [1], problem (10) can be equivalently transformed to problem (11) as follows Problem (11) can be tackled by alternately solving the following two subproblems and find v where The two non-convex quadratically constrained quadratic programming (QCQP) problems, i.e., (12) and (13), were then converted into two SDP problems with rank-one constraints by using the matrix lifting approach.
An intuitive solution is to apply the SDR technique [31] to convexify the problems by directly dropping the rank-one constraints, yielding the alternating SDR algorithm [27]. As an alternative, based on the fact that the rank-one constraint of a positive definite matrix is equivalent to the zero-difference between the spectral norm and trace norm, a DC technique [32] was proposed to tackle the rank-one constraint, yielding the alternating DC algorithm [1]. The existing studies that adopted the aforementioned framework suffer from two limitations, i.e., non-guaranteed convergence and high computation complexity. Specifically, the optimization of phase-shift vector v involves a feasibility detection problem, i.e., (13). According to the analysis in [33], both the alternating SDR and alternating DC algorithms are not guaranteed to converge. Besides, AirComp is expected to support wireless data aggregation in high-density IoT networks, where the number of IoT devices would be large. However, the aforementioned state-of-the-art methods, i.e., alternating DC and alternating SDR algorithms, are not scalable because of their high computational complexity. Especially for the alternating DC algorithm, a series of SDP problems generated by the SCA technique need to be solved by the standard interior-point method [34] at each alternating iteration. The computation time consumption would be an unaffordable burden when the aforementioned algorithms are applied to solve large-scale optimization problems. The limitations of the existing studies motivate us to develop a low-complexity algorithm with a theoretical convergence guarantee for RIS-assisted AirComp systems.

C. Problem Transformation
To mitigate the aforementioned limitations, in this subsection, we reformulate problem (10) as a min-max optimization problem, which is presented in the following proposition. Proposition 1. Problem (10) is equivalent to the following min-max QCQP problem: Proof. Please refer to Appendix A.
As can be observed from (14), both optimization variables m and v are involved in the objective function. This transformation enables us to eliminate the feasibility detection problem as in [1], and allows us to exploit the monotonicity of the objective function during alternating minimization. Problem (14) is still a challenging non-convex optimization problem. Specifically, solving problem (14) faces the following three challenges. First, the optimization variables v and m are coupled in the objective function. Second, the unit-modulus constraint on v i , ∀ i and the unit receive power constraint on m are non-convex. Third, the pointwise maximum of quadratic terms, i.e., the objective function, is non-convex and non-smooth. To tackle these issues, we shall propose an alternating minimization method in conjunction with SCA to solve problem (14) in the following section.

III. PROPOSED ALTERMIN SCA FRAMEWORK
In this section, we propose an alternating minimization method to alternately optimize the receive beamforming vector m and the phase-shift vector v, resulting in two non-convex subproblems with respect to m and v, respectively. We then construct convex approximations for the two yielded subproblems by using SCA.

A. Phase-Shift Vector Optimization
When the receive beamforming vector m is fixed, problem (14) is reduced to the following subproblem that requires the optimization of phase-shift vector v (15) can be rewritten as For simplicity of algorithm design, we further convert problem (16) from the complex domain to the real domain.
, we obtain the following problem Problem (17) aims to minimize the pointwise maximum of concave quadratic terms. Solving problem (17) is challenging due to the non-convex constraints and the non-convex objective function. In the following, we tackle the non-convex constraint by utilizing the convex relaxation technique. Specifically, we relax the unit modulus constraint toṽ On the other hand, the SCA technique is applied to tackle the non-convexity of the objective In particular, due to the concavity of {ṽ TÃ kṽ −2ṽ T b k − |c k | 2 }, we construct its linear upper bound based on the first-order Taylor approximation as at the n-th iteration. As a result, we have Therefore, at the (n+1)-th iteration, we can replace the non-convex objective function in problem problem (18) is approximated by the following subproblem To efficiently solve problem (18), we resort to iteratively solve its non-smooth convex approximation problem (20).

B. Receive Beamforming Vector Optimization
When the phase-shift vector v is fixed, (14) can be formulated as an optimization problem with respect to the receive beamforming vector m as follows The constraint in (22) is non-convex. According to [35], problem (22) is equivalent to the following problem This is because that the constraint should be met with equality at the optimal point for problem (23). Otherwise, m could be scaled up to reduce the objective value, thereby contradicting the where M = {m | m 2 ≤ 1} and To tackle the non-convexity of the objective function of problem (24), we shall apply SCA to construct its local convex approximation. Due to the similar structure of problem (18) and problem (24), the derivation here is similar to that presented in Section III-A. For completeness, we sketch the main procedures for solving problem (24). Starting from an initial pointm (0) ∈ M, SCA is applied to generate a sequence of solutions {m (n) } as follows. With the approximated solutionm (n) obtained at the n-th iteration, the concave quadratic functionm TH km can be upper bounded by its linear majorization. Specifically, we have the following inequalitỹ By denotingp Then,m (n+1) can be obtained by solving the following non-smooth convex approximation

C. Convergence Analysis
We recall that problem (14) is decomposed into two problems (18) and (24) with respectṽ andm, respectively, which are then alternately solved by using SCA. Finally, we projectṽ to Proof. Please refer to Appendix B.

D. Algorithm Discussion
To efficiently solve problem (14), we still need to design an efficient algorithm to solve problem (20) and problem (26). However, the objective function max k {(p (20) is convex but non-smooth. Intuitively, the subgradient algorithm as a first-order method can be applied. However, it requires O 1 2 iterations to attain an -optimal solution [36]. Besides, the Nesterov's smoothing technique in conjunction with the accelerated gradient algorithm can also be employed to solve problem (20). It attains an -optimal solution with O 1 µs iterations [37], where µ s is the smoothness parameter. Notice that the convergence performance of Nesterov's approach is very sensitive to the smoothness parameter (i.e., µ s ), whose optimal value is, in general, difficult to determine. In addition, by introducing an auxiliary variable s, problem (20) can be equivalently formulated as the following convex QCQP problem Algorithm 1: AlterMin SCA for problem (14) Input: Initial pointṽ Problem (27) can be solved by using the interior-point method [34], which attains an -optimal solution with only O √ N + K log 2(N +K) iterations. However, the time complexity of each iteration is O ((N + K)N 2 + N 3 ) [34]. As problem (20) and problem (26) have a similar form, the above analysis also applies to problem (26). Hence, all of the aforementioned algorithms cannot efficiently solve our problem when the number of optimization variables is large. This motivates us to exploit the underlying structure of problems (20) and (26) to develop a highly efficient algorithm with a fast convergence rate and low iteration cost in the following section.

IV. MIRROR-PROX FOR NON-SMOOTH CONVEX PROBLEMS
In this section, we aim to develop a low-complexity algorithm to solve the non-smooth convex problems (20) and (26). We equivalently convert problems (20) and (26) to the smooth convex-concave saddle point problems by using the primal-dual transformation, and then propose to use the Mirror-Prox method [38] to solve the resulting problems. (

A. Mirror-Prox Method for Non-smooth Convex Problem
where P (n) = p Proof. Please refer to Appendix C.
Different from the Nesterov's smoothing technique discussed in Section III-D, which relies on the smoothness parameter to balance the tradeoff between approximation accuracy and computation efficiency, our proposed method is parameter-free and the resulting smooth saddle point problem (28) is equivalent to the non-smooth problem (20) rather than an approximation. By denoting ψ (n) (ṽ, y) := P (n)ṽ + q (n) T y, solving non-smooth convex problem (28) is equivalent to finding a saddle point for the smooth convex-concave function ψ (n) (ṽ, y) under V × Y.
2) First-Order Optimality Condition: By denoting (ṽ * , y * ) as the saddle point of ψ (n) (ṽ, y), we have The first-order optimality condition [39] of a saddle point for ψ (n) (ṽ, y) is given by By denoting z = ṽ T , y T T and the first-order optimality condition (30) can be rewritten in a more compact form as follows

Lemma 2. The operator F(z) is monotone and L-Lipschitz continuous on space V × Y, where
V is endowed with l 2 norm, Y is endowed with l 1 norm, and the Lipschitz parameter L = Proof. Please refer to Appendix D.
Given the above, problem (28) is equivalent to the following variational inequality problem with monotone and L-Lipschitz continuous operator: Remark 2. F(z) can be regarded as a gradient-type vector field on space V ×Y. The variational inequality F (z * ) T (z − z * ) ≥ 0 is similar to the first-order optimality condition for convex constrained problems, where F resembles the gradient or subgradient. Hence, an intuitive solution is to employ the generalized projected gradient method [40] to solve problem (32). However, the classical gradient-type algorithm cannot monitor the local geometry in the non-Euclidean space [41], thereby, weakening the algorithm performance. This motivates the Mirror-Prox method, which we shall present as follows.
3) Mirror-Prox Method: The Mirror-Prox method was firstly proposed in [38] for solving the Lipschitz continuous variational inequality problem with convergence rate O 1 t . Specifically, at each iteration, the Mirror-Prox method updates z through the following two steps where D (z, z t ) denotes the Bregman distance and γ is a parameter that is determined by the Lipschitz parameter of F(z). According to the analysis in [36], [38], we set γ = 1/ 2 max k { p (n) k } to achieve the desired convergence rate. Besides, the use of Bregman distance D (z, z t ) is to monitor the local geometry for improving the algorithm performance [41]. Specifically, Bregman distance D (z, z t ) is induced by a mirror mapping function Φ(z) : We select the mapping function according to the structure of V ×Y to attain the goal of capturing the local geometry. In our work, Φ(z) : where the first item and the second item are the generally used mirror mapping function for an Euclidean space, like V, and a simplex space, like Y, respectively. As a result, we have Remark 3. The update of the Mirror-Prox method has an additional Step (33b) compared to the mirror descent method that only requires Step (33a). The computation of z t+1 in (33a) is used to find a better direction F z t+1 than the mirror descent method which is further used to update z t+1 , i.e., (33b). This process is illustrated in Fig. 2. The Mirror-Prox method improves the convergence rate from O 1 √ t achieved by mirror descent to O 1 t by using a more accurate update. We will show that the updates of (33a) and (33b) are of low complexity.

4) Implementation Details:
At each iteration of the Mirror-Prox method, we need to efficiently solve two optimization problems (33a) and (33b). Specifically, by introducing a variable w, the update of z t+1 in (33a) can be decomposed into the following three steps [36] It is clear that (36a) is easy to compute. Furthermore, w in (36b) can be obtained in a closed form, since ∇Φ(·) and ∇Φ −1 (·) can analytically be expressed as Subsequently, we show that the solution of problem (36c) also admits a closed form, which involves a projection problem on V × Y. According to (35), we rewrite problem (36c) as where w = [u T , e T ] T . Problem (37) can be decomposed into two independent subproblems with respect toṽ and y, respectively, given bỹ v t+1 = arg miñ Problem (38a) can be considered as a projection problem in an Euclidean space [39]. The optimal (ṽ t+1 ) i , ∀ i, admit the following expression Problem (38b) is a projection problem in a simplex space [36]. The optimal y is given by , otherwise.
The above derivation for problem (33a) can be directly applied to problem (33b). The details of the proposed Mirror-Prox algorithm for solving problem (32) is summarized in Algorithm 2.

B. Mirror-Prox Method for Non-smooth Convex Problem
We next sketch the process of transforming problem (26) to its equivalent variational inequality problem. According to Lemma 1,problem (26) is equivalent to the following problem We denote the Lipschitz parameter of operatorF(z) asL. According to Lemma 2, we haveL = Algorithm 2 can be applied to solve problem (42) by replacing z, p (n) k , and F(z t ) byz,p (n) k , andF(z t ), respectively.

C. Computational Complexity
At each iteration of Algorithm 2, the computation complexity is dominated by Step 2. In Step 2, we take a matrix-vector multiplication to update operator F(·). For the optimization of phase-shift vectorṽ ∈ R 2N , the computation cost of operator F(·) in Step 2 is O(N K). Besides, according to [36], Algorithm 2 can obtain an -optimal solution within O L log(N ) iterations. As a result, the computation complexity of Algorithm 2 is O N KL log(N ) . In a similar manner, we can conclude that the computation complexity is O M KL log(M ) for updatingm. The specific time savings in our problem achieved by the proposed algorithm will be further demonstrated in the following section via simulations.

V. SIMULATION RESULTS
In this section, we present sample simulation results to illustrate the performance of the proposed algorithm for minimizing the MSE of the RIS-assisted AirComp systems.

A. Simulation Settings
We consider a three-dimensional (3D) coordinate system. The AP and the RIS are, respectively, located at (0, 0, 20) meters and (100, 0, 20) meters, while the IoT devices are uniformly located within a circular region centered at (100, 20, 0) meters with radius 20 meters. The antennas at the AP and the passive reflecting elements at the RIS are arranged as a uniform linear array and a uniform planar array, respectively. In the simulations, we consider both large-scale fading and small-scale fading for all the channels. The distance-dependent large-scale fading is modeled where T 0 is the path loss at the reference distance d 0 = 1 meter, d denotes the distance between the transmitter and the receiver, and α is the path loss exponent. We consider Rayleigh fading for the direct channel. Besides, we consider Rician fading for the reflecting links with Rician factor β. For the RIS-AP link (i.e., G), we have where G LoS and G NLoS denote the line-of-sight (LoS) and the non-line-of-sight (NLoS) components, respectively, d RA is the distance between the RIS and the AP, and α RA is the path loss

B. Performance Evaluation
We investigate the convergence performance of the proposed Mirror-Prox based AlterMin SCA algorithm in Fig. 3. It can be observed that the MSE of our proposed algorithm monotonically decreases over the iterations and converges in a few iterations. In addition, the achieved MSE values of the proposed algorithms before and after the projection of the phase-shift vector at the RIS are almost the same. This is because, in the simulations, the obtained phase-shift vector always meets the constraints |v i | = 1, ∀ i before projection.
We compare the proposed algorithm with the following four baseline methods.
• Alternating SDR: This method leverages the SDR technique [18], [27], [31] to optimize m and v alternately. The Gaussian randomization technique is applied when the solution returned by the relaxed SDP problem does not meet the rank-one constraint. The number of randomization is set to be 50.
• Alternating DC: This method was proposed in [1], which reformulates the rank-one constrained SDP problem as a DC programming problem, followed by using SCA to obtain the rank-one solution via successively solving the convex approximation of the DC problem.
Our comparison with this algorithm is only conducted when the number of IoT devices is small, i.e., low-density scenario, due to its high computational complexity.   becomes large. The reason is that the alternating SDR algorithm requires the execution of the second-order interior point method at each iteration, while the proposed algorithm as a first-order algorithm has a much lower computation complexity than the alternating SDR algorithm.
In Fig. 6, we investigate the impact of the number of the reflecting elements at the RIS on MSE when the number of IoT devices K = 200 and the number of antennas at the AP M = 20. As can be observed from Fig. 6, the proposed algorithm achieves almost the same MSE performance for different number of reflecting elements against the benchmark, which confirms the capability of our proposed algorithm to achieve high accurate AirComp. In addition, the MSE decreases significantly as the number of reflecting elements at the RIS increases. This is due to the fact that the RIS with more reflecting elements has more freedom for the reflection coefficient design. The computation time of our proposed algorithm and the alternating SDR algorithm versus the number of reflecting elements at the RIS is plotted in Fig. 7. As the number of reflecting elements at the RIS increases, the computation time of the alternating SDR algorithm increases significantly.
Comparing with the alternating SDR algorithm, the proposed algorithm only consumes 1% and 16% of the computation time when N = 100 and N = 30, respectively.
The computation time of the considered algorithms versus the number of IoT devices is illustratd in Fig. 8. It is obvious that, compared to the benchmark, our proposed algorithm has a superior performance in terms of the computation time. In particular, the reduction ratios are approximately 97% and 95% when K = 300 and K = 100, respectively. It can also be observed   high-density RIS-assisted AirComp systems.
2) Low-density Scenario: Due to the high computational complexity of the alternating DC algorithm, we compare its performance with the proposed algorithm when K = 10 in terms of the MSE and the computation time in Figs. 9 and 10, respectively. It can be observed from Fig. 9 that the proposed algorithm achieves a lower MSE than the alternating SDR algorithm and attains a slightly higher than MSE than the alternating DC algorithm. In addition, the MSE performance of all algorithms decreases as the number of reflecting elements at the RIS increases from 20 to 40. However, as shown in Fig. 10, our proposed algorithm is remarkably better than the alternating SDR algorithm and the alternating DC algorithm in terms of the computation time.

VI. CONCLUSION
In this paper, we proposed to leverage the advantage of RIS to mitigate the performance bottleneck of AirComp, thereby, achieving fast wireless data aggregation in IoT networks. We formulated an MSE minimization problem that requires the joint optimization of the transmit scalars at the IoT devices, the receive beamforming vector and the denoising factor at the AP, and the phase-shift matrix at the RIS. To solve this problem, a novel alternating minimization method in conjunction with the SCA technique was thus developed with convergence guarantee.
To further reduce the computational complexity, we proposed a Mirror-Prox method that only involves a series of closed-form updates to solve the convex but non-smooth subproblem in each alternation. Simulations showed that, compared to the existing alternating SDR and alternating DC algorithms, the proposed algorithm can significantly reduce the computation time while achieving a similar MSE performance.

A. Proof of Proposition 1
For simplicity of notations, we denote such that problem (10) can be rewritten as We then reformulate the problem into the following equivalent form: We further transform problem (46) to its equivalent problem in the min-max form as follows

Besides, inequality 3) holds asṽ
(n+1) (l) = arg minṽ ∈Vf v (l) (ṽ,ṽ (n) (l) ). Hence, we obtain the following chain inequalities Besides, the continuous function f v (l) (ṽ) has a lower bound in the constrained set. As a result, the non-increasing and lower bounded sequence {f v (l) (ṽ (n) (l) )} converges. Similarly, we can establish the non-increasing and convergent property for the objective value sequence achieved by {m (n) (l) } ∞ n=0 . To this end, we have proved property i). On the other hand, we can prove property ii) by iteratively utilizing property i).

C. Proof of Lemma 1
We have shown that problem (20) is equivalent to problem (27). We then rewrite problem (27) in a more compact form as where 1 = [1, 1, . . . , 1] T ∈ R K . For a given vector y ∈ R K with non-negative components, which is known as dual variable, the corresponding Lagrangian relaxed problem is given by miñ v,t t + y T P (n)ṽ + q (n) − t1 s.t.ṽ ∈ V, t ∈ R. (48) We reorganize the objective function of problem (48) as 1 − 1 T y t + P (n)ṽ + q (n) T y.
The dual objective function of problem (47) is given by the optimal value of problem (48). If 1−1 T y = 0, then 1 − 1 T y t is not bounded from below, since 1 − 1 T y t → −∞ if 1 T y > 1 and t → +∞ or if 1 T y < 1 and t → −∞.
Thus, we only need to consider y ∈ R K that satisfy y ≥ 0 and 1 T y = 1. For these y, the dual objective function is given by minṽ ∈V P (n)ṽ + q (n) T y. The dual problem is max y miñ v P (n)ṽ + q (n) T y s.t.ṽ ∈ V, y ∈ Y.
Because the original problem is convex and set V is closed and compact, the strong duality condition is satisfied. Hence, its dual problem is equivalent to itself. As the objective function P (n)ṽ + q (n) T y is linear toṽ and y, according to [39], problem (49) is equivalent to problem (28), which is a smooth convex-concave saddle point problem [38].