text:
Fast and Robust Least Squares Estimation in Corrupted Linear Models

# Fast and Robust Least Squares Estimation in Corrupted Linear Models

Brian McWilliamsGabriel KrummenacherMario LučićJoachim M. Buhmann
Department of Computer Science
ETH Zürich, Switzerland
{mcbrian,gabriel.krummenacher,mario.lucic,jbuhmann}@inf.ethz.ch
Joint first author
###### Abstract

Subsampling methods have been recently proposed to speed up least squares estimation in large scale settings. However, these algorithms are typically not robust to outliers or corruptions in the observed covariates.

The concept of influence that was developed for regression diagnostics can be used to detect such corrupted observations as shown in this paper. This property of influence – for which we also develop a randomized approximation – motivates our proposed subsampling algorithm for large scale corrupted linear regression which limits the influence of data points since highly influential points contribute most to the residual error. Under a general model of corrupted observations, we show theoretically and empirically on a variety of simulated and real datasets that our algorithm improves over the current state-of-the-art approximation schemes for ordinary least squares.

Fast and Robust Least Squares Estimation in Corrupted Linear Models

Brian McWilliams  Gabriel Krummenacherthanks: Joint first author  Mario Lučić  Joachim M. Buhmann Department of Computer Science ETH Zürich, Switzerland {mcbrian,gabriel.krummenacher,mario.lucic,jbuhmann}@inf.ethz.ch

## 1 Introduction

To improve scalability of the widely used ordinary least squares algorithm, a number of randomized approximation algorithms have recently been proposed. These methods, based on subsampling the dataset, reduce the computational time from to 111Informally: means grows more slowly than . [14]. Most of these algorithms are concerned with the classical fixed design setting or the case where the data is assumed to be sampled i.i.d. typically from a sub-Gaussian distribution [7]. This is known to be an unrealistic modelling assumption since real-world data are rarely well-behaved in the sense of the underlying distributions.

We relax this limiting assumption by considering the setting where with some probability, the observed covariates are corrupted with additive noise. This scenario corresponds to a generalised version of the classical problem of “errors-in-variables” in regression analysis which has recently been considered in the context of sparse estimation [12]. This corrupted observation model poses a more more realistic model of real data which may be subject to many different sources of measurement noise or heterogeneity in the dataset.

A key consideration for sampling is to ensure that the points used for estimation are typical of the full dataset. Typicality requires the sampling distribution to be robust against outliers and corrupted points. In the i.i.d. sub-Gaussian setting, outliers are rare and can often easily be identified by examining the statistical leverage scores of the datapoints.

Crucially, in the corrupted observation setting described in §2, the concept of an outlying point concerns the relationship between the observed predictors and the response. Now, leverage alone cannot detect the presence of corruptions. Consequently, without using additional knowledge about the corrupted points, the OLS estimator (and its subsampled approximations) are biased. This also rules out stochastic gradient descent (SGD) – which is often used for large scale regression – since convex cost functions and regularizers which are typically used for noisy data are not robust with respect to measurement corruptions.

This setting motivates our use of influence – the effective impact of an individual datapoint exerts on the overall estimate – in order to detect and therefore avoid sampling corrupted points. We propose an algorithm which is robust to corrupted observations and exhibits reduced bias compared with other subsampling estimators.

#### Outline and Contributions.

In §2 we introduce our corrupted observation model before reviewing the basic concepts of statistical leverage and influence in §3. In §4 we briefly review two subsampling approaches to approximating least squares based on structured random projections and leverage weighted importance sampling. Based on these ideas we present influence weighted subsampling (IWS-LS), a novel randomized least squares algorithm based on subsampling points with small influence in §5.

In §6 we analyse IWS-LS in the general setting where the observed predictors can be corrupted with additive sub-Gaussian noise. Comparing the IWS-LS estimate with that of OLS and other randomized least squares approaches we show a reduction in both bias and variance. It is important to note that the simultaneous reduction in bias and variance is relative to OLS and randomized approximations which are only unbiased in the non-corrupted setting. Our results rely on novel finite sample characteristics of leverage and influence which we defer to §SI.3. Additionally, in §SI.4 we prove an estimation error bound for IWS-LS in the standard sub-Gaussian model.

Computing influence exactly is not practical in large-scale applications and so we propose two randomized approximation algorithms based on the randomized leverage approximation of [8]. Both of these algorithms run in time which improve scalability in large problems. Finally, in §7 we present extensive experimental evaluation which compares the performance of our algorithms against several randomized least squares methods on a variety of simulated and real datasets.

## 2 Statistical model

In this work we consider a variant of the standard linear model

 y=Xβ+ϵ, (1)

where is a noise term independent of . However, rather than directly observing we instead observe where

 Z=X+UW. (2)

and is a Bernoulli random variable with probability of being 1. is a matrix of measurement corruptions. The rows of therefore are corrupted with probability and not corrupted with probability .

###### Definition 1 (Sub-gaussian matrix).

A zero-mean matrix is called sub-Gaussian with parameter if (a) Each row is sampled independently and has . (b) For any unit vector , is a sub-Gaussian random variable with parameter at most .

We consider the specific instance of the linear corrupted observation model in Eqs. (1), (2) where

• are sub-Gaussian with parameters and respectively,

• is sub-Gaussian with parameters ,

and all are independent of each other.

The key challenge is that even when and the magnitude of the corruptions, are relatively small, the standard linear regression estimate is biased and can perform poorly (see §6). Sampling methods which are not sensitive to corruptions in the observations can perform even worse if they somehow subsample a proportion of corrupted points. Furthermore, the corruptions may not be large enough to be detected via leverage based techniques alone.

The model described in this section generalises the “errors-in-variables” model from classical least squares modelling. Recently, similar models have been studied in the high dimensional () setting in [5, 4, 6, 12] in the context of robust sparse estimation. The “low-dimensional” () setting is investigated in [5], but the “big data” setting () has not been considered so far.222Unlike [6, 12] and others we do not consider sparsity in our solution since .

In the high-dimensional problem, knowledge of the corruption covariance, [12], or the data covariance [6], is required to obtain a consistent estimate. This assumption may be unrealistic in many settings. We aim to reduce the bias in our estimates without requiring knowledge of the true covariance of the data or the corruptions, and instead sub-sample only non-corrupted points.

## 3 Diagnostics for linear regression

In practice, the sub-Gaussian linear model assumption is often violated either by heterogeneous noise or by a corruption model as in §2. In such scenarios, fitting a least squares model to the full dataset is unwise since the outlying or corrupted points can have a large adverse effect on the model fit. Regression diagnostics have been developed in the statistics literature to detect such points (see e.g. [2] for a comprehensive overview). Recently, [14] proposed subsampling points for least squares based on their leverage scores. Other recent works suggest related influence measures that identify subspace [16] and multi-view [15] clusters in high dimensional data.

### 3.1 Statistical leverage

For the standard linear model in Eq. (1), the well known least squares solution is

 ˆβ=argminβ∥y−Xβ∥2=(X⊤X)−1X⊤y. (3)

The projection matrix with specifies the subspace in which the residual lies. The diagonal elements of the “hat matrix” , , are the statistical leverage scores of the sample. Leverage scores quantify to what extent a particular sample is an outlier with respect to the distribution of .

An equivalent definition from [14] which will be useful later concerns any matrix which spans the column space of (for example, the matrix whose columns are the left singular vectors of ). The statistical leverage scores of the rows of are the squared row norms of , i.e. .

Although the use of leverage can be motivated from the least squares solution in Eq. (3), the leverage scores do not take into account the relationship between the predictor variables and the response variable . Therefore, low-leverage points may have a weak predictive relationship with the response and vice-versa. In other words, it is possible for such points to be outliers with respect to the conditional distribution but not the marginal distribution on .

### 3.2 Influence

A concept that captures the predictive relationship between covariates and response is influence. Influential points are those that might not be outliers in the geometric sense, but instead adversely affect the estimated coefficients. One way to assess the influence of a point is to compute the change in the learned model when the point is removed from the estimation step. [2].

We can compute a leave-one-out least squares estimator by straightforward application of the Sherman-Morrison-Woodbury formula (see Prop. 3 in §SI.3):

 ˆβ−i =(X⊤X−x⊤ixi)−1(X⊤y−x⊤iyi)=ˆβ−Σ−1x⊤iei1−li

where . Defining the influence333The expression we use is also called Cook’s distance [2]., as the change in expected mean squared error we have

 di

Points with large values of are those which, if added to the model, have the largest adverse effect on the resulting estimate. Since influence only depends on the OLS residual error and the leverage scores, it can be seen that the influence of every point can be computed at the cost of a least squares fit. In the next section we will see how to approximate both quantities using random projections.

## 4 Fast randomized least squares algorithms

We briefly review two randomized approaches to least squares approximation: the importance weighted subsampling approach of [9] and the dimensionality reduction approach [14]. The former proposes an importance sampling probability distribution according to which, a small number of rows of and are drawn and used to compute the regression coefficients. If the sampling probabilities are proportional to the statistical leverages, the resulting estimator is close to the optimal estimator [9]. We refer to this as LEV-LS.

The dimensionality reduction approach can be viewed as a random projection step followed by a uniform subsampling. The class of Johnson-Lindenstrauss projections – e.g. the SRHT – has been shown to approximately uniformize leverage scores in the projected space. Uniformly subsampling the rows of the projected matrix proves to be equivalent to leverage weighted sampling on the original dataset [14]. We refer to this as SRHT-LS. It is analysed in the statistical setting by [7] who also propose ULURU, a two step fitting procedure which aims to correct for the subsampling bias and consequently converges to the OLS estimate at a rate independent of the number of subsamples [7].

#### Subsampled Randomized Hadamard Transform (SRHT)

The SHRT consists of a preconditioning step after which rows of the new matrix are subsampled uniformly at random in the following way with the definitions [3]:

• is a subsampling matrix.

• is a diagonal matrix whose entries are drawn independently from .

• is a normalized Walsh-Hadamard matrix444For the Hadamard transform, must be a power of two but other transforms exist (e.g. DCT, DFT) for which similar theoretical guarantees hold and there is no restriction on . which is defined recursively as

 Hn=[Hn/2Hn/2Hn/2−Hn/2],  H2=[+1+1+1−1].

We set so it has orthonormal columns.

As a result, the rows of the transformed matrix have approximately uniform leverage scores. (see [17] for detailed analysis of the SRHT). Due to the recursive nature of , the cost of applying the SRHT is operations, where is the number of rows sampled from [1].

The SRHT-LS algorithm solves which for an appropriate subsampling ratio, results in a residual error, which satisfies

 ∥~e∥≤(1+ρ)∥e∥ (4)

where is the vector of OLS residual errors [14].

#### Randomized leverage computation

Recently, a method based on random projections has been proposed to approximate the leverage scores based on first reducing the dimensionality of the data using the SRHT followed by computing the leverage scores using this low-dimensional approximation [8, 13, 10, 9].

The leverage approximation algorithm of [8] uses a SRHT, to first compute the approximate SVD of , Followed by a second SHRT to compute an approximate orthogonal basis for

 R−1=VΠXΣ−1ΠX∈Rp×p,  ~U=XR−1Π2∈Rn×r2. (5)

The approximate leverage scores are now the squared row norms of , From [14] we derive the following result relating to randomized approximation of the leverage

 ~li≤(1+ρl)li, (6)

where the approximation error, depends on the choice of projection dimensions and .

The leverage weighted least squares (LEV-LS) algorithm samples rows of and with probability proportional to (or in the approximate case) and performs least squares on this subsample. The residual error resulting from the leverage weighted least squares is bounded by Eq. (4) implying that LEV-LS and SRHT-LS are equivalent [14]. It is important to note that under the corrupted observation model these approximations will be biased.

## 5 Influence weighted subsampling

In the corrupted observation model, OLS and therefore the random approximations to OLS described in §4 obtain poor predictions. To remedy this, we propose influence weighted subsampling (IWS-LS) which is described in Algorithm 1. IWS-LS subsamples points according to the distribution, where is a normalizing constant so that . OLS is then estimated on the subsampled points. The sampling procedure ensures that points with high influence are selected infrequently and so the resulting estimate is less biased than the full OLS solution.

Obviously, IWS-LS is impractical in the scenarios we consider since it requires the OLS residuals and full leverage scores. However, we use this as a baseline and to simplify the analysis. In the next section, we propose an approximate influence weighted subsampling algorithm which combines the approximate leverage computation of [8] and the randomized least squares approach of [14].

#### Randomized approximation algorithms.

Using the ideas from §4 and §4 we obtain the following randomized approximation to the influence scores

 ~di=~e2i~li(1−~li)2, (7)

where is the residual error computed using the SRHT-LS estimator. Since the approximation errors of and are bounded (inequalities (4) and (6)), this suggests that our randomized approximation to influence is close to the true influence.

#### Basic approximation.

The first approximation algorithm is identical to Algorithm 1 except that leverage and residuals are replaced by their randomized approximations as in Eq. (7). We refer to this algorithm as Approximate influence weighted subsampling (aIWS-LS). Full details are given in Algorithm 3 in §SI.2.

#### Residual Weighted Sampling.

Leverage scores are typically uniform [13, 7] for sub-Gaussian data. Even in the corrupted setting, the difference in leverage scores between corrupted and non-corrupted points is small (see §6). Therefore, the main contribution to the influence for each point will originate from the residual error, . Consequently, we propose sampling with probability inversely proportional to the approximate residual, . The resulting algorithm Residual Weighted Subsampling (aRWS-LS) is detailed in Algorithm 2. Although aRWS-LS is not guaranteed to be a good approximation to IWS-LS, empirical results suggests that it works well in practise and is faster to compute than aIWS-LS.

#### Computational complexity.

Clearly, the computational complexity of IWS-LS is . The computation complexity of aIWS-LS is , where the first term is the cost of SRHT-LS, the second term is the cost of approximate leverage computation and the last term solves OLS on the subsampled dataset. Here, is the dimension of the random projection detailed in Eq. (5). The cost of aRWS-LS is where the first term is the cost of SRHT-LS, the second term is the cost of computing the residuals , and the last term solves OLS on the subsampled dataset. This computation can be reduced to . Therefore the cost of both aIWS-LS and aRWS-LS is .

## 6 Estimation error

In this section we will prove an upper bound on the estimation error of IWS-LS in the corrupted model. First, we show that the OLS error consists of two additional variance terms that depend on the size and proportion of the corruptions and an additional bias term. We then show that IWS-LS can significantly reduce the relative variance and bias in this setting, so that it no longer depends on the magnitude of the corruptions but only on their proportion. We compare these results to recent results from [12, 5] suggesting that consistent estimation requires knowledge about . More recently, [6] show that incomplete knowledge about this quantity results in a biased estimator where the bias is proportional to the uncertainty about . We see that the form of our bound matches these results.

Inequalities are said to hold with high probability (w.h.p.) if the probability of failure is not more than where are positive constants that do not depend on the scaling quantities . The symbol means that we ignore constants that do not depend on these scaling quantities. Proofs are provided in the supplement. Unless otherwise stated, denotes the norm for vectors and the spectral norm for matrices.

#### Corrupted observation model.

As a baseline, we first investigate the behaviour of the OLS estimator in the corrupted model.

###### Theorem 1 (A bound on ∥ˆβOLS−β∥).

If then w.h.p.

 ∥ˆβOLS−β∥≲ ((σϵσx+πσϵσw+π(σ2w+σwσx)∥β∥)√plogpn+πσ2w√p∥β∥)⋅1λ (8)

where .

###### Remark 1 (No corruptions case).

Notice for a fixed , taking or for a fixed taking (i.e. there are no corruptions) the above error reduces to the least squares result (see for example [5]).

###### Remark 2 (Variance and Bias).

The first three terms in (8) scale with so as , these terms tend towards 0. The last term does not depend on and so for some non-zero the least squares estimate will incur some bias depending on the fraction and magnitude of corruptions.

We are now ready to state our theorem characterising the mean squared error of the influence weighted subsampling estimator.

###### Theorem 2 (Influence sampling in the corrupted model).

For we have

 ∥ˆβIWS−β∥≲ ((σϵσx+πσϵ(σw+1)+π∥β∥)√plogpnsubs+π√p∥β∥).1λ

where and is the covariance of the influence weighted subsampled data.

###### Remark 3.

Theorem 2 states that the influence weighted subsampling estimator removes the proportional dependance of the error on so the additional variance terms scale as and . The relative contribution of the bias term is compared with for the OLS or non-influence-based subsampling methods.

#### Comparison with fully corrupted setting.

We note that the bound in Theorem 1 is similar to the bound in [6] for an estimator where all data points are corrupted (i.e. ) and where incomplete knowledge of the covariance matrix of the corruptions, is used. The additional bias in the estimator is proportional to the uncertainty in the estimate of – in Theorem 1 this corresponds to . Unbiased estimation is possible if is known. See the Supplementary Information for further discussion, where the relevant results from [6] are provided in Section SI.6.1 as Lemma 16.

## 7 Experimental results

We compare IWS-LS against the methods SRHT-LS [14], ULURU [7]. These competing methods represent current state-of-the-art in fast randomized least squares. Since SRHT-LS is equivalent to LEV-LS [9] the comparison will highlight the difference between importance sampling according to the two difference types of regression diagnostic in the corrupted model. Similar to IWS-LS, ULURU is also a two-step procedure where the first is equivalent to SRHT-LS. The second reduces bias by subtracting the result of regressing onto the residual. The experiments with the corrupted data model will demonstrate the difference in robustness of IWS-LS and ULURU to corruptions in the observations. Note that we do not compare with SGD. Although SGD has excellent properties for large-scale linear regression, we are not aware of a convex loss function which is robust to the corruption model we propose.

We assess the empirical performance of our method compared with standard and state-of-the-art randomized approaches to linear regression in several difference scenarios. We evaluate these methods on the basis of the estimation error: the norm of the difference between the true weights and the learned weights, . We present additional results for root mean squared prediction error (RMSE) on the test set in §SI.7.

For all the experiments on simulated data sets we use , , . For datasets of this size, computing exact leverage is impractical and so we report on results for IWS-LS in §SI.7. For aIWS-LS and aRWS-LS we used the same number of sub-samples to approximate the leverage scores and residuals as for solving the regression. For aIWS-LS we set (see Eq. (5)). The results are averaged over 100 runs.

#### Corrupted data.

We investigate the corrupted data noise model described in Eqs. (1)-(2). We show three scenarios where . and were sampled from independent, zero-mean Gaussians with standard deviation and respectively. The true regression coefficients, were sampled from a standard Gaussian. We added i.i.d. zero-mean Gaussian noise with standard deviation .

Figure 1 shows the difference in distribution of influence and leverage between non-corrupted points (top) and corrupted points (bottom) for a dataset with 30% corrupted points. The distribution of leverage is very similar between the corrupted and non-corrupted points, as quantified by the difference. This suggests that leverage alone cannot be used to identify corrupted points. On the other hand, although there are some corrupted points with small influence, they typically have a much larger influence than non-corrupted points. We give a theoretical explanation of this phenomenon in §SI.3 (remarks 4 and 5).

Figure 2LABEL:sub@fig:c1 and LABEL:sub@fig:c2 shows the estimation error and the mean squared prediction error for different subsample sizes. In this setting, computing IWS-LS is impractical (due to the exact leverage computation) so we omit the results but we notice that aIWS-LS and aRWS-LS quickly improve over the full least squares solution and the other randomized approximations in all simulation settings. In all cases, influence based methods also achieve lower-variance estimates.

For corruptions for a small number of samples ULURU outperforms the other subsampling methods. However, as the number of samples increases, influence based methods start to outperform OLS. Here, ULURU converges quickly to the OLS solution but is not able to overcome the bias introduced by the corrupted datapoints. Results for corruptions are shown in Figs. 5 and 6 and we provide results on smaller corrupted datasets (to show the performance of IWS-LS) as well as non-corrupted data simulated according to [13] in §SI.7.

#### Airline delay dataset

The dataset consists of details of all commercial flights in the USA over 20 years.555Dataset along with visualisations available from
http://stat-computing.org/dataexpo/2009/
Selecting the first US Airways flights from January 2000 (corresponding to approximately 1.5 weeks) our goal is to predict the delay time of the next US Airways flights. The features in this dataset consist of a binary vector representing origin-destination pairs and a real value representing distance ().

The dataset might be expected to violate the usual i.i.d. sub-Gaussian design assumption of standard linear regression since the length of delays are often very different depending on the day. For example, delays may be longer due to public holidays or on weekends. Of course, such regular events could be accounted for in the modelling step, but some unpredictable outliers such as weather delay may also occur. Results are presented in Figure 2LABEL:sub@fig:real1, the RMSE is the error in predicted delay time in minutes. Since the dataset is smaller, we can run IWS-LS to observe the accuracy of aIWS-LS and aRWS-LS in comparison. For more than samples, these algorithm outperform OLS and quickly approach IWS-LS. The result suggests that the corrupted observation model is a good model for this dataset. Furthermore, ULURU is unable to achieve the full accuracy of the OLS solution.

## 8 Conclusions

We have demonstrated theoretically and empirically under the generalised corrupted observation model that influence weighted subsampling is able to significantly reduce both the bias and variance compared with the OLS estimator and other randomized approximations which do not take influence into account. Importantly our fast approximation, aRWS-LS performs similarly to IWS-LS. We find ULURU quickly converges to the OLS estimate, although it is not able to overcome the bias induced by the corrupted datapoints despite its two-step procedure. The performance of IWS-LS relative to OLS in the airline delay problem suggests that the corrupted observation model is a more realistic modelling scenario than the standard sub-Gaussian design model for some tasks.

#### Acknowledgements.

We thank David Balduzzi for invaluable discussions, suggestions and comments.

## References

• [1] Nir Ailon and Edo Liberty. Fast dimension reduction using rademacher series on dual bch codes. In 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1–9, 2008.
• [2] David A Belsley, Edwin Kuh, and Roy E Welsch. Regression Diagnostics. Identifying Influential Data and Sources of Collinearity. Wiley, 1981.
• [3] Christos Boutsidis and Alex Gittens. Improved matrix algorithms via the Subsampled Randomized Hadamard Transform. 2012. arXiv:1204.0062v4 [cs.DS].
• [4] Y Chen, C Caramanis, and S Mannor. Robust Sparse Regression under Adversarial Corruption. In International Conference on Machine Learning, 2013.
• [5] Yudong Chen and Constantine Caramanis. Orthogonal Matching Pursuit with Noisy and Missing Data: Low and High Dimensional Results. June 2012. arXiv:1206.0823.
• [6] Yudong Chen and Constantine Caramanis. Noisy and Missing Data Regression: Distribution-Oblivious Support Recovery. In International Conference on Machine Learning, 2013.
• [7] P Dhillon, Y Lu, D P Foster, and L Ungar. New Subsampling Algorithms for Fast Least Squares Regression. In Advances in Neural Information Processing Systems, 2013.
• [8] Petros Drineas, Malik Magdon-Ismail, Michael W Mahoney, and David P Woodruff. Fast approximation of matrix coherence and statistical leverage. September 2011. arXiv:1109.3843v2 [cs.DS].
• [9] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for l2 regression and applications. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA ’06, pages 1127–1136, New York, NY, USA, 2006. ACM.
• [10] Petros Drineas, Michael W Mahoney, S Muthukrishnan, and Tamás Sarlós. Faster least squares approximation. Numerische Mathematik, 117(2):219–249, 2011.
• [11] Daniel Hsu, Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electron. Commun. Probab., 17:no. 52, 1–6, 2012.
• [12] Po-Ling Loh and Martin J Wainwright. High-dimensional regression with noisy and missing data: Provable guarantees with nonconvexity. The Annals of Statistics, 40(3):1637–1664, June 2012.
• [13] Ping Ma, Michael W Mahoney, and Bin Yu. A Statistical Perspective on Algorithmic Leveraging. In proceedings of the International Conference on Machine Learning, 2014.
• [14] Michael W Mahoney. Randomized algorithms for matrices and data. April 2011. arXiv:1104.5557v3 [cs.DS].
• [15] Brian McWilliams and Giovanni Montana. Multi-view predictive partitioning in high dimensions. Statistical Analysis and Data Mining, 5(4):304–321, 2012.
• [16] Brian McWilliams and Giovanni Montana. Subspace clustering of high-dimensional data: a predictive approach. Data Mining and Knowledge Discovery, 28:736â–772, 2014.
• [17] Joel A Tropp. Improved analysis of the subsampled randomized Hadamard transform. November 2010. arXiv:1011.1595v4 [math.NA].
• [18] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. November 2010. arXiv:1011.3027.

Supplementary Information for Fast and Robust Least Squares Estimation in Corrupted Linear Models

Here we collect supplementary technical details, discussion and empirical results which support the results presented in the main text.

## Appendix SI.1 Software

We have made available a software package available for Python which implements

• IWS-LS,

• aIWS-LS and

• aRWS-LS,

along with the methods we compare against

• SRHT-LS and

• ULURU.

The software is available from: http://bit.ly/1kifYBU

## Appendix SI.2 Approximate Influence Weighted Algorithm

Here we present a detailed description of the approximate influence weighted subsampling (aIWS-LS) algorithm. Steps 2, 3 and 4 are required for the approximate leverage computation. Step 3 could be replaced with the QR decomposition.

## Appendix SI.3 Leverage and Influence

Here we provide detailed derivations of leverage and influence terms as well as the full statement and proofs of finite sample bounds under the sub-Gaussian design and corrupted design models which are abbreviated in the main text as Lemmas 5, 6, 7, and 8.

Here we provide a full derivation of the leave-one-out estimator of which appears in less detail in [2].

###### Proposition 3 (Derivation of ˆβ−i ).

Defining and

 ˆβ−i =(Σ−x⊤ixi)−1(X⊤y−x⊤iyi) =(Σ−1+Σ−1xix⊤iΣ−11−li)(X⊤y−x⊤iyi) =ˆβ−Σ−1x⊤i(yi+xiΣ−1Xy−xiΣ−1x⊤iyi1−li) =ˆβ−Σ−1x⊤i(yi+^yi−liyi1−li) =ˆβ−Σ−1x⊤i(yi+ei1−li−yi(1−li)1−li) =ˆβ−Σ−1x⊤iei1−li

Where the first equality comes from a straightforward application of the Sherman Morrison formula.

Here we provide a derivation of the leave-one-out estimator in the corrupted model where the point we removed is corrupted.

###### Proposition 4 (Derivation of ˆβ−m).

By proposition 3. Defining

 em=^ym−ym=(xm+wm)ˆβ−ym   and
 lm=(xm+wm)Σ−1(xm+wm)⊤

where , we have that

 ˆβ−m=ˆβ−Σ−1(xm+wm)⊤em1−lm.

### si.3.1 Results for Sub-Gaussian random design

###### Lemma 5 (Leverage).

The leverage of a non-corrupted point is bounded by

 li≤σ2x⋅O((p/√n)2) (9)

where the exact form of the term is given in the supplementary material.

###### Lemma 6 (Influence).

Defining , the influence of a non-corrupted point is

 di≤Ci(σxσϵ+σ2xE). (10)

The term is proportional to .

#### Proof of Lemma 5.

Lemma 5 states

 li≤σ2x⋅(p+2logp+2√plogp√n−C√p−√logp)2.

From the Eigen-decomposition, . Define such that . We have

 li =xiΣ−1x⊤i =∥Ax⊤i∥2

Since and are sub-Gaussian random vectors so the above quadratic form is bounded by Lemma 14, setting the parameter . We combine this with the following inequalities

 √tr(Σ−2)=∥Σ−1∥F≤√p∥Σ−1∥=√pσ1(A)2

and

 tr(Σ−1)=∥A∥2F≤(√p∥A∥)2=pσ1(A)2

which relate the Frobenius norm with the spectral norm. We also make use of the relationship where to obtain

 ∥Ax∥2 ≤σ2xσn(Z)−2(p+2logp+2√plogp)

which holds with high probability.

In order for this bound to not be vacuous in our application, it must be smaller than 1. In order to ensure this, we need bound using Lemma 15 and setting to obtain the following which holds with high probability

 ∥Ax∥2 ≤σ2x(p+2logp+2√plogp√n−C√p−τ)2 ≤σ2x(p+2logp+2√plogp√n−C√p−√logp)2.

#### Proof of Lemma 6.

Defining , Lemma 6 states

 ∥ˆβ−i−ˆβ∥≤ ∥Σ−1∥1−li(σxσϵ+2σ2x∥β−ˆβ∥)√plogp.

Using Proposition 3 we have

 ∥ˆβ−i−ˆβ∥= 11−li∥Σ−1x⊤iei∥ = 11−li∥Σ−1x⊤i(ϵ+xi(β−ˆβ))∥ ≤ 11−li∥Σ−1∥∥x⊤iϵ+x⊤ixi(β−ˆβ)∥ ≤

Using Corollary 12 to bound and (since for these terms and so Lemma 11 does not immediately apply) completes the proof. ∎

### si.3.2 Results for corrupted observations

###### Lemma 7 (Leverage of corrupted point).

The leverage of a corrupted point is bounded by

 lm≤(σ2x+σ2w)⋅O((p/√n)2). (11)
###### Remark 4 (Comparison of leverage).

Comparing this with Eq. (9), when is large, the dominant term is which implies that the difference in leverage between a corrupted and non-corrupted point – particularly when the magnitude of corruptions is not large – is small. This suggests that it may not be possible to distinguish between the corrupted and non-corrupted points by only comparing leverage scores.

###### Lemma 8 (Influence of corrupted point).

Defining , the influence of a corrupted point is

 dm≤ Cm(σxσw+σ2w)∥β∥+(σ2x+2σxσw+σ2w)E +(σx+σw)σϵ. (12)
###### Remark 5 (Comparison of influence).

Here, differs from in Lemma 6 only in its dependence on the leverage of a corrupted instead of non-corrupted point and so for large , . It can be seen that the influence of the corrupted point includes a bias term similar to the one which appears in Eq. (8). This suggests that the relative difference between the influence of a non-corrupted and corrupted point will be larger than the respective relative difference in leverage. All of the information relating to the proportion of corrupted points is contained within .

#### Proof of Lemma 7.

Lemma 7 states

 lm≤(σ2x+σ2w)⋅(p+2logp+2√plogp√n−C√p−√logp)2.

The proof follows from rewriting and following the same steps as the proof of Lemma 5 above. ∎

#### Proof of Lemma 8.

Lemma 8 states

 ∥ˆβ−m−ˆβ∥≤ ∥Σ−1∥1−lm(2(σxσw+σ2w)∥β∥+2(σ2x+σxσw+σ2w)⋅∥β−ˆβ∥+2(σx+σw)σϵ) ⋅√plogp.

From Proposition 4 and following the same argument as Lemma 6 we have

 ∥ˆβ−m−ˆβ∥= 11−lm∥Σ−1(xm+wm)⊤em∥ ≤ 11−lm∥Σ−1(xm+wm)⊤((xm+wm)(β−ˆβ)+wmβ+ϵ)∥ ≤ 11−lm∥Σ−1∥(∥x⊤mwmβ∥+∥w⊤mwmβ∥+∥x⊤mϵ∥+∥w⊤mϵ∥ +∥(x⊤mxm+w⊤mwm+2x⊤mwm)(β−ˆβ)∥).

Applying the triangle inequality followed by Corollary 12 and noting that completes the proof. ∎

## Appendix SI.4 Estimation error in sub-Gaussian model

Using the definition of influence above, we can state the following theorem characterising the error of the influence weighted subsampling estimator in the sub-Gaussian design setting.

Defining for we have

 ∥ˆβIWS−β∥≲ 1λ⋅σϵλmin(Σx)(σϵ+2σxE)⋅√1rn

where and is the covariance of the influence weighted subsampled data and .

###### Remark 6.

Theorem 9 states that in the non-corrupted sub-Gaussian model, the influence weighted subsampling estimator is consistent. Furthermore, if we set the sampling proportion, , the error scales as . Therefore, similar to ULURU there is no dependence on the subsampling proportion.

## Appendix SI.5 Proof of main theorems

In this section we provide proofs of our main theorems which describe the properties of the influence weighted subsampling estimator in the sub-Gaussian random design case, the OLS estimator in the corrupted setting and finally our influence weighted subsampling estimator in the corrupted setting.

In order to prove our results we require the following lemma

###### Lemma 10 (A general bound on ∥ˆβ−β∥ from [6]).

Suppose the following strong convexity condition holds: . Then the estimation error satisfies

 ∥ˆβ−β∥≲1λ∥^γ−ˆΣβ∥.

Where , are estimators for and respectively

To obtain the results for our method in the non-corrupted and corrupted setting we can simply plug in our specific estimates for and .

#### Proof of Theorem 9.

Through subsampling according to influence, we solve the problem

 ˆβIWS=argminβ∥Θy−ΘXβ∥2

where . is a subsampling matrix, is a diagonal matrix whose entries are where is a constant which ensures .

 D2ii∝(∥Σ−1∥1−li(σxσϵ+2σ2x∥β−ˆβ∥)√plogp)−1. (13)

Setting , , by Lemma 10 the error of the influence weighted subsampling estimator is given by

 1λ∥^γ−ˆΣβ∥= ∥(ΘX)⊤(Θy)−(ΘX)⊤(ΘX)β∥ = 1λ∥(ΘX)⊤(Θϵ)+(ΘX)⊤(ΘX)β−(ΘX)⊤(ΘX)β∥ = 1λ∥(ΘX)⊤(Θϵ)∥ (14)

Now, by Lemma 11 we have

 ∥X⊤ϵ∥≤σxσϵ√plogpn

and so defining ,

 ∥(ΘX)⊤Θϵ∥≤ ∥1rnrn∑i=1pi∥⋅∥(SX)⊤Sϵ∥ ≤ ∥1rnrn∑i=1(1−li)∥σxσϵ√plogp/rn∥Σ−1∥(σxσϵ+2σ2xE)√plogp ≤ σxσϵ√plogp/rn∥Σ−1∥(σxσϵ+2σ2xE)√plogp ≤ σϵ√1/rnλmin(Σx)(σϵ+2σxE) (15)

where the third inequaltiy uses the fact that .

Define . Now, when using Lemma 13 with we have w.h.p. . It follows that

 λmin((ΘX)⊤(ΘX)) =inf∥v∥=1v⊤(ΣΘx+(ΘX)⊤(ΘX)−ΣΘx))v ≥12λmin(ΣΘx). (16)

Using (15) and (15) in Eq. (14) completes the proof.

###### Remark 7 (Scaling by π).

In the following, with some abuse of notation we will write as . Now,

 ∥W∥ :=∥UW∥ ≤π∥W∥.

#### Proof of Theorem 1.

Setting , we have

 ∥^γ−ˆΣβ∥ =∥(X+W)⊤y−(X+W)⊤(X+W)β∥ =∥X⊤(Xβ+ϵ)+W⊤(Xβ+ϵ)−X⊤Xβ−W⊤Wβ−X⊤Wβ−W⊤Xβ∥ =∥X⊤ϵ+W⊤ϵ−X⊤Wβ−W⊤Wβ∥ ≤∥X⊤ϵ∥+∥W⊤ϵ∥+∥X⊤Wβ∥+∥W⊤Wβ∥.

From Lemma 11 and Remark 7 we have w.h.p.

 ∥X⊤ϵ∥ ≤σxσϵ√plogpn (17) ∥W⊤ϵ∥ ≤πσwσϵ√plogpn (18) ∥X⊤Wβ∥ ≤πσxσw∥β∥√plogpn (19) ∥W⊤Wβ∥ ≤∥(W⊤W−


text:
The Peano curve: continuity can be counter-intuitive

The Peano curve is obtained as the limit of piecewise-linear continuous (even closed) curves $\gamma_n$. Denote by $K=\{|x|+|y|\le 1\}$ the square (rotated by $\frac \pi/4$) and by $\mathbb Z^2=\{(x,y):x,y\in\mathbb Z$ the grid of horizontal and vertical lines at distance 1 from each other, then one can construct a family of piecewise-linear continuous curves $\gamma_n:[0,1]\to\mathbb R^2$ which visits all points of the intersection $K\cap\frac1{2^n}\mathbb Z^2$ in such a way that $|\gamma_n(t)-\gamma_n(t)|<\frac1{2^n}$ uniformly on $t\in[0,1]$.

This sequence of curves converges uniformly to a function (curve) $\gamma_*:[0,1]\to\mathbb R^2$ and this curve is closed and continuous for the same reasons that justify continuity of the Koch snowflake curve.

What are the properties of the images $C_n=\gamma_n([0,1])$ and of the limit curve $C_*=\gamma_*([0,1])$?

• Each curve $C_n$ for any finite $n$ is piecewise-linear. It has zero area in the sense that for any $\varepsilon > 0$ the curve $C_n$ can be covered by a finite union of (open) rectangles with the total area less than $\varepsilon$;
• Each curve $C_n$ has finite length (although it grows to infinity as $n\to\infty$, – check it!).
• The limit curve $C_*$ has no length (that’s the same as saying that it has infinite length). Moreover, unlike many other curves of infinite length (say, the straight line $\{y=0\}\subseteq\mathbb R^2$), no part $\gamma([a,b]),\ a, of $C_*$ has finite length!
• The limit curve $C_*$ coincides with the square $K$, hence fills the area equal to 2.

All these assertions are easy except for the last one. Let’s prove it.

Consider the images $C_n=K\cap \frac1{2^n}\mathbb Z^2$. The union of these images is dense in $K$: by definition, this means that any point $P\in K$ can be approximated by a sequence of points $P_n\in C_n$ which converge to $P$ as $n\to\infty$. Being in the image of $\gamma_n([0,1])$, each point $P_n$ is the image of some point in [0,1]: $\exists a_n\in[0,1]:\ \gamma(a_n)=P_n$. Such point may well be non-unique, and in any case we have absolutely no knowledge of how the points $a_1,a_2,\dots$ are distributed over [0,1].

However, we know that the sequence $a_n\in [0,1]$ must have an accumulation point $a_*\in [0,1]$, which is by definition a limit of some infinite subsequence. (This won’t be the case if instead of [0,1] we were dealing with the curves defined on the entire real line!). Replacing the sequence by this subsequence, we see that it still converges to the same limit, $P_n=\gamma(a_n)\to a_*=\gamma_*(a_*)=P$. Thus we proved that an arbitrary point in $K$ lies in the image: $P\in C_*$.

Topology: the study of properties preserved by continuous maps (functions, applications, …)

Definition. A neighborhood of a point $a\in\mathbb R^n$ in the Euclidean space is any set of the form $\{x:|x-a| 0$, where $| ??? |$ is a distance function satisfying the triangle inequality. Examples:

• $|x|=\sqrt{x_1^2+\cdots+x_n^2}$ (the usual Euclidean distance on the line, on the plane, …) for $x=(x_1,\dots,x_n)\in\mathbb R^n$;
• $|x|=\max\{|x_1|, \dots, |x_n|\}$ (in the above notation);
• $|x|=|x_1|+\cdots+|x_n|$.

Definition. A subset $A\subset\mathbb R^n$ of the Euclidean space (OK, plane) is called open, if together with any its point $a\in A$ it contains some neighborhood of $a$.
A subset is called closed, if the limit of converging infinite sequence $\{a_n\}\subset A$ again belongs in $A$.

Theorem. A subset $A$ is open if and only if its complement $\mathbb R^n\smallsetminus A$ is closed.

Theorem. The union of any family (infinite or even uncountable) of open sets is open. Finite intersection of open sets is also open (for infinite intersections this is wrong).
Corollary. Intersection of any family (infinite or even uncountable) of closed sets is closed. Finite union of closed sets is also closed (for infinite intersections this is wrong).

One can immediately produce a lot of examples of open/closed subsets in $\mathbb R^n$. It turns out that any property that can be formulated using only these notions, is preserved by maps which are continuous together with their inverses. The corresponding area of math is called topology.

Continuity of functions

Let $f\colon D\to\mathbb R,\ D\subseteq\mathbb R$ be a function of one variable, and $a\in D$ a point in its domain. The function is said to be continuous at $a$, if for any precision $\varepsilon>0$ the function is $\varepsilon$-constant (equal to its value $f(a)$) after restriction on a sufficiently short interval around $a$.

Formally, if we denote by $\bold I=\bold I^1$ the (open) interval, then the continuity means that $\forall \varepsilon>0\ \exists\delta>0\ f(a+\delta\bold I)\subseteq f(a)+\varepsilon\bold I$ (check that you understand the meaning of the notation $u+v\bold I$ for a subset of $\mathbb R$).

A function $f\colon D\to\mathbb R$ is said to be continuous on a subset $D'\subset D$, if it is continuous at all points $a\in D'$ of this subset. Usually we consider the cases where $D'=D$, that is, functions continuous on their domain of definition.

Remarks.
1. If $a$ is an isolated point of the domain $D$, then any function is automatically continuous at $a$ for a simple reason: for all sufficiently small $\delta>0$ the intersection $(a+\delta\bold I)\cap D$ consists of a single point $a$, so the image is a single point $f(a)$.

2. If $a\notin D$ but $\inf_{x\in D} |x-a|=0$ and there exists a limit $A=\lim_{x\to a}f(x)$, then one can extend $f$ on $a$ by letting $f(a)=A$ and obtain a function defined on $D\cup\{a\}$ which is continuous at $a$.

Obvious properties of the continuity

The sum, difference and product of two functions continuous at a point $a$, is again continuous. The reciprocal of a continuous function $\frac1{f}$ is continuous at $a$, if $f(a)\ne 0$.

This is an obvious consequence of the rules of operations on “approximate numbers” (קירובים). When dealing with the sum/difference, one has to work with absolute approximations, when dealing with the product/ratio – with the relatice approximations, but ultimately it all boils down to the same argument: if two functions are almost constant on a sufficiently small interval around $a$, then application of the arithmetic operations is almost constant.

Not-so-obvious property of continuity

When the continuity is compatible with transition to limit? More specifically, we consider the situation where there is an infinite number of functions $f_n\colon:D\to\mathbb R$ defined on the common domain $D$. Assume that for any $a\in D$ the values (numbers!) $f_n(a)\in\mathbb R$ form a converging sequence whose limit is denoted by $f_*(a)$ (it depends on $a$!). What can one say about the function $f_*\colon a\mapsto f_*(a)$?

Example.
Assume that $f_n(x)=x^n$ and $D=[0,1]$. All of them are continuous (why?). If $a<1$, then $\lim_{n\to\infty} a^n=0$. If $a=1$, then for any $n\ a^n=1$. Thus the limit $\lim_{n\to\infty}f_n(a)$ exists for all $a$, but as a function of $a\in[0,1]$ it is a discontinuous function. Thus without additional precautions a sequence of continuous functions can converge to a discontinuous one.

Distance between the functions.
The distance between real numbers $a,b\in\mathbb R$ is the nonnegative number $|a-b|$ which is zero if and only if $a=b$. Motivated by that, we introduce the distance $\|f-g\|$ between two functions $f,g\colon D\to \mathbb R$ as the expression $\sup_{a\in D}|f(a)-g(a)|$.

Exercise. Prove that any three functions $f,g,h$ defined on the common domain $D$, the “triangle inequality” $\|f-g\|\leqslant \|f-h\|+\|h-g\|$.

Definition. A sequence of functions $f_n\colon D\mathbb R$ is said to be uniformly converging to a function $f_*\colon D\to\mathbb R$, if $\lim_{n\to\infty}\|f_n-f_*\|=0$.

Theorem. If a sequence of continuous functions converges uniformly, then the limit is also a continuous function.

Indeed, denote by $g$ the limit function, $a\in D$ any point, and let $\varepsilon>0$ be any “resolution”. We need to construct a small interval around $a$ such that $g$ on this interval is $\varepsilon$-indistinguishable from the value $g(a)$. We split the resolution allowance into two halves. The first half we use to find $N$ such that $\|f_n-g\| < \frac\varepsilon2$ for all $n\ge N$. The second half we spend on the continuity: since $f_N$ is continuous, there exists a segment $a+\delta\bold I$ on which $f_N$ is $\frac\varepsilon2$-indistinguishable from $f_N(a)$. Collecting all inequalities we see that for any point $x\in a+\delta\bold I$ we have three inequalities: $|f_N(a)-g(a)|<\frac\varepsilon2, \ |f_N(x)-g(x)|<\frac\varepsilon2,\ |f_N(x)-g(x)|<\frac\varepsilon2$. By the triangle inequality, $|g(x)-g(a)|< \frac{3\varepsilon}2$. Ooops! we were heading for $\varepsilon$! One should rather divide our allowance into unequal parts, $\frac{2\varepsilon}3$ for the distance and $\frac\varepsilon3$ for the continuity of $f_N$ if we thought ahead of the computation! 😉 in any case, the outcome is the same.

Curves

The notion of continuity, the distance between functions etc. can be generalized from functions of one variable to other classes of functions.

For instance, functions of the form $\gamma\colon [0,1]\to\mathbb R^2$ can be called (parametrized) curves. Here the argument $x\in[0,1]$ can be naturally associated with time, so the $\gamma(t)$ is the position of the moving point at the moment $t$. We can draw the image $\gamma([0,1])$: this drawing does not reflect the timing: to indicate it, we can additionally mark the images, say, $\gamma (\frac k{10}),\ k=0,1,\dots,10$.

To define continuity for curves, denote by $\bold I^2$ the unit square $\{|x|<1,\ |y|<1\}$. A curve $\gamma$ is continuous at a point $a\in [0,1]$ if $\forall\varepsilon >0 \ \exists \delta>0$ such that $\gamma (a+\delta\bold I^1)\subseteq \gamma(a)+\varepsilon \bold I^2$. (Do you understand this formula? 😉 )

The distance between two points $a=(a_1,a_2),\ b=(b_1,b_2)\in\mathbb R^2$ is usually defined as $\sqrt{(a_1-b_1)^2+(a_2-b_2)^2}$, but this difference is not very much different from the expression $|a-b|=\max_{i=1,2}|a_i-b_i|$ (this definition can be immediately generalized for spaces $\mathbb R^n$ of any finite dimension $n=3,4,\dots$. The distance between two curves has a very similar form: $\|f-g\|=\sup_{x\in [0,1]}|f(x)-g(x)|$.

Remark. If the functions $f,g$ are continuous, we can replace the supremum by maximum (which is always achieved).

Koch snowflake revisited

Now we can return to one of the examples we discussed on Lecture 1, the Koch snowflake. In contrast with that time, we now have an appropriate language to deal with it.

The process of constructing the curve actually produces a sequence of closed curves. The image of the first curve is an equilateral triangular, the second one gives the Star of David, the third one has no canonical name.

In all cases the new curve $\gamma_{n+1}$ is obtained by taking the previous curve $\gamma_n$ and modifying it on a subset of its domain: instead of traversing a line segment with constant speed, one takes a middle third of this segment and forces $\gamma_{n+1}$ to detour. This requires increasing the speed, but we don’t care as long as the trajectory remains continuous. The distance between $\gamma_n$ and $\gamma_{n+1}$ is $\frac{\sqrt3}2$ times the size of the size of the segment $\frac1{3^n}$.

This observation guarantees that $\|\gamma_n-\gamma_{n+1}\|< C(1/3)^n$. This implies that the sequence of maps $\gamma_n\colon [0,1]\to\mathbb R^2$ converges uniformly. The result is continuous curve $\gamma_*\colon[0,1]\to\mathbb R^2$ which has "infinite length" (in fact, it has no length at all).

Wednesday, November 11, 2015

Lecture 3, Nov 10, 2015

Filed under: Rothschild course "Analysis for high school teachers" — Sergei Yakovenko @ 5:18
Tags: ,

Limits

First, what’s the problem?
Assume we want to calculate the derivative of the function $f(x)=x^2$, say, at the point $x=2$. This derivative is the number, defined using the divided difference $\displaystyle\frac{(2+h)^2-4}{h}=4+h$ when $h$ is “very small”. What does it mean “very small”? We cannot let $h$ be exactly zero, since division by zero is forbidden. On the other hand, if $h\ne 0$, then the above expression is never equal to 4 (as expected) precisely, so in any case the “derivative” cannot be 4, as we want. To resolve this controversy, Leibniz introduced mysterious “differentials” which disappear when added to usual numbers, but whose ratio has precise numerical meaning.

The approach by Leibniz can be worked out into a rigorous mathematical theory, called nonstandard analysis, but historically a different approach, based on the notion of limit (of sequence, function, …), prevailed.

Limit of a sequence

Consider an (infinite) sequence $\{a_n:n\in\mathbb N\}=\{a_1,a_2,a_3,\dots,a_n,\dots\}$ of real numbers. We say that it stabilizes (מתיצבת) at the value $A\in\mathbb R$, if only finitely many terms in this sequence can be different from $A$, and the remaining infinite “tail” consists of the repeated value $A$. Since among the finitely many numbers $n\in\mathbb N$ one can always choose the maximal one (denoted by $N$), we say that the sequence $latex\{a_n\}$ stabilizes, if

$\exists N\in\mathbb N\ \forall n>N\ a_n=A.$

Obviously, stabilizing sequences are not interesting, but their obvious properties can be immediately listed:

1. Changing any finite number of terms in a stabilizing sequence keeps it stabilizing and vice versa;
2. If a sequence $\{a_n\}$ stabilizes at $A$, and another sequence $\{b_n\}$ stabilizes at $B$, then the sum-sequence $\{a_n+b_n\}$ stabilizes at $A+B$, the product-sequence $\{a_nb_n\}$ at $AB$.
3. The fraction-sequence $\{a_n/b_n\}$ may be not defined, but if $B\ne 0$, then only finitely many terms $b_n$ can be zeros, just change them to nonzero numbers and then the fraction-sequence will be defined for all $n$ and stabilize at $A/B$.
4. Exercise: formulate properties of stabilizing sequences, involving inequalities.

Blurred vision

As we have introduced the real numbers, to test their equality requires to check infinitely many “digits”, which is unfeasible. All the way around, we can specify a given precision $\varepsilon >0$ (it can be chosen rational). Then one can replace the genuine equality by $\varepsilon$-equality, saying that two numbers $a,b\in\mathbb R$ are $\varepsilon$-equal, if $|a-b|<\varepsilon$. This is a bad notion that will be used only temporarily, since it is not transitive (for the same fixed value of $\varepsilon$). Yet as a temporary notion, it is very useful.

We say that an infinite sequence $\{a_n\}\ \varepsilon$-stabilizes at a value $A$ for a given precision $\varepsilon$, if only finitely many terms in the sequence are not $\varepsilon$-equal to $A$. Formally, this means that

$\exists N\in\mathbb N\ \forall n>N\ |a_n-A|<\varepsilon.$

The choice of the precision $\varepsilon>0$ is left open so far. In practice it may be set at the level which is determined by the imperfection of our measuring instruments, but since we strive for a mathematical definition, we should not set any artificial threshold.

Definition. A sequence of real numbers $\{a_n\}$ is said to converge to the limit $A\in\mathbb R$, if for any given precision $\varepsilon>0$ this sequence $\varepsilon$-stabilizes at $A$. The logical formula for the corresponding statement is obtained by adding one more quantifier to the left:

$\forall\varepsilon>0\ \exists N\in\mathbb N\ \forall n>N\ |a_n-A|<\varepsilon.$

If we want to claim that the sequence is converging without specifying what the limit is, one more quantifier is required:

$\exists A\in\mathbb R\ \forall\varepsilon>0\ \exists N\in\mathbb N\ \forall n>N\ |a_n-A|<\varepsilon.$

Of course, this formula is inaccessible to anybody not specially prepared for the job, this is why so many students shuttered their heads over it.

Obvious examples

1. $a_n=\frac 1n$, or, more generally, $a_n=\frac1{n^p},\ p>0$. The limit is zero.
2. $a_n=c,\ c\in\mathbb R$. Joke.
3. $a_n =n^p,\ p>0$. Diverges.
4. These rules (plus the obvious rules concerning the arithmetic operations) allow to decide the convergence of any sequence $a_n$ whose general term is a rational function of $n$.
5. Exceptional cases are very rare: e.g., when $a_n=\displaystyle\left(1+\frac 1n\right)^n$

Limits of functions

Let $f\colon D\to\mathbb R$ be a function defined on a subset $D$, and $a\in\mathbb R\smallsetminus D$ a point outside the doomain of $f$. We want to “extend” the function to this point if this makes sense.

For a given precision $\varepsilon>0$ we say that $f$ is $\varepsilon$-constant on a set $S\subseteq D$, if there exists a constant $A\in\mathbb R$ such that $\forall x\in S\ |f(x)-A|<\varepsilon$.

Definition. The function $f\colon D\to\mathbb R$ is said to have a limit equal to $A$ at a point $a\notin D$, if

1. all intersections between $D$ and small intervals $I_\delta=\{|x-a|<\delta\}$ are non-empty and
2. $\forall\varepsilon>0\ \exists\delta>0$ such that the function restricted on $D\cap \{|x-a|<\delta\}$ is $\varepsilon$-constant.

In other words, the function is $\varepsilon$-indistinguishable from a constant on a sufficiently small open interval centered around $a$.

Remark. One can encounter situations when the function is defined at some point $a\in D$, but if we delete this point from $D$, then the function will have a limit $A$ at this point. If this limit coincides with the original value $f(a)$, then the function is well-behaved (we say that it is continuous). If the limit exists but is different from $f(a)$, then we understand that the function was intentionally twisted, and if we change its value at just one point, then it will become continuous. If $f$ has no limit at $a$ if restricted on $D\smallsetminus \{a\}$, we say that $katex f$ is discontinuous$at $a$. Clearly, such extension by taking limit is possible (if at all) only for points at “zero distance” from the domain of the function. For more detail read the lecture notes from the past years. Series As was mentioned, the problem of calculating limits of explicitly given (i.e., elementary) functions is usually not very difficult. The real fun begins when there is no explicit formula for the terms of the sequence (or the function). This may happen if the sequence is produced by some recurrent (inductive) rule. The most simple case occurs where the rule is simply summation (should we say “correction”?) of a known nature: $a_{n+1}=a_n+\text{something explicitly depending on }n$. If we denote the added value by $b_n$, then the sequence will take the form $a_1, a_1+b_1, a_1+b_1+b_2,a_1+b_1+b_2+b_3,a_1+b_1+b_2+b_3+b_4,\dots$. If we can perform such summations explicitly and write down the answer as a function of $n$, it would be great. Example. Consider the case where $b_n=\frac1{n(n+1)}=\frac1n-\frac1{n+1}$. Then we get a “telescopic” sum which can be immediately computed. But this is rather an exception… Another example is the geometric progression where $b_n=cq^n$ for some constant $c,q$. In general we cannot write down the sum as a function of $n$, which makes the task challenging. Definition. Let $b_n$ be a real sequence. We say that the infinite series $\sum_{k=1}^\infty b_k$ converges, if the sequence of its finite sums $a_n=\sum_{k=1}^n b_k$ has a (finite) limit. Examples. 1. The geometric series $\sum_{k=1}^\infty q^k$ converges if $|q|<1$ and diverges if $|q|\ge 1$. 2. The harmonic series $\sum_{k=1}^\infty \frac1k$ diverges. 3. The inverse square series $\sum_{k=1}^\infty \frac1{n^2}$ converges. The last two statements follow from the comparison of the series with patently diverging or patently converging series (fill in the details!). Later on we will concentrate specifically on the series of the form $\sum_{k=0}^\infty c_k q^k$ with a given sequence of “Taylor coefficients” $c_0,c_1,c_2,\dots$ which contain a parameter $q$. Considered as the function of $q$, these series exhibit fascinating properties which make them ubiquitous in math and applications. Tuesday, January 10, 2012 Lectures 11-12, January 3, 10 (2012) Properties of continuous functions. Basic notions of topology The standard list of properties of functions, continuous on intervals, includes theorems on intermediate value, on boundedness, on attainability of extremal values etc. We explain that these results are manifestations of the following phenomenon. There are several properties of subsets of $\mathbb R^1$ (and, in general, arbitrary subsets of the Euclidean space), which can be defined using only the notions of limit and proximity. Such properties are called topological. Examples of such properties are openness/closeness, connectedness (arc-connectedness) and compactness. The general principle then can be formulated (vaguely) as follows: the topological properties are preserved by continuous maps (or their inverses). Wednesday, December 28, 2011 Lecture 10, December 27, 2011 Continuity and limits of functions of real variable In the first lecture we introduce the notion of continuity of a function at a given point in its domain and a very close notion of a limit at a point outside of the “natural” domain. This notion is closely related to the notion of sequential limit as introduced earlier. This paves a way to generalize immediately all arithmetic and order results from numeric sequences to functions. The novel features involve one-sided limits, limits “at infinity” and continuity of composition of functions. The (unfinished) notes, to be eventually replaced by a more polished text, are available here: follow the updates, this temporary link will eventually be erased. Monday, December 21, 2009 Lecture 8 (Dec 22, 2009) Continuation of continuity Let $f\colon [0,1]\times[\alpha,\beta]\to\mathbb R^2$ be a continuous function defined on the closed rectangle $[0,1]\times[\alpha,\beta]$. Then the functions $f_a(x)=f(x,a)$ are all defined on the segment $[0,1]$ and “converge” to $f_{a_*}(x)$ as $a\to a_*\in[\alpha,\beta]$. If $a_1,a_2,\dots, a_n,\dots$ is a sequence of values of $a$ converging to $a_*$, $\lim a_n=a_*$, then we have a sequence of functions $f_n=f_{a_n}\colon[-1,1]\to\mathbb R$, all defined on the same segment, which also “converges” to the limit $f_*=f_{a_*}$ The meaning of the “convergence of functions” is not yet defined. Problem. Prove that in the above notations, for any point $x\in[0,1]$ the sequence of numbers $f_n(x)$ converges to the number $f_*(x)$. This type of convergence is called pointwise convergence (התכנסות נקודתית). Example. Prove that the functions $f_n(x)=x^n,~n=1,2,\dots$, converge pointwise to a certain limit function $f_*\colon[0,1]\to\mathbb R$. Find this function. Example. Let $\phi(x)=\frac1{1+x^2}$ be the function defined on the entire axis $\mathbb R$, and denote $f_n(x)=\phi(x-n)\colon\mathbb R\to\mathbb R$ (translation to the right by $n$). The same question: does a limit exist? Formally, the pointwise convergence is defined by the following formula: $\lim f_n=f_*$, if $\forall x\in [0,1],~\forall \varepsilon >0,~\exists N=N(x,\varepsilon),~\forall n\ge N,~|f_n(x)-f_*(x)|<\varepsilon$. Clearly, this is the same as the formula $\forall \varepsilon >0,~\forall x\in [0,1],~\exists N=N(x,\varepsilon),~\forall n\ge N,~|f_n(x)-f_*(x)|<\varepsilon.$ However, the “convergence” which comes from the continuity in two variables, is stronger. Theorem. If $f(x,y)$ is a continuous function on the rectangle, as above, then for any $\varepsilon>0$ there exists a positive $\delta>0$ such that for any $a$ with $|a-a_*|<\delta$, the functions $f_a$ and $f_{a_*}$ differ at most by $\varepsilon$ on the entire segment $[0,1]$: $\forall x\in[0,1],~|f_a(x)-f_{a_*}(x)|<\varepsilon$. Corollary. In the above notation, $f_n$ converges to $f_*$ “simultaneously” (uniformly, במידה שווה): $\forall\varepsilon>0,~\exists N=N(\varepsilon):~\forall x\in[0,1],~\forall n\ge N,~|f_n(x)-f_*(x)|<\varepsilon.$ Functions as “points” (vectors) Continuous functions defined on the same interval, can be added, subtracted, multiplied by constants etc, which makes them similar to vectors in $\mathbb R^3$. We can also define the “distance” between the functions as follows, $d(f_1,f_2)=\max_{x\in[0,1]}|f_1(x)-f_2(x)|$. This number is always non-negative and finite: 1. $d(f_1,f_2)=0\iff f_1=f_2$; 2. $d(f_1,f_2)=d(f_2,f_1)$ (symmetry); 3. $d(f_1,f_3)\le d(f_1,f_2)+d(f_2,f_3)$ (the triangle inequality). Proposition/Definition. The sequence of functions $\{f_n\}$ converges uniformly to $f_*$, if $d(f_n,f_*)\to0$. Question. In which of the examples above the convergence is uniform? Can a limit of continuous functions be disconjugate? A sequence of pointwise converging continuous functions may converge to a discontinuous function (see the first example above). Theorem. The limit of uniformly converging on a closed sequence continuous functions is again continuous. Example. The snowflake is a continuous closed curve of “infinite length”. Peano (plane-filling) curve This is a continuous map $\gamma\colon [0,1]\to \mathbb R^2$ which fills completely (i.e., passes through each point of) the unit square. There are many examples of such curves, below is the example constructed by D. Hilbert. Giuseppe Peano was an Italian mathematician Sketch of the justification In both cases the “malicious” curve is obtained as the limit of an infinite sequence of planar polygonal (hence continuous) curves $\gamma_n\colon [0,1]\to\mathbb R^2$. By construction, each next curve $\gamma_{n+1}$ differs from its predecessor $\gamma_n$ by an explicitly limited “modification”. In the example with the Peano curve, we subdivide the initial unit square into for small squares of the “first level” and draw the curve crossing each of the four squares in the specified order. Then each 1st level square is again subdivided into 4 tiny sub-squares of the “second level” and each segment of the curve is modified so as it (1) remains inside the same 1st level square, yet (2) crosses each of the four 2nd level squares as plotted. Hence the curve $\gamma_2$ differs from the curve $\gamma_2$ by no more than $\sqrt 2$. In the same way $\|\gamma_3-\gamma_2\|\le \sqrt 2/2$$\|\gamma_4-\gamma_3\|\le \sqrt 2/2^2$ etc. Thus it is clear that for any $t\in[0,1]$ the limit $\lim_{n\to\infty}\gamma_n(t)$ exists, and $|\gamma_n(t)-\gamma_*(t)|\le \sqrt{2}/2^{n-3}$. Thus the convergence of the functions is uniform, and therefore the limit is also a continuous function. How to show that it indeed passes through each point of the unit square? Note that the curve $\gamma_n$ passes through centers of all squares of the $n$th level. Any point $a_*$ of the initial square can be approximated by centers of the squares of sufficiently high level. There exists an infinite sequence of points $a_n\in\gamma_n([0,1])$ which converges to $a_*$, i.e., the infinite sequence of moments $t_n\in[0,1]$ such that $\lim_{n\to\infty}\gamma_n(t_n)=a$. Passing to a subsequence if necessary, we can assume (since the segment [0,1] is compact) that the sequence $\{t_n\}$ converges to a limit $t_*$. One can easily check that because of the uniform continuity, $\gamma_*(t_*)=a_*$. Problem. Write the detailed accurate exposition of this proof. Monday, December 14, 2009 Lecture 7 (Dec 15, 2009) Topology of the plane 1. Functions of two variables as maps $f\colon \mathbb R^2\to\mathbb R$. Domains in the plane. Open and closed domains. 2. Convergence of planar points: $\lim_{n\to\infty}(x_n,y_n)=(X,Y)\in\mathbb R^2\iff\lim x_n=X\ \&\ \lim y_n=Y$. Alternative description: any square $Q_\varepsilon(X,Y)=\{|x-X|<\varepsilon,\ |y-Y|<\varepsilon\}$ contains almost all elements of the sequence. 3. Limits of functions: $f\colon U\to\mathbb R$, $Z=(X,Y)\in\mathbb R$. We say that $A=\lim_{(x,y)\to Z}f(x,y)$, if for any sequence of points $\{(x_n,y_n)\}$ converging to $Z$, the sequence $f(x_n,y_n)$ converges to $A$ as $n\to\infty$. We say that $f$ is continuous at $Z$, if $A=f(Z)$. 4. Exercise: $f$ is continuous at $Z$, if the preimage $f^{-1}(J)$, of any interval $J=(A-\delta,A+\delta),\ \delta>0$, contains the intersection $Q_\varepsilon\cap U$ for some sufficiently small $\varepsilon>0$. 5. Exercise: if $f$ is continuous at all points of the rectangle $\{x\in I,\ y\in J\}\subseteq\mathbb R^2$, then for any $y\in J$ the function $f_y\colon I\to\mathbb R$, defined by the formula $f_y(x)=f(x,y)$ is continuous on $I$. Can one exchange the role of $x$ and $y$? Formulate and think about the inverse statement. 6. Exercise: Check that the functions $f(x,y)=x\pm y$ and $g(x,y)=xy$ are continuous. What can be said about the continuity of the function $f(x,y)=y/x$? 7. Exercise: formulate and prove a theorem on continuity of the composite functions. 8. Exercise: Give the definition of a continuous function $f\colon I\to\mathbb R^2$ for $I\subseteq\mathbb R$. Planar curves. Simple curves. Closed curves. 9. Intermediate value theorem for curves. Connected sets, connected components. Jordan lemma. 10. Rotation of a closed curve around a point. Continuity of the rotation number. Yet another “Intermediate value theorem” for functions of two variables. Tuesday, December 8, 2009 Lecture 6 (Dec 8, 2009) Topology on the real line Definition. A homeomorphism between two subsets $X,Y\subseteq\mathbb R$ is a one-to-one map $\Phi\colon X\to Y$ such that both $\Phi$ and its inverse $\Phi^{-1}\colon Y\to X$ are continuous. If such a map exists, the two subsets are called homeomorphic (or topologically equivalent) and we write $X\simeq Y$. • Homeomorphisms between $(a,b),~(0,+\infty)$ and $\mathbb R$. • The property “Every continuous function is bounded” is invariant by homeomorphism: if it is true for a set $X$ and $Y\simeq X$, then this property also holds for $Y$. Non-homeomorphy of $[0,1]$ and $\mathbb R$. • The properties “Closedness” and “Openness” are invariant by homeomorphism: if $X$ is closed/open and $Y\simeq X$, then $Y$ is closed/open respectively. • Is the property “Boundedness” invariant by homeomorphism? • The disjoint union $(-1,0)\cup (0,1)$ is homeomorphic to $(-2,-1)\cup(1,2)$ yet non-homeomorphic to $(-1,1)$ or $(-1,1]$. Definition. A set $K\subseteq\mathbb R$ is called compact, if from any covering of $K$ by open sets (intervals), $K\subseteq\bigcup_i U_i$, one can choose a finite sub-covering $U_{i_1}\cup U_{i_2}\cup\dots\cup U_{i_n}\supseteq K$. Finite point sets are compact. Union of two compacts is a compact. Theorem. The segment $[0,1]$ is compact. Proof. Assume that it is not compact, and $\bigcup U_i$ is an open covering that does not admit a finite subcovering. Then out of the two halves $[0,\frac 12]$ and $[\frac12, 1]$ one is non-compact and the same covering does not admit finite subcovering of this bad half. The bad half-segment can be again divided by two etc. This process produces a nested family of segments $[0,1]=K_0\supset K_1\supset K_2\supset\cdots\supset K_n\supset\dots$ of lengths decreasing to 0, which has a (unique) common point $a\in K_0$: none of these segments by construction admits a finite subcovering by the sets $U_i$. But the open interval $U_{i_k}$ covering $a$, covers also all sufficiently small segments $K_n$. The resulting contradiction proves that the initial segment $K_0$ was compact. ♦ Proposition. A function continuous on a compact set, is bounded (and achieves its extremal values). Proof. For each point $a\in X$ there exists a neighborhood $U_a\subset\mathbb R$ such that $f$ is bounded on $U_a$ (e.g., takes values on the interval $(f(a)-1,f(a)+1)$. Choose a finite sub-covering and pick the maximal out of the (finitely many!!) local bounds. ♦ Definition. A subset $X\subseteq\mathbb R$ is called connected, if together with any pair of points $a,b\in X$ it contains the entire segment $[a,b]$. The property “Being connected” is invariant by homeomorphisms (what does this mean?) There are only four non-empty connected subsets on $\mathbb R$, not homeomorphic to each other: a point, an open interval, a closed segment and a semi-interval $(0,1]$. The Cantor set From the closed segment $[0,1]$ delete the (open) middle third $(\frac 13,\frac 23)$. To each of the two remaining closed segments $[0,\frac13],\ [\frac23,1]$ apply the same procedure (deleting the middle third), and repeat it. As a result, we obtain an infinite collection (family) of nested closed subsets $[0,1]=K_0\supset K_1\supset\cdots\supset K_n\supset\cdots$, each of which is a finite union of $2^n$ closed segments of total length $(\frac 23)^n$ going to zero. The intersection $\mathbf K=\bigcap_{n=0}^\infty K_n$ is the Cantor set. • $\mathbf K$ is closed. For any $\varepsilon>0$ it can be covered by finitely many intervals of total length less than $\varepsilon$. • $\mathbf K$ contains no open subset (everywhere holes!), yet no point of$latex\mathbf K\$ is isolated.
• $\mathbf K$ is in one-to-one correspondence with the entire segment $[0,1]$.

These properties can be seen from the alternative description of $\mathbf K$ as points on the segment $[0,1]$, whose infinite “ternary” (i.e., on the basis 3) representation does not involve “ones” (see the warning below), only zeros and “twos”.

Example. To show that any point $a=0.a_1a_2a_3\dots\in\mathbf K$ is not isolated, we show that each interval of length $3^{-n}$ centered at $a$, contains another point of $\mathbf K$. For this, it is sufficient to change a “ternary digit” $a_k$ with the number $k$ greater than $n$ by “the other” digit, i.e., 0 by 2 or 2 by 0.

Warning. The infinite ternary representation is non-unique (in the same way as the decimal representation): the two expressions $0.0222222222\dots$ and $0.10000\dots$ correspond to the same point! how does this affect the above arguments?

Difficult question. Construct a continuous  function $f\colon \mathbf K\to[0,1]$ such that the preimage $f^{-1}(b)$ of any point $b\in[0,1]$ always consists of only one or two points from $\mathbf K$.

Continuity

A function $f\colon X\to\mathbb R$ defined on a subset $X\subseteq\mathbb R$ is continuous (in full, continuous on $X$), if it is continuous at each point $a\in X$. Continuity is equivalent to the requirement that the preimage $f^{-1}(U)$ of any open set $U$ is open in $X$ (i.e., is an intersection between $X$ and an open subspace $V\subseteq \mathbb R$).

• Continuity at a point is a local property. Automatic continuity at isolated points of $X$.
• Examples of discontinuity points.
• Continuity and arithmetic operations. Continuity of the composition. Continuity of elementary functions.
• Dirichlet function: the ugly beast. Further pathologies.
• Continuity and global properties:
1. Continuity and boundedness
2. Continuity and existence of roots
3. Continuity and monotonicity
• Continuity and functional equations $f(x+y)=f(x)+f(y)$, $f(x+y)=f(x)\cdot f(y)$, $f(xy)=f(x)+f(y)$, $f(xy)=f(x)\cdot f(y)$.

Create a free website or blog at WordPress.com.

format: plain


text:
# Importing data surrounded by Square brackets

I have a big one line data file with a list of integers which are in the following format:

[[1 4 5 6 2] [9 8 7 4 7] [....]],[[...] .....[...]],.....]]

I have been trying Import but what I get is

{{[[1,4,5,6,2],[9,8,7,4,7],[....]],[[...] .....[...]],.....]]}}

The problem is that I can not replace the "[" and "]" by "{" and "}" respectively.

How I could a list of lists with brackets?

Thanks regards

• I guess something like ImportString["[[1 4 5 6 2] [9 8 7 4 7] [10 3 1 0 5]],[[3 0 9 1 7] [5 6 11 1 7] [3 0 2 0 1]]", "Table", "FieldSeparators" -> {" "}, "IgnoreEmptyLines" -> True, "LineSeparators" -> {",", "[", "]"}]? – J. M. will be back soon Mar 31 '17 at 13:26
• Hi, I can not copy-paste the content of the file into ImportString command of your example because there are mores than 300 000 integers. Also, this example gives {{1,4,5,6,2},{ }, [9 8 7 4 7] . – user1993416 Mar 31 '17 at 13:44
• import the whole thing as string then, ToExpression[StringReplace[instring, {" " -> ",", "[" -> "{", "]" -> "}"}]] (You may need an extra pair of { } around the whole thing ) Is this matlab output by the way? – george2079 Mar 31 '17 at 13:46
• The idea is to use Import[filename, "Table", options] on your end, where you make the necessary replacements. – J. M. will be back soon Mar 31 '17 at 13:49
• I have tested the two alternatives work fine. Thank you very much @J.M and – user1993416 Mar 31 '17 at 13:56

ToExpression[
StringReplace["[[1 4 5 6 2] [9 8 7 4 7]]", {" " -> ",", "[" -> "{", "]" -> "}"}]]
(* {{1, 4, 5, 6, 2}, {9, 8, 7, 4, 7}} *)

• i just realized george2079 wrote the same answer in the comments – Ali Hashmi Mar 31 '17 at 16:19

This is what you after?

string="[[1 4 5 6 2] [9 8 7 4 7] [10 3 1 0 5]],[[3 0 9 1 7] [5 6 11 1 7] [3 0 2 0 1]]";
ImportString[StringReplace[#,Whitespace->","],"RawJSON"]&/@StringSplit[string,","]

{{{1,4,5,6,2},{9,8,7,4,7},{10,3,1,0,5}},{{3,0,9,1,7},{5,6,11,1,7},{3,0,2,0,1}}}

• +1, and a suggestion: it'll be more robust if you replace " " with Whitespace. – Szabolcs Mar 31 '17 at 15:30
• @Szabolcs Good suggestion,I have updated that.Thanks. – yode Mar 31 '17 at 15:34

You could use something like this if your data is not too large:

terp = Interpreter[
DelimitedSequence[
DelimitedSequence["Number", {"[", Whitespace, "]"}],
{"[", Whitespace, "]"}
]
]

terp["[[1 2] [3 4]]"]
(* {{1, 2}, {3, 4}} *)

You can add another layer of DelimitedSequence if you have several such expressions separated by commas.

Unfortunately, this method of parsing is quite slow.


text:
## Dihedral group - isomorphism

The dihedral group Dn of order 2n has a subgroup of rotations of order n and a subgroup of order 2. Explain why Dn cannot be isomorphic to the external direct product of two such groups.

If H denotes the subgroup of rotations and G denotes the subgroup of order 2.

G = { identity, any reflection} ( because order of any reflection is 2)

I can see that order of Dn= 2n = order of external direct product
 PhysOrg.com science news on PhysOrg.com >> Intel's Haswell to extend battery life, set for Taipei launch>> Galaxies fed by funnels of fuel>> The better to see you with: Scientists build record-setting metamaterial flat lens
 Blog Entries: 8 Recognitions: Gold Member Science Advisor Staff Emeritus Try to show that Dn is nonabelian (for $n\geq 3$) and that your direct product will always be abelian...

 Quote by micromass Try to show that Dn is nonabelian (for $n\geq 3$) and that your direct product will always be abelian...
Thanks a lot. I got it.

If we take H as the subgroup consisting of all rotations of Dn, then being a cyclic group, it would also be abelian. Then again, subgroup K of order 2 is abelian.

Further, the external direct product H + K is abelian as H and K are abelian.

Thanks !!


text:
### Home > INT2 > Chapter 9 > Lesson 9.4.1 > Problem9-138

9-138.

Graph the following points on graph paper and then connect them in the order given. Then find the area and perimeter of the shape. Show all work. 9-138 HW eTool (Desmos).

$A(-2,-3)$, $B(-6,5)$, $C(11,5)$, $D(7,2)$,$E(7,-3)$

Try using the Pythagorean Theorem to find the lengths of different sides. Also try breaking up this shape into easier shapes to find the area.

$\text{Perimeter } = 44.9 \; \text{units}$
$\text{Area} = 94 \; \text{square units}$

Use the eTool below to plot the points correctly.
Click the link at right for the full version of the eTool: INT2 9-138 HW eTool


text:
# Solution - In the following figure, (QR)/(QS) = (QT)/(PR) and ∠1 = ∠2. Show that ΔPQS ~ ΔTQR. - Criteria for Similarity of Triangles

Account
Register

Share

Books Shortlist
ConceptCriteria for Similarity of Triangles

#### Question

In the following figure, (QR)/(QS) = (QT)/(PR)  and ∠1 = ∠2. Show that ΔPQS ~ ΔTQR.

#### Solution

You need to to view the solution
Is there an error in this question or solution?

#### Reference Material

Solution for question: In the following figure, (QR)/(QS) = (QT)/(PR) and ∠1 = ∠2. Show that ΔPQS ~ ΔTQR. concept: Criteria for Similarity of Triangles. For the course CBSE
S


text:
# Why do we not care about completeness, sufficiency of an estimator as much anymore?

When we begin to learn Statistics, we learn about seemingly important class of estimators that satisfy the properties sufficiency and completeness. However, when I read recent articles in Statistics I can hardly find any papers that address complete sufficient statistics. Why would we not care about completeness, sufficiency of an estimator as much anymore?

• Statistically speaking, how do you quantify the "as much anymore" part in your question? To what degree of certainty do you know that your observation is sufficiently objective? – luis.espinal Feb 27 at 17:27

We still care. However, a large part of statistics is now based on a data-driven approach where these concepts may not be essential or there are many other important concepts.

With computation power and lots of data, a large body of statistics is devoted to provide models that solve specific problems (such as forecasting or classification) that can be tested using the given data and cross-validation strategies. So, in these applications, the most important characteristics of models are that they have a good fit to the data and claimed ability to forecast out of sample.

Furthermore, some years ago, we were very interested in unbiased estimators. We still are. However, in that time, in rare situations one could consider to use an estimator that is not unbiased. In situations where we are interested in out of sample forecasts, we may accept an estimator that is clearly biased (such as Ridge Regression, LASSO and Elastic Net) if they are able to reduce the out of sample forecast error. Using these estimators actually we “pay” with bias to reduce the variance of the error or the possibility of overfitting.

This new focus of the literature has also brought new concepts such as sparsistency. In statistical learning theory we study lots of bounds to understand the ability of the generalization of a model (this is crucial). See for instance the beautiful book "Learning From Data" by Abu-Mostafa et al.

Related fields such as econometrics have also been suffering the impact of these changes. Since this field is strongly based on statistical inference and it is fundamental to work with unbiased estimators associated with models that come from the theory, the changes are slower. However, several attempts have been introduced and machine learning (statistical learning) is becoming essential to deal for instance high dimensional databases.

Why is that?

Because economists, in several situations, are interested in the coefficients and not in the predictable variable. For instance, imagine a work that tries to explain corruption-level using a regression model such as: $$\text{corruptionLevel} = \beta_0 + \beta_1 \text{yearsInPrison} + \beta_2 \text{numberConvicted} + \cdots$$

Note that the coefficients $$\beta_1$$ and $$\beta_2$$ provide information to guide the public policy. Depending on the values of the coefficients, different public policies will be carried out. So, they cannot be biased.

If the idea is that we should trust in the coefficients of the econometric regression model and we are working with high dimensional databases, maybe we may accept to pay with some bias to receive in return lower variance: “Bias-variance tradeoff holds not only for forecasts (which in the case of a linear model are simply linear combinatons of the estimated coefficients) but also for individual coefficients. One can estimate individual coefficients more accurately (in terms of expected squared error) by introducing bias so as to cut variance. So in that sense biased estimators can be desirable. Remember: we aim at finding the true value. Unbiasedness does not help if variance is large and our estimates lie far away from the true value on average across repeated samples.” - @Richard_Hardy

This idea has motivated researchers to look for solutions that sound good for economists as well. Recent literature has approached this problem by choosing focus variables that are not penalized. These focus variables are the ones that are important to guide public policy. In order to avoid the omitted variables bias, they also run a regression of this focus variables on all the other independent variables using a shrinking procedure (such as Lasso). The ones with coefficients different from zero are also included in the regression model as well. They ensure that asymptotics of this procedure is good. See here a paper of one of the leader of the field. See for instance this overview by leaders of the field.

• I think this captures the broad situation quite well. However, many fields including econometrics make much use of maximum likelihood and tolerate small biases. (This is a bit more gung-ho for machine learning than many readers would be, but let opinions be opinions.) – Nick Cox Feb 25 at 9:59
• @DanielTheRocketMan, you say it is fundamental to work with unbiased estimators in econometrics. Could you offer some explanation on how / why / what is the technical reason? – Richard Hardy Feb 25 at 14:21
• This argument has not convinced me so far. Bias-variance tradeoff holds not only for forecasts (which in the case of a linear model are simply linear combinatons of the estimated coefficients) but also for individual coefficients. One can estimate individual coefficients more accurately (in terms of expected squared error) by introducing bias so as to cut variance. So in that sense biased estimators can be desirable. Remember: we aim at finding the true value. Unbiasedness does not help if variance is large and our estimates lie far away from the true value on average across repeated samples. – Richard Hardy Feb 25 at 15:01
• I agree with @RichardHardy here. Much of statistics boils down to a trade-off between bias and variance and a small bias is often both inevitable and acceptable. – Nick Cox Feb 25 at 15:07
• I am aware of this approach. Assuming some of the shrunken variables are actually relevant and correlated with the focus variables, the focus variables will be biased even if they are not shrunken, so there you go. Also, Bayesian econometrics is being successfully used in heavly parameterized macroeconomic models with small samples; frequentist estimators of these models are less biased but have such high variance that are useless in practice (and therefore not used). But if you agree with my argument, then you may wish to reconsider the bit where you write fundamental in your answer. – Richard Hardy Feb 25 at 15:49

We do care but usually either the issue is taken care of, or we're not making a specific distributional assumption with which we could apply those considerations.

1. Many of the usual estimators for commonly used parametric models are either fully efficient under the usual distributional assumptions for that model or asymptotically efficient under those model assumptions. Unless we're dealing with fairly small sample sizes, there's nothing to do.

Consider generalized linear models as an obvious example.

2. We often don't have a fully explicit parametric distributional model. We might use a robust procedure, or we might be looking at some convenient estimator along with a bootstrap for dealing with bias and estimating standard error.

Without an explicit distribution to even start looking at sufficiency or completeness for, there's nothing to do.

(Consider that there may be little point in finding an efficient estimator for a model you're sure will be wrong... what might make more sense would be finding one that does reasonably well in some kind of neighborhood of an approximate model. A good part of the theory for robustness takes a particular sense of the word "neighborhood" when considering a question like this.)

In the comments below Nick Cox points out that "deviations from the ideal -- are often perfectly tolerable"; this is certainly the case. Box wrote "Remember that all models are wrong; the practical question is how wrong do they have to be to not be useful." To me this is a pretty central issue, but I'd add "and in what particular ways" after "how wrong".

It's important to understand the behavior of the tools we use away from the situation they're best at; when do they perform quite well, when do they perform badly (and hopefully what else might do at least as well in a similar range of circumstances).

We need to keep in mind that statistical tools like tests, estimates and intervals all have several senses in which we expect them to 'perform' (e.g. significance level and power, bias and variance, interval width and coverage); for example, there's often a tendency to focus very hard on significance level on tests without paying attention to power.

These issues are less clean-cut than looking at completeness or sufficiency, and we don't have a nice array of "neat" theorems to use. In many cases we may need to use coarser but simpler tools - like simulation - to get much of a sense of what may happen. [In some situations it helps to understand something of the tools of robustness to have clues about what things it might make sense to simulate. It's good to have a sense of what it takes to make something go completely off the rails. I've seen people report that a test has "good robustness to skewness" while simulating nothing more extreme than an exponential distribution, for example, and only examining type I error rate.]

• (+1) It's a one-person campaign, just about, but I think that much of the literature, and much discussion, would be easier and more effective if we could talk and write about ideal conditions for procedures rather than assumptions. In logic and pure mathematics, truth of conclusions depends on truth of assumptions, but in marriage and statistics, imperfections -- deviations from the ideal -- are often perfectly tolerable. – Nick Cox Feb 25 at 14:10
• (Sure, in logic and pure mathematics, you can get a correct conclusion by accident.) – Nick Cox Feb 25 at 14:15
• @NickCox: I think focusing on tolerance of imperfections in statistical models and marriage might actually be a two-person campaign --- you, and my wife. – Ben - Reinstate Monica Feb 25 at 23:23
• A very good point that was made for the first time, as far as I'm aware, by John W. Tukey in his 1962 paper "The Future of Data Analysis", projecteuclid.org/download/pdf_1/euclid.aoms/1177704711 - particularly Sec. I.5 Dangers of optimization. – Lewian Feb 26 at 0:04


text:
Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

E. Two Permutations
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rubik is very keen on number permutations.

A permutation a with length n is a sequence, consisting of n different numbers from 1 to n. Element number i (1 ≤ i ≤ n) of this permutation will be denoted as ai.

Furik decided to make a present to Rubik and came up with a new problem on permutations. Furik tells Rubik two number permutations: permutation a with length n and permutation b with length m. Rubik must give an answer to the problem: how many distinct integers d exist, such that sequence c (c1 = a1 + d, c2 = a2 + d, ..., cn = an + d) of length n is a subsequence of b.

Sequence a is a subsequence of sequence b, if there are such indices i1, i2, ..., in (1 ≤ i1 < i2 < ... < in ≤ m), that a1 = bi1, a2 = bi2, ..., an = bin, where n is the length of sequence a, and m is the length of sequence b.

You are given permutations a and b, help Rubik solve the given problem.

Input

The first line contains two integers n and m (1 ≤ n ≤ m ≤ 200000) — the sizes of the given permutations. The second line contains n distinct integers — permutation a, the third line contains m distinct integers — permutation b. Numbers on the lines are separated by spaces.

Output

On a single line print the answer to the problem.

Examples
Input
1 111
Output
1
Input
1 212 1
Output
2
Input
3 32 3 11 2 3
Output
0


text:
# Finding the number of events in a given period based on time interval between events

I have a set of "Days since last Visit" data from the Google Analytics:

Day since last Visit     Count of Users
Total                    400K
0                        100K
1                        50K
2                        10K
....

Given a fixed Time Frame, the row "1 50K" means that there are 50K users who have the last two visits in a consecutive day, and "0 100K" means that for that 100K users, their last two visits occur on the same day.

So is it possible for me to estimate, the expected number of days for the users visit the sites in a month?

• Do you mean you want to estimate the expected number of visits per month of a user; or do you just want the expected value of the "days since last visit" variable? – Peter Ellis Jun 25 '13 at 5:32
• expected Days of visits per month of a user, so if the user come several times in the same day, that only count as 1. – Kloser Cheung Jun 25 '13 at 11:27


text:
# 4.4: Right Triangle Trigonometry

Trigonometry is the study of triangles. If you know the angles of a triangle and one side length, you can use the properties of similar triangles and proportions to completely solve for the missing sides.

Imagine trying to measure the height of a flag pole. It would be very difficult to measure vertically because it could be several stories tall. Instead walk 10 feet away and notice that the flag pole makes a 65 degree angle with your feet. Using this information, what is the height of the flag pole?

### Trigonometric Functions

The six trigonometric functions are sine, cosine, tangent, cotangent, secant and cosecant. Opp stands for the side opposite of the angle $$\theta,$$ hyp stands for hypotenuse and adj stands for side adjacent to the angle $$\theta$$.

\begin{aligned} \sin \theta &=\frac{o p p}{h y p} \\ \cos \theta &=\frac{a d j}{h y p} \\ \tan \theta &=\frac{o p p}{a d j} \\ \cot \theta &=\frac{a d j}{o p p} \\ \sec \theta &=\frac{h y p}{a d j} \\ \csc \theta &=\frac{h y p}{o p p} \end{aligned}

The reason why these trigonometric functions exist is because two triangles with the same interior angles will have side lengths that are always proportional. Trigonometric functions are used by identifying two known pieces of information on a triangle and one unknown, setting up and solving for the unknown. Calculators are important because the operations of sin, cos and tan are already programmed in. The other three (cot, sec and csc) are not usually in calculators because there is a reciprocal relationship between them and tan, cos and sec.

$$\sin \theta=\frac{o p p}{h y p}=\frac{1}{\csc \theta}$$
$$\cos \theta=\frac{a d j}{h y p}=\frac{1}{\sec \theta}$$
$$\tan \theta=\frac{o p p}{a d j}=\frac{1}{\cot \theta}$$

Keep in mind that your calculator can be in degree mode or radian mode. Be sure you can toggle back and forth so that you are always in the appropriate units for each problem.

Note that the images throughout this concept are not drawn to scale. If you were given the following triangle and asked to solve for side $$b$$, you would use sine to find $$b$$.

\begin{aligned} \sin \left(\frac{2 \pi}{7}\right) &=\frac{b}{14} \\ b &=14 \cdot \sin \left(\frac{2 \pi}{7}\right) \approx 10.9 \mathrm{in} \end{aligned}

### Examples

Example 1

Earlier, you were asked about the height of a flagpole that you are 10 feet away from. You notice that the flag pole makes a $$65^{\circ}$$ angle with your feet.

If you are 10 feet from the base of a flagpole and assume that the flagpole makes a $$90^{\circ}$$ angle with the ground, you can use the following triangle to model the situation.

\begin{aligned} \tan 65^{\circ} &=\frac{x}{10} \\ x &=10 \tan 65^{\circ} \approx 21.4 f t \end{aligned}

Example 2

Solve for angle $$A$$.

This problem can be solved using sin, cos or tan because the opposite, adjacent and hypotenuselengths are all given.

The argument, or input, of a sin function is always an angle. The arcsin, or $$\sin ^{-1} \theta,$$ function on the calculator has an argument that is a ratio of the triangle sides.

\begin{aligned} \sin A &=\frac{5}{13} \\ \sin ^{-1}(\sin A) &=\sin ^{-1}\left(\frac{5}{13}\right) \\ A &=\sin ^{-1}\left(\frac{5}{13}\right) \approx 0.39 \text { radian } \approx 22.6^{\circ} \end{aligned}

Example 3

Given a right triangle with $$a=12$$ in $$, m \angle B=20^{\circ},$$ and $$m \angle C=90^{\circ}$$, find the length of the hypotenuse.

It is helpful to draw a diagram to represent the data given in a question.

\begin{aligned} \cos 20^{\circ} &=\frac{12}{c} \\ c &=\frac{12}{\cos 20^{\circ}} \approx 12.77 \mathrm{in} \end{aligned}

Example 4

Given $$\triangle A B C$$ where $$B$$ is a right angle, $$m \angle C=18^{\circ},$$ and $$c=12 .$$ What is $$a$$ ?

Drawing out this triangle, it looks like:

\begin{aligned} \tan 18^{\circ} &=\frac{12}{a} \\ a &=\frac{12}{\tan 18^{\circ}} \approx 36.9 \end{aligned}

Example 5

Given $$\triangle M N O$$ where $$O$$ is a right angle, $$m=12$$, and $$n=14$$. What is the measure of angle $$M$$ ?
Drawing out the triangle, it looks like:

\begin{aligned} \tan M &=\frac{12}{14} \\ M &=\tan ^{-1}\left(\frac{12}{14}\right) \approx 0.7 \text { radian } \approx 40.6^{\circ} \end{aligned}

Review

For $$1-15$$, information about the sides and/or angles of right triangle $$A B C$$ is given. Completely solve the triangle (find all missing sides and angles) to 1 decimal place.

 Problem Number $$A$$ $$B$$ $$C$$ $$a$$ $$b$$ $$c$$ 1. $$90^{\circ}$$ 4 7 2. $$90^{\circ}$$ $$37^{\circ}$$ 18 3. $$90^{\circ}$$ $$15^{\circ}$$ 32 4. $$90^{\circ}$$ 6 11 5. $$90^{\circ}$$ $$12^{\circ}$$ 19 6. $$90^{\circ}$$ 17 10 7. $$90^{\circ}$$ $$10^{\circ}$$ 2 8. $$4^{\circ}$$ $$90^{\circ}$$ 0.3 9. $$\frac{\pi}{2}$$ radian 1 radian 15 10. $$\frac{\pi}{2}$$ radian 12 15 11. $$\frac{\pi}{2}$$ radian 9 14 12. $$\frac{\pi}{4}$$ radian $$\frac{\pi}{4}$$ radian 5 13. $$\frac{\pi}{2}$$ radian 26 13 14. $$\frac{\pi}{2}$$ radian 19 16 15. $$\frac{\pi}{2}$$ radian 10 $$10 \sqrt{2}$$