nous employons la définition de dimension doublement pour prouver que, si b / ∈ X, alors Sb / ∈ S(X) presque sûrement aussi longtemps que d = Ω(DDim(X)). ici, DDim(X) est la dimension de doublement de X, qui est défini comme le plus petit nombre tel que chaque boule dans X peut être couvert par 2 dd(X) boules de la moitié du rayon. Nous étendons ce résultat au cas seuillée, et obtenons un plus utile lié pour d. Il se trouve que, en conséquence de ce résultat, nous sommes en mesure pour améliorer une borne de Indyk-Naor sur les plus proches neigbour embeddings Préserver par un facteur de log(1/δ) ε .

Dans le chapitre 6, nous proposons d'appliquer des projections aléatoires pour le problème des régions de confiance sous-problème, qui est déclaré comme min{c x + x Qx | Ax ≤ b, X ≤ 1}. Ces problèmes se posent dans les méthodes de région de confiance pour faire face à l'optimisation des produits dérivés libre. Soit P ∈ R d×n soit une matrice aléatoire échantillonnée par la distribution gaussienne, nous considérons alors le problème " projeté " suivant:

en définissant u := P x. Ce dernier problème est de faible dimension et peut être résolu beaucoup plus rapidement que l'original. Cependant, nous montrons que, si u * est la solution optimale, alors avec une forte probabilité, x * := P u * est une (1 + O(ε)) -approximation pour le problème d'origine. Cela se fait à l'aide de résultats récents de la "concentration de valeurs propres de matrices gaussiennes".

3

Acknowledgement

First of all, I would like to express my gratitude to my PhD advisor, Prof. Leo Liberti. He is a wonderful advisor who always encourages, supports and advises me, both in research and career. Under his guidance I have learned about creative ways for solving difficult problems. I wish to thank Dr. Claudia D'Ambrosio for supervising me when my advisor was in sabbatical years. Her knowledge and professionalism really helped me to build the first steps of my research career. I would also like to acknowledge the supports of my joint PhD advisor, Dr.

Youssef Hamadi, during my first 2 years. I would like to thank Pierre-Louis Poirion for being my long time collaborator. He is a very smart guy who can generate tons of ideas on a problem. It is my pleasure to work with him and his optimism has encouraged me to continue to work on challenging problems. I would like to thank all my colleagues at the Laboratoire d'informatique de l' École Polytechnique (LIX), including Andrea, Gustavo, Youcef, Claire, Luca, Sonia, and so on... for being my friends and for all their helps. Last but not least, I would like to thank my wife, Diep, for her unlimited love and support. This research was supported by a Microsoft Research PhD scholarship.

iii

Résumé

Dans cette thèse, nous allons utiliser les projections aléatoires pour réduire le nombre de variables ou le nombre de contraintes (ou les deux) dans certains problèmes d'optimisation bien connus. En projetant les données dans des espaces de dimension faible, nous obtenons de nouveaux problèmes similaires, mais plus facile à résoudre. De plus, nous essayons d'établir des conditions telles que les deux problèmes (original et projeté) sont fortement liés (en probabilité). Si tel est le cas, alors en résolvant le problème projeté, nous pouvons trouver des solutions approximatives ou une valeur objective approximative pour l'original.

Nous allons appliquer les projections aléatoires pour étudier un certain nombre de problèmes d'optimisation importants, y compris la programmation linéaire et en nombres entiers (Chapitre 2), l'optimisation convexe avec des contraintes linéaires (Chapitre 3), adhésion et rapprocher le plus proche voisins (chapitre 4) et la région-confiance (chapitre sous-problèmes 5). Tous ces résultats sont tirés des documents dont je suis co-auteur avec [START_REF] Vu | Using the Johnson-Lindenstrauss lemma in linear and integer programming[END_REF][START_REF] Vu | Gaussian random projections for Euclidean membership problems[END_REF][START_REF] Vu | Randomized sketches for convex optimization with linear constraints[END_REF][START_REF] Vu | Random projections for trust-region subproblems with applications to derivative-free optimization[END_REF].

Cette thèse sera construite comme suit. Dans le premier chapitre, nous présenterons quelques concepts et des résultats de base en théorie des probabilités. Puisque cette thèse utilise largement les probabilités élémentaire, cette introduction informelle sera plus facile pour les lecteurs avec peu de connaissances sur ce champ pour suivre nos travaux. "Décidez si dist(T b, T (X)) ≥ τ ". Dans le cas où X peut être indénombrable, nous montrons que l'original et les projections des problèmes sont également équivalentes si la dimension projetée d est proportionnelle à une dimension intrinsèque de l'ensemble X. En particulier, probability, this informal introduction will make it easier for readers with little background on this field to follow our works.

In Chapter 2, we will briefly introduce to random projection and the Johnson-Lindenstrauss lemma. We will present several constructions of random projectors and explain the reason why they work. In particular, sub-gaussian random matrices will be treated in details, together with some discussion on fast and sparse random projections.

In Chapter 3, we study optimization problems in their feasibility forms. In particular, we study the so-called restricted linear membership problem, which asks for the feasibility of the system {Ax = b, x ∈ C} where C is some set that restricts the choice of parameters x. This class contains many important problems such as linear and integer feasibility. We propose to apply a random projection T to the linear constraints and obtain the corresponding projected problem: {T Ax = T b, x ∈ C}. We want to find conditions on T , so that the two feasibility problems are equivalent with high probability. The answer is simple when C is finite and bounded by a polynomial (in n). In that case, any random projection T with O(log n) rows is sufficient. When C = R n + , we use the idea of separating hyperplane to separate b from the cone {Ax | x ≥ 0} and show that T b is still separated from the projected cone {T Ax | x ≥ 0} under certain conditions. If these conditions do not hold, for example when the cone {Ax | x ≥ 0} is non-pointed, we employ the idea in the Johnson-Lindenstrauss lemma to prove that, if b / ∈ {Ax | x ≥ 0}, then the distance between b and that cone is slightly distorted under T , thus still remains positive. However, the number of rows of T depends on unknown parameters that are hard to estimate.

In Chapter 4, we continue to study the above problem in the case when C is a convex set.

Under that assumption, we can define a tangent cone K of C at x * ∈ arg min x∈C Ax -b .

We establish the relations between the original and projected problems based on the concept of Gaussian width, which is popular in compressed sensing. In particular, we prove that the two problems are equivalent with high probability as long as the random projection T is sampled from sub-gaussian distributions and has at least O(W 2 (AK)) rows, where W(AK) is the Gaussian-width of AK. We also extend this result to the case when T is sampled from randomized orthonormal systems in order to exploit its fast matrix-vector multiplication.

Our results are similar to those in [START_REF] Pilanci | Randomized sketches of convex programs with sharp guarantees[END_REF], however they are more useful in privacy-preservation applications when the access to the original data A, b is limited or unavailable.

In Chapter 5, we study the Euclidean membership problem: "Given a vector b and a closed set X in R n , decide whether b ∈ X or not". This is a generalization of the restricted linear membership problem considered previously. We employ a Gaussian random projection T to embed both b and X into a lower dimension space and study the corresponding projected version: "Decide whether T b ∈ T (X) or not". When X is finite or countable, using a straightforward argument, we prove that the two problems are equivalent almost surely regardless the projected dimension. However, this result is only of theoretical interest, possibly due to round-off errors in floating point operations which make its practical application difficult. We address this issue by introducing a threshold τ > 0 and study the corresponding "thresholded" problem: "Decide whether dist (T b, T (X)) ≥ τ ". In the case when X may be uncountable, we prove that the original and projected problems are also equivalent if the projected dimension d is proportional to some intrinsic dimension of the set X. In particular, we employ the definition of doubling dimension to prove that, if b / ∈ X, then Sb / ∈ S(X) almost surely as long as d = Ω(ddim(X)). Here, ddim(X) is the doubling dimension of X, which is defined as the smallest number such that each ball in X can be covered by at most 2 dd(X) balls of half the radius. We extend this result to the thresholded case, and obtain a more useful bound for d. It turns out that, as a consequence of that result, we are able to improve a bound of Indyk-Naor on the Nearest Neigbour Preserving embeddings by a factor of log(1/δ) ε .

In Chapter 6, we propose to apply random projections for the trust-region subproblem, which is stated as min{c x + x Qx | Ax ≤ b, x ≤ 1}. These problems arise in trust-region methods for dealing with derivative-free optimization. Let P ∈ R d×n be a random matrix sampled from Gaussian distribution, we then consider the following "projected" problem: min{c P P x + x P P QP P x | AP P x ≤ b, P x ≤ 1}, which can be reduced to min{(P c) u + u (P QP )u | AP u ≤ b, u ≤ 1} by setting u := P x. The latter problem is of low dimension and can be solved much faster than the original. However, we prove that, if u * is its optimal solution, then with high probability,

x * := P u * is a (1 + O(ε))-approximation for the original problem. This is done by using recent results about the "concentration of eigenvalues" of Gaussian matrices.

Chapter 1

Introduction

Optimization is the process of minimizing or maximizing an objective function over a given domain, which is called the feasible set. In this thesis, we consider the following general In the digitization age, data becomes cheap and easy to obtain. That results in many new optimization problems with extremely large sizes. In particular, for the same kind of problems, the numbers of variables and constraints are huge. Moreover, in many application settings such as those in Machine Learning, an accurate solution is less preferred as approximate but robust ones. It is a real challenge for traditional algorithms, which are used to work well with average-size problems, to deal with these new circumstances.

Instead of developing algorithms that scale up well to solve these problems directly, one natural idea is to transform them into small-size problems that strongly relates to the originals.

Since the new ones are of manageable sizes, they can still be solved efficiently by classical methods. The solutions obtained by these new problems, however, will provide us insight into the original problems. In this thesis, we will exploit the above idea to solve some highdimensional optimization problems. In particular, we apply a special technique called random projection to embed the problem data into low dimensional spaces, and approximately reformulate the problem in such a way that it becomes very easy to solve but still captures the most important information.

Random projection versus Principal Component Analysis

Random projection (defined formally in Chapter 2) is the process of mapping high-dimensional vectors to a lower-dimensional space by a random matrix. Examples of random projectors are matrices with i.i.d Gaussian or Rademacher entries. These matrices are constructed in certain ways, so that, with high probability, they can well-approximate many geometrical structures such as distances, inner products, volumes, curves, . . . The most interesting feature is that, they are often very "fat" matrices, i.e. the number of rows is significantly smaller than the number of columns. Therefore, they can be used as a dimension reduction tool, simply by taking matrix-vector multiplications.

Despite of its simplicity, random projection works very well and comparable to many other classical dimension reduction methods. One method that is often compared to random projection is the so-called Principal Component Analysis (PCA). PCA attempts to find a set of orthonormal vectors {ξ 1 , ξ 2 , . . .} that better represent the data points. These vectors are often called principal components. In particular, the first component ξ 1 is found as the vector with the largest variance, i.e.

ξ 1 = arg max u =1 n i=1 x i , u 2 ,
and inductively, ξ i is found as the vector with the largest variance among all the vectors that are orthogonal to ξ 1 , . . . , ξ i-1 . In order to apply PCA for dimension reduction, we simply take k first components out to obtain a matrix Ξ k = (ξ 1 . . . ξ k ), and then form the new

(lower-dimensional) data point T k = XΞ k .
Note that, PCA closely relates to the singular vector decomposition (SVD) of the matrix X.

Recall that, any matrix X can be written in the SVD form as the product of U ΣV , in which It is easy to see that, as opposed to PCA and SVD, random projection is much cheaper to compute. The complexity of constructing a random projector is often fractional to the number of entries, i.e. O(nm), and that is significantly smaller than the complexity O(nm 2 + m 3 ) of PCA. Moreover, random projections are data-independent, i.e. they are always constructed the same way regardless how the point set is distributed. This property is often called oblivious, and it is one of the main advantages of random projection over other dimension reduction techniques. In many applications, the number of data points are often very large and/or might not be known at hand (in the case of online and stream computations). In these circumstances, it is expensive and even impossible to exploit the information of the data point to construct principal components in the PCA method. Random projection, therefore, is the only choice.

U, V are (n × n)-orthogonal matrices (i.e. U U = V V = I n ) and

Structure of the thesis

In this thesis, we will use random projection to reduce either the number of variables or the number of constraints (or both in some cases) in some well-known optimization problems. By projecting data into lower dimensional spaces, we obtain new problems with similar structures, but much easier to solve. Moreover, we try to establish conditions such that the two problems (original and projected) are strongly related (in probability sense). If it is the case, then by solving the projected problem, we can either find approximate solutions or approximate objective value for the original one.

We will apply random projection to study a number of important optimization problems, including linear and integer programming (Chapter 2), convex optimization with linear constraints (Chapter 3), membership and approximate nearest neighbor (Chapter 4) and trustregion subproblems (Chapter 5). All these results are taken from the papers that I am co-authored with [START_REF] Vu | Using the Johnson-Lindenstrauss lemma in linear and integer programming[END_REF][START_REF] Vu | Gaussian random projections for Euclidean membership problems[END_REF][START_REF] Vu | Randomized sketches for convex optimization with linear constraints[END_REF][START_REF] Vu | Random projections for trust-region subproblems with applications to derivative-free optimization[END_REF].

The rest of this thesis will be constructed as follows. At the end of this chapter, we will present some basic concepts and results in probability theory. Since this thesis extensively uses elementary probability, this informal introduction will make it easier for readers with little background on this field to follow our works.

In Chapter 2, we will briefly introduce to random projection and the Johnson-Lindenstrauss lemma. We will present several constructions of random projectors and explain the reason why they work. In particular, sub-gaussian random matrices will be treated in details, together with some discussion on fast and sparse random projections.

In Chapter 3, we study optimization problems in their feasibility forms. In particular, we study the so-called restricted linear membership problem, which asks for the feasibility of the system {Ax = b, x ∈ C} where C is some set that restricts the choice of parameters x. This class contains many important problems such as linear and integer feasibility. We propose to apply a random projection T to the linear constraints and obtain the corresponding projected problem: {T Ax = T b, x ∈ C}. We want to find conditions on T , so that the two feasibility problems are equivalent with high probability. The answer is simple when C is finite and bounded by a polynomial (in n). In that case, any random projection T with O(log n) rows is sufficient. When C = R n + , we use the idea of separating hyperplane to separate b from the cone {Ax | x ≥ 0} and show that T b is still separated from the projected cone {T Ax | x ≥ 0} under certain conditions. If these conditions do not hold, for example when the cone {Ax | x ≥ 0} is non-pointed, we employ the idea in the Johnson-Lindenstrauss lemma to prove that, if b / ∈ {Ax | x ≥ 0}, then the distance between b and that cone is slightly distorted under T , thus still remains positive. However, the number of rows of T depends on unknown parameters that are hard to estimate.

In Chapter 4, we continue to study the above problem in the case when C is a convex set.

Under that assumption, we can define a tangent cone K of C at x * ∈ arg min x∈C Ax -b .

We establish the relations between the original and projected problems based on the concept of Gaussian width, which is popular in compressed sensing. In particular, we prove that the two problems are equivalent with high probability as long as the random projection T is sampled from sub-gaussian distributions and has at least O(W 2 (AK)) rows, where W(AK) is the Gaussian-width of AK. We also extend this result to the case when T is sampled from randomized orthonormal systems in order to exploit its fast matrix-vector multiplication.

Our results are similar to those in [START_REF] Pilanci | Randomized sketches of convex programs with sharp guarantees[END_REF], however they are more useful in privacy-preservation applications when the access to the original data A, b is limited or unavailable.

In Chapter 5, we study the Euclidean membership problem: "Given a vector b and a closed set X in R n , decide whether b ∈ X or not". This is a generalization of the restricted linear membership problem considered previously. We employ a Gaussian random projection T to embed both b and X into a lower dimension space and study the corresponding projected version: "Decide whether T b ∈ T (X) or not". When X is finite or countable, using a straightforward argument, we prove that the two problems are equivalent almost surely regardless the projected dimension. However, this result is only of theoretical interest, possibly due to round-off errors in floating point operations which make its practical application difficult. We address this issue by introducing a threshold τ > 0 and study the corresponding "thresholded" problem: "Decide whether dist (T b, T (X)) ≥ τ ". In the case when X may be uncountable, we prove that the original and projected problems are also equivalent if the projected dimension d is proportional to some intrinsic dimension of the set X. In particular, we employ the definition of doubling dimension to prove that, if b / ∈ X, then Sb / ∈ S(X) almost surely as long as d = Ω(ddim(X)). Here, ddim(X) is the doubling dimension of X, which is defined as the smallest number such that each ball in X can be covered by at most 2 dd(X) balls of half the radius. We extend this result to the thresholded case, and obtain a more useful bound for d. It turns out that, as a consequence of that result, we are able to improve a bound of Indyk-Naor on the Nearest Neigbour Preserving embeddings by a factor of log(1/δ) ε .

In Chapter 6, we propose to apply random projections for the trust-region subproblem, which is stated as min{c x + x Qx | Ax ≤ b, x ≤ 1}. These problems arise in trust-region methods for dealing with derivative-free optimization. Let P ∈ R d×n be a random matrix sampled from Gaussian distribution, we then consider the following "projected" problem: min{c P P x + x P P QP P x | AP P x ≤ b, P x ≤ 1}, which can be reduced to min{(P c) u + u (P QP )u | AP u ≤ b, u ≤ 1} by setting u := P x. The latter problem is of low dimension and can be solved much faster than the original. However, we prove that, if u * is its optimal solution, then with high probability,

x * := P u * is a (1 + O(ε))-approximation for the original problem. This is done by using recent results about the "concentration of eigenvalues" of Gaussian matrices.

Preliminaries on Probability Theory

A probability space is mathematically defined as a triple (Ω, A, P), in which

• Ω is a non-empty set (sample space)

• A ⊆ 2 Ω is a σ-algebra over Ω (set of events) and

• P is a probability measure on A.

A family ∅ ∈ A of subsets of Ω is called a σ-algebra (over Ω) if it is closed under compliments and countable unions. More precisely,

• ∅, Ω ∈ A. is a non-empty set (sample space)

• If E ∈ A then E c := Ω \ E ∈ A. • If E 1 , E 2 , . . . ∈ A then ∞ i=1 E i ∈ A.
A function P : A → [0, 1] is called a probability measure if it is countably additive and its value over the entire sample space is equal to one. More precisely,

• If A 1 , A 2 , . . . are a countable collection of pairwise disjoint sets, then

P( ∞ i=1 A i ) = ∞ i=1 P(A i ), • P(Ω) = 1.
Each E ∈ A is called an event and P(E) is called the probability that the event E occurs.

If E ∈ A and P(E) = 1, then E is called an almost sure event.

A function

X : A → R n is called a random variable if for all Borel set Y in R, X -1 (Y ) ∈ A.
Given a random variable X, the distribution function of X, denoted by F X is defined as follows:

F X (x) := P(ω : X(ω) ≤ x) = P(X ≤ x) for all x ∈ R n .
Given a random variable X, the density function of X is any measurable function with the property that

P[X ∈ A] = X -1 A dP = A f dµ for any A ∈ A.
The following distribution functions are used in this thesis:

• Discrete distribution: X only takes values x 1 , x 2 . . ., each with probability p 1 , p 2 , . . . where 0 ≤ p i and i p i = 1.

• Rademacher distribution: X only takes values -1 and 1, each with probability 1 2 .

• Uniform distribution: X takes values in the interval [a, b] and has the density function

f (x) = 1 b -a .
• Normal distribution: X has the density function

f (x) = 1 √ 2π e -x 2 /2 .
The expectation of a random variable X is defined as follows:

• E(X) = ∞ i=1 x i p i if X has discrete distribution: P(X = x i ) = p i for i = 1, 2, . . .. • E(X) = ∞ -∞ xf (x)dx, if X has a (continuous) density function f (.).
The variance of a random variable X is defined as follows:

• Var(X) = ∞ i=1 x 2 i p i if X has discrete distribution: P(X = x i ) = p i for i = 1, 2, . . .. • Var(X) = ∞ -∞ x 2 f (x)dx, if X has a (continuous) density function f (.).
The following property, which is called union bound, will be used very often in this thesis:

Lemma 1.3.1 (Union bound). Given events A 1 , A 2 , . . . and positive numbers δ 1 , δ 2 , . . . such that for each i, the event A i occurs with probability at least 1 -δ i . Then the probability that all these events occur is at least 1 -∞ i=1 δ i .

We also use the following simple but very useful inequality:

Markov inequality: For any nonnegative random variable X and any t > 0, we have

P(X ≥ t) ≤ E(X) t .
Note that, if we have a nonnegative increasing function f , then we can apply Markov inequality to obtain

P(X ≥ t) = P(f (X) ≥ f (t)) ≤ E(f (X)) f (t) .
13

Chapter 2

Random projections and

Johnson-Lindenstrauss lemma

Johnson-Lindenstrauss lemma

One of the main motivations for the development of random projections is the so-called

Johnson-Lindenstrauss lemma (JLL), which is found by William B. Johnson and Joram Lindenstrauss in their 1984 seminal paper [START_REF] Johnson | Extensions of Lipschitz mappings into a Hilbert space[END_REF]. The lemma asserts that any subset of R m can be embedded into a low-dimension space R k (k m), whilst keeping the Euclidean distances between any two points of the set almost the same. Formally, it is stated as follows:

Theorem 2.1.1 (Johnson-Lindenstrauss Lemma [START_REF] Johnson | Extensions of Lipschitz mappings into a Hilbert space[END_REF]). Given ε ∈ (0, 1) and A = {a 1 , . . . , a n } be a set of n points in R m . Then there exists a mapping T :

R m → R k , where k = O(ε -2 log n), such that (1 -ε) a i -a j 2 ≤ T (a i ) -T (a j ) 2 ≤ (1 + ε) a i -a j 2 (2.1)
for all 1 ≤ i, j ≤ n.

To see why this theorem is important, let's imagine we have a billion of points in R m . According to JLL, we can compress these points by projecting them into

R k , with k = O(ε -2 log n) ≈ O(20 ε -2 ).
For reasonable choices of the error ε, the projected dimension k might be much smaller than m (for example, when m = 10 6 and ε = 0.01). The effect is even more significant for larger instances, mostly due to the rapid decrease of the log-function.

Note that in JLL, the magnitude of the projected dimension k only depends on the number of data points n and a predetermined error ε, but not on the original dimension m. Therefore, JLL is more meaningful for the "big-data" cases, i.e. when m and n are huge. In contrast, if m is small, then small values of ε will result in dimensions k that are larger than m. In that case the applying of JLL is not useful.

The existence of the map T in JLL is shown by probabilistic methods. In particular, T is drawn from some well-structured classes of random maps T , in such a way one can prove that the inequalities (2.1) hold for all i ≤ i, j ≤ n with some positive probability. This can be done if the random map T satisfies for all x ∈ R m :

P (1 -ε) x 2 ≤ T (x) 2 ≤ (1 + ε) x 2 > 1 - 2 (n -1)n . (2.2)
Indeed, if it is the case, we have

P (1 -ε) x i -x j 2 ≤ T (x i -x j ) 2 ≤ (1 + ε) x i -x j 2 > 1 - 2 (n -1)n ,
for all 1 ≤ i < j ≤ n. It is only left to apply the union bound for n 2 pairs of points (x i , x j ).

There are several ways to construct a random map T satisfying the requirement (2.2). In the original paper of Johnson and Lindenstrauss ([14]), T is constructed as the orthogonal projection on a k-dimensional random subspace of R m . Later on, P. Indyk and R. Motwani [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF] noticed that T can be defined simply as a random matrix whose entries are i.i.d Gaussian random variables. Another breakthrough is made by Achlioptas [START_REF] Achlioptas | Database-friendly random projections: Johnson-Lindenstrauss with binary coins[END_REF], in which the entries of T are greatly simplified to i.i.d random variables of ±1 values, each with probability 1 2 . He also gave another interesting construction

T i,j =         
+1 with probability 1 6 , 0 with probability 2 3 , -1 with probability 1 6 .

This construction is particularly useful because it only requires 1 3 of the entries to be nonzero, therefore the matrix T becomes relatively sparse. The sparsity of T leads to faster matrix-vector multiplications, which are useful in many applications.

After the discoveries of these results, many researchers continue to find more sophisticated constructions of the random map T that are suitable for specific problems. These researches can be divided into 2 main branches: faster constructions (i.e. to obtain fast matrix-vector multiplications) and sparser constructions (i.e. to obtain sparse random matrices). As opposed to the common intuition, many fastest random matrices are dense. However, sparse matrices are obvious relatively "fast".

In the next section, we will give a formal definition of random projections. Several popular constructions of random projections will be briefly introduced in Section 2.3.

For the simplicity of notations, for the rest of the thesis, we will use T (instead of T ) to denote a random map. Moreover, since we will only work with linear maps, T is also treated as a random matrix. Thus, the expression T (x) is best written as the matrix-vector product T x and T ij will stand for the (i, j)-entry of T . The terminologies "random projection", "random mapping" and "random matrix", therefore can be used exchangeable.

Definition of random projections 2.2.1 Normalized random projections

It might be useful and easy to follow if we give a formal definition of random projections (RP). However, there is no general agreement on what an RP is. Naturally, we first provide the properties that are desired and look for structures that follow them. Since we will focus on the applications of existing random projections instead of constructing new ones, for convenience, we will give the following definition (motivated by the unpublished manuscript of Jiří Matoušek [START_REF] Matoušek | Lecture notes on metric embeddings[END_REF]). It contains the property that we will mostly deal with in this thesis. Definition 2.2.1. A random linear map T : R m → R k is called a random projection (or random matrix ) if for all ε ∈ (0, 1) and all vectors x ∈ R m , we have:

P( (1 -ε) x 2 ≤ T (x) 2 ≤ (1 + ε) x 2 ) ≥ 1 -2e -Cε 2 k (2.3)
for some universal constant C > 0 (independent of m, k, ε).

It should be noted that, given an RP, one can show the existence of a map T satisfying conditions in the Johnson-Lindenstrauss lemma. Indeed, to obtain a positive probability, it

is sufficient to choose k such that 1 -2e -Cε 2 k ≥ 1 -2 (n-1
)n , and this can be done with any k > ( 2 C ) log n ε 2 . More interesting, the probability that we can successfully find such a map (by sampling) is very high. For example, if we want this probability to be at least, say 99.9%, by the union bound, we can simply choose any k such that

1 -n(n -1)e -Cε 2 k > 1 - 1 1000
.

This means k can be chosen to be k = ln(1000)+2 ln(n)

Cε 2 ≤ 7+2 ln(n) Cε 2
. Therefore, by slightly increasing the projected dimension, we almost always obtain a "good" mapping without having to re-sample.

Preservation of scalar products

From the definition, we can immediately see that an RP also preserves the scalar product with high probability. Indeed, given any x, y ∈ R n , then by applying the definition of RP on two vectors x + y, x -y and using the union bound, we have

| T x, T y -x, y | = 1 4 T (x + y) 2 -T (x -y) 2 -x + y 2 + x -y 2 ≤ 1 4 T (x + y) 2 -x + y 2 + 1 4 T (x -y) 2 -x -y 2 ≤ ε 4 ( x + y 2 + x -y 2 ) = ε 2 ( x 2 + y 2 ),
with probability at least 1 -4e -Cε 2 k . We can actually strengthen it to obtain the following useful lemma:

Lemma 2.2.2. Let T : R m → R k be a random projection and 0 < ε < 1. Then there is a universal constant C such that, for any x, y ∈ R n :

T x, T y = x, y ± ε x . y with probability at least 1 -4e -Cε 2 k .
Proof. Apply the above result for u = x x and v = y y .

Lower bounds for projected dimension

It is interesting to know whether we can obtain a lower value for the dimension k if we use a smarter construction of a map T (such as nonlinear ones). It turns out that the answer is negative, i.e. the value k = O(ε -2 log n) is almost optimal. Indeed, Noga Alon shows in ( [START_REF] Alon | Problems and results in extremal combinatorics -I[END_REF]) that there exists a set of n points such that the dimension k has to be at least k = O( log n ε 2 log(1/ε) ) in order to preserve the distances between all pairs of points. Moreover, when the mapping T is required to be linear, then Larsen and Nelson [START_REF] Kasper | The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction[END_REF]) are able to prove that k = O(ε -2 log n) is actually the best possible. Therefore, the linearity requirement of T in the definition 2.2.1 is quite natural.

Constructions of random projections

In this section, we introduce several popular constructions of random projections. We first consider sub-gaussian random matrices, the simplest case that contains many well-known constructions that are mentioned in the previous section. Then we move to fast constructions in the subsection 2.3.2. For simplicity, we will discard the scaling factor n k in the random matrix T . This does not affect the main ideas we present but makes them clearer and more concise.

Sub-gaussian random projections

Perhaps the simplest construction of a random projection is matrices with i.i.d entries which are drawn from a certain "good distribution". Some of good distributions are: Normal N (0, 1) (by Indyk and Motwani ( [START_REF] Indyk | Approximate nearest neighbors: Towards removing the curse of dimensionality[END_REF]), Rademacher (±1) (by Achlioptas [START_REF] Achlioptas | Database-friendly random projections: Johnson-Lindenstrauss with binary coins[END_REF]), Uniform U (-a, a), . . . . In [START_REF] Matoušek | On variants of the Johnson-Lindenstrauss lemma[END_REF], Matoušek shows that all these distributions turn out to be special cases of a general class of the so-called sub-Gaussian distributions. He proves that an RP can still be obtained by sampling under this general distribution. Definition 2.3.1. A random variable X is called sub-Gaussian (or to has a sub-Gaussian tail) if there are constants C, δ such that for any t > 0:

P(|X| > t) ≤ Ce -δt 2 .
A random variable X is called sub-Gaussian up to t 0 if there are constants C, δ such that for any t > t 0 :

P(|X| > t) ≤ Ce -δt 2 .
As the name suggests, this family of distributions strongly relates to Gaussian distribution.

Intuitively, a sub-Gaussian random variable has a strong tail decay property, similar to that of a Gaussian distribution. One of its useful properties is that, a linear combination of sub-Gaussian random variables (of the uniform constants C, δ) is again sub-Gaussian. Moreover, Lemma 2.3.2. Let X be a random variable with E(X) = 0. If E(e uX ) ≤ e Cu 2 for some constant C and any u > 0, then X has a sub-gaussian tail. In reverse, if Var(X) = 1 and X has a sub-gaussian tail, then E(e uX ) ≤ e Cu 2 for all u > 0 and some constant C.

The following lemma states that, the sum of squares of sub-Gaussian random projections also has a sub-Gaussian tail up to a constant. Lemma 2.3.3 (Matoušek [START_REF] Matoušek | On variants of the Johnson-Lindenstrauss lemma[END_REF]). Let Y 1 , . . . , Y k be independent random variables with E(Y j ) = 0 and Var(E) = 1 and a uniform sub-Gaussian tail. Then

Z = 1 √ k (Y 2 1 + . . . + Y 2 k -k)
has a sub-Gaussian tail up to √ k.

Now let T ∈ R k×m be a matrix whose entries are random variables with expectation 0, variance 1 k and a uniform sub-Gaussian tail. Then, for any x ∈ R m ,

T x 2 -1 = (T 1 x) 2 + . . . + (T k x) 2 -1
has the distribution the same as the variable 1 √ k Z in the above lemma. By the definition of sub-Gaussian tail, we have

Prob (| T x 2 -1| ≥ ε) = Prob (|Z| ≥ ε √ k) ≤ Ce -δε 2 k ,
which then implies that T is an RP.

Fast Johnson-Lindenstrauss transforms

In many applications, the bottle-neck in applying random projection techniques is the cost of matrix-vector multiplications. Indeed, the complexity of multiplying a k × n matrix T to a vector is of order O(kn). Even with Achlioptas' sparse construction, the computation time is only decreased by the factor of 3. Therefore, it is important to construct the random matrix T such that the operations T x can be done as fast as possible.

It is natural to expect that, the sparser the matrix T we can construct, the faster the product T x becomes. However, due to the uncertainty principle in analysis, if the vector x is also sparse, then its image under a sparse matrix T can be largely distorted. Therefore, a random projection that satisfies Johnson-Lindenstrauss lemma cannot be too sparse.

One of the ingenious ideas to construct fast random projectors is given by Ailon and Chazelle [START_REF] Ailon | The fast Johnson-Lindenstrauss transform and approximate nearest neighbors[END_REF], in which they propose the so-called Fast Johnson Lindenstrauss Transform (FJLT). The idea is to precondition a vector (possibly sparse) by an orthogonal matrix, in order to enlarge its support. After the precondition step, we obtain a "smooth" vector, which can now be projected under a sparse random projector. More precisely, a FJLT is constructed as a product of three real-valued matrices T = P HD, which are defined as follows:

• P is a k × d matrix whose elements are independently distributed as follows:

P ij =    0 with probability 1 -q ∼ N (0, 1 q ) with probability q.
Here q is a sparsity constant given by q = min{Θ(

ε p-2 log p (n) d ), 1}
• H is a d × d normalized Walsh-Hadamard matrix:

H ij = 1 √ d (-1) i-1,j-1
where i, j is the dot-product of the m-bit vectors i, j expressed in binary.

• D is a d × d diagonal matrix, where each D ii independently takes value equal to -1 or 1, each with probability 1 2 .

Note that, in the above definition, the matrices P and D are random and H is deterministic.

Moreover, both H and D are orthogonal matrices, therefore it is only expected that P obeys the low-distortion property, i.e. P y is not so different from y. However, the vectors y being considered are not the entire set of unit vectors, but are restricted to only those that have the form HDx. The two matrices H, D play the role of "smoothening" x, so that we have the following property:

Property: Given a set X of n unit vectors. Then

max x∈X HDx ∞ = O( log n √ k ),
with probability at least 1 -1 20 .

The main theorem regarding FJLT is stated as follows:

Theorem 2.3.4 ([3]).
Given a set X of n unit vectors in R n , ε < 1, and p ∈ {1, 2}. Let T be a FJLT defined as above. Then with probability at least 2/3, the following two events occur:

1. For all x ∈ X:

(1 -ε)α p ≤ T x p ≤ (1 + ε)α p , in which α 1 = k 2 π and α 2 = k.
2. The mapping T : R n → R k requires O(n log n + min{kε -2 log n, e p-4 log p+1 k}) time to compute each matrix-vector multiplication.

Chapter 3

Random projections for linear and integer programming

Restricted Linear Membership problems

Linear Programming (LP) is one of the most important and well-studied branches of optimization. An LP problem can be written in the following normal form

max{c T x | Ax = b, x ≥ 0}.
It is well-known that it can be reduced (via an easy bisection argument) to LP feasibility problems, defined as follows:

Linear Feasibility Problem(LFP). Given b ∈ R m and A ∈ R m×n . Decide whether there exists x ∈ R n + such that Ax = b.

We assume that m and n are very large integer numbers. Furthermore, as most other standard LPs, we also assume that A is a full row-rank matrix with m ≤ n.

LFP problems can obviously be solved using the simplex method. Despite the fact that simplex methods are often very efficient in practice, there are instances for which the methods run in exponential time. On the other hand, polynomial time algorithms such as interior point methods are known to scale poorly, in practice, on several classes of instances. In any case, when m and n are huge, these methods fail to solve LPF. Our purpose is to use random projections to reduce considerably either m or n to the extend that traditional methods can apply.

Note that, if a 1 , . . . , a n are the column vectors of A, then the LPF is equivalent to finding

x ≥ 0 such that b is a non-negative linear combination of a 1 , . . . , a n . In other words, the LPF is equivalent to the following cone membership problem:

Cone Membership (CM). Given b, a 1 , . . . , a n ∈ R m , decide whether b ∈ cone{a 1 , . . . , a n }.

It is known from the Johnson-Lindenstrauss lemma that there is a linear mapping T : R m → R k , where k m, such that the pairwise distances between all vector pairs (a i , a j ) undergo low distortion. We are now stipulating that the complete distance graph is a reasonable representation of the intuitive notion of "shape". Under this hypothesis, it is reasonable to expect that the image of C = cone(a 1 , . . . , a n ) under T has approximately the same shape as

C.
Thus, given an instance of CM, we expect to be able to "approximately solve" a much smaller (randomly projected) instance instead. Notice that since CM is a decision problem, "approximately" really refers to a randomized algorithm which is successful with high probability.

The LFP can be viewed as a special case of the restricted linear membership problem, which is defined as follows:

Restricted Linear Membership (RLM). Given b, a 1 , . . . , a n ∈ R m and X ⊆ R n , decide whether b ∈ lin X (a 1 , . . . , a n ), i.e. whether ∃λ ∈ X s.

t. b = n i=1 λ i a i .
RLM includes several very important classes of membership problems, such as

• When X = R n + ( or R n + ∩ { n i=1 x i = 1}
), we have the cone membership problem (or convex hull membership problem), which corresponds to Linear Programming.

• When X = Z n (or {0, 1} n ), we have the integer (binary) cone membership problem (corresponding to Integer and Binary Linear Programming -ILP).

• When X is a convex set, we have the convex linear membership problem.

• When n = d 2 and X is the set of d × d-positive semidefinite matrices, we have the semidefinite membership problem (corresponding to Semidefinite Programming-SDP).

Notation wise, every norm • is Euclidean unless otherwise specified, and we shall denote by A c the complement of an event A. Moreover, we will implicitly assume (WLOG) that a 1 , . . . , a n , b, c are unit vectors.

The following lemma shows that the kernels of random projections are "concentrated around zero". This can be seen as a direct derivation from the definition of RP. x ∈ R m be a non-zero vector. Then we have

P(T (x) = 0) ≥ 1 -2e -Ck . (3.1)
for some constant C > 0 (independent of m, k).

Proof. For any ε ∈ (0, 1) , we define the following events:

A = T (x) = 0 B = (1 -ε) x ≤ T (x) ≤ (1 + ε) x .
By Definition 2.2.1, it follows that P(B) ≥ 1 -2e -Cε 2 k for some constant C > 0 independent of m, k, ε. On the other hand, A c ∩ B = ∅, since otherwise, there is a mapping T 1 such that

T 1 (x) = 0 and (1 -ε) x ≤ T 1 (x)
, which altogether imply that x = 0 (a contradiction).

Therefore, B ⊆ A, and we have P(A) ≥ P(B) ≥ 1 -2e -Cε 2 k . This holds for all 0 < ε < 1, so

we have P(A) ≥ 1 -2e -Ck . Lemma 3.1.2.
Let T : R m → R k be a random projection as in the definition 2.2.1 and let b, a 1 , . . . , a n ∈ R m . Then for any given vector x ∈ R n , we have:

(i) If b = n i=1 x i a i then T (b) = n i=1 x i T (a i ); (ii) If b = n i=1 x i a i then P T (b) = n i=1 x i T (a i ) ≥ 1 -2e -Ck ;
(iii) If for all y ∈ X ⊆ R n where |X| is finite, we have b = n i=1 y i a i , then

P ∀y ∈ X, T (b) = n i=1 y i T (a i ) ≥ 1 -2|X|e -Ck ;
for some constant C > 0 (independent of n, k).

Proof. Point (i) follows by linearity of T , and (ii) by applying Cor. 3.1.1 to Ax -b. For (iii), we have

P ∀y ∈ X, T (b) = n i=1 y i T (a i ) = P y∈X T (b) = n i=1 y i T (a i ) = 1 -P y∈X T (b) = n i=1 y i T (a i ) c ≥ 1 - y∈X P T (b) = n i=1 y i T (a i ) c [by (ii)] ≥ 1 - y∈X 2e -Ck = 1 -2|X|e -Ck , as claimed.
This lemma can be used to solve the RLM problem when the cardinality of the restricted set X is bounded by a polynomial in n. In particular, if |X| < n d , where d is small w.r.t. n, then

P T (b) / ∈ Lin X {T (a 1 ), . . . , T (a n )} ≥ 1 -2n d e -Ck . (3.2)
Then by taking any k such that k ≥ 1 C ln( 2 δ ) + d C ln n, we obtain a probability of success of at least 1 -δ. We give an example to illustrate that such a bound for |X| is natural in many different settings.

Example 3.1.3. If X = {x ∈ {0, 1} n | n i=1 α i x i ≤ d} for some d, where 0 < α i for all 1 ≤ i ≤ n, then |X| < n d , where d = max 1≤i≤n d α i .
To see this, let α = min

1≤i≤n α i ; then n i=1 x i ≤ n i=1 α i α x i ≤ d α , which implies n i=1 x i ≤ d. Therefore |X| ≤ n 0 + n 1 + • • • + n d < n d , as claimed.
Lemma 3.1.2 also gives us an indication as to why estimating the probability that T (b) / ∈ cone{T (a 1 ), . . . , T (a n )} is not straightforward. This event can be written as an intersection of infinitely many sub-events {T (b) = n i=1 y i T (a i )} where y ∈ R n + ; even if each of these occurs with high probability, their intersection might still be small. As these events are dependent, however, we still hope to find to find a useful estimation for this probability.

Projections of separating hyperplanes

In this section we show that if a hyperplane separates a point x from a closed and convex set C, then its image under a random projection T is also likely to separate T (x) from T (C).

The separating hyperplane theorem applied to cones can be stated as follows.

Theorem 3.2.1 (Separating hyperplane theorem). Given b / ∈ cone{a 1 , . . . , a n } where b, a 1 , . . . , a n ∈ R m . Then there is c ∈ R m such that c T b < 0 and c T a i ≥ 0 for all i = 1, . . . , n.

For simplicity, we will first work with pointed cone. Recall that a cone C is called pointed if and only if C ∩ -C = {0}. The associated separating hyperplane theorem is obtained by replacing all ≥ inequalities by strict ones. Without loss of generality, we can assume that c = 1. From this theorem, it immediately follows that there is a positive ε 0 such that

c T b < -ε 0 and c T a i > ε 0 for all 1 ≤ i ≤ n. Proposition 3.2.2. Given unit vectors b, a 1 , . . . , a n ∈ R m such that b / ∈ cone{a 1 , . . . , a n }. Let ε > 0 and c ∈ R m with c = 1 be such that c T b < -ε and c T a i ≥ ε for all 1 ≤ i ≤ n. Let
T : R m → R k be a random projection as in the definition 2.2.1, then

P T (b) / ∈ cone{T (a 1 ), . . . , T (a n )} ≥ 1 -4(n + 1)e -Cε 2 k
for some constant C (independent of m, n, k, ε).

Proof. Let A be the event that both (1

-ε) c -x 2 ≤ T (c -x) 2 ≤ (1 + ε) c -x 2 and (1 -ε) c + x 2 ≤ T (c + x) 2 ≤ (1 + ε) c + x 2 hold
T (c), T (b) = 1 4 ( T (c + b) 2 -T (c -b) 2 ) ≤ 1 4 ( c + b 2 -c -b 2 ) + ε 4 ( c + b 2 + c -b 2 ) = c T b + ε < 0
and similarly, for all i = 1, . . . , n, we can derive

T (c), T (a i ) ≥ c T a i -ε ≥ 0. Therefore, by Thm. 3.2.1, T (b) / ∈ cone{T (a 1 ), . . . , T (a n )}.
From this proposition, it follows that the larger ε will provide us a better probability. The largest ε can be found by solving the following optimization problem.

Separating Coefficient Problem (SCP). Given b / ∈ cone {a 1 , . . . , a n }, find ε = max c,ε {ε| ε ≥ 0, c T b ≤ -ε, c T a i ≥ ε}.
Note that ε can be extremely small when the cone C generated by a 1 , . . . , a n is almost nonpointed, i.e., the convex hull of a 1 , . . . , a n contains a point close to 0. Indeed, for any convex combination x = i λ i a i with i λ i = 1 of a i 's, we have:

x = x • c ≥ c T x = n i=1 λ i c T a i ≥ n i=1 λ i ε = ε. Therefore, ε ≤ min{ x | x ∈ conv{a 1 , . . . , a n }}.

Projection of minimum distance

In this section we show that if the distance between a point x and a closed set is positive, it remains positive with high probability after applying a random projection. First, we consider the following problem.

Convex Hull Membership (CHM). Given b, a 1 , . . . , a n ∈ R m , decide whether b ∈ conv{a 1 , . . . , a n }.

Applying random projections, we obtain the following proposition: We will not prove this proposition. Instead we will prove the following generalized result concerning the separation of two convex hulls under random projections.

Proposition 3.3.1. Given a 1 , . . . , a n ∈ R m , let C = conv{a 1 , . . . , a n }, b ∈ R m such that b / ∈ C, d = min
Proposition 3.3.2. Given two disjoint polytopes C = conv{a 1 , . . . , a n } and C * = conv{a * 1 , . . . , a * p } in R m , let d = min
x∈C,y∈C * x -y and D = max 1≤i≤n,1≤j≤p a i -a * j . Let T : R m → R k be a random projection. Then

P T (C) ∩ T (C * ) = ∅ ≥ 1 -2n 2 p 2 e -Cε 2 k (3.4) for some constant C (independent of m, n, p, k, d, D) and ε < d 2 D 2 .
Proof. Let S ε be the event that both (1

-ε) x -y 2 ≤ T (x -y) 2 ≤ (1 + ε) x -y 2 and (1-ε) x+y 2 ≤ T (x+y) 2 ≤ (1+ε) x+y 2 hold for all x, y ∈ {a i -a * j | 1 ≤ i ≤ n, 1 ≤ j ≤ p}.
Assume S ε occurs. Then for all reals λ i ≥ 0 with n i=1 λ i = 1 and γ j ≥ 0 with p j=1 γ j = 1, we have:

n i=1 λ i T (a i ) - p j=1 γ j T (a * j ) 2 = n i=1 p j=1 λ i γ j T (a i -a * j ) 2 = n i=1 p j=1 λ 2 i γ 2 j T (a i -a * j ) 2 + 2 (i,j) =(i ,j ) λ i γ j λ i γ j T (a i -a * j ), T (a i -a * j ) = n i=1 p j=1 λ 2 i γ 2 j T (a i -a * j ) 2 + 1 2 (i,j) =(i ,j ) λ i γ j λ i γ j T (a i -a * j + a i -a * j ) 2 -T (a i -a * j -a i + a * j ) 2 ≥ (1 -ε) n i=1 p j=1 λ 2 i γ 2 j a i -a * j 2 + + 1 2 (i,j) =(i ,j ) λ i γ j λ i γ j (1 -ε) a i -a * j + a i -a * j 2 -(1 + ε) a i -a * j -a i + a * j 2 = n i=1 λ i a i - p j=1 γ j a * j 2 -ε n i=1 p j=1 λ 2 i γ 2 j a i -a * j 2 + (i,j) =(i ,j ) λ i γ j λ i γ j a i -a * j 2 + a i -a * j 2 .
From the definitions of d and D, we have:

n i=1 λ i T (a i ) - p j=1 γ j T (a * j ) 2 ≥ d 2 -εD 2 n i=1 p j=1 λ 2 i γ 2 j + 2 (i,j) =(i ,j ) λ i γ j λ i γ j ≥ d 2 -εD 2 > 0 due to the choice of ε < d 2 D 2 .
In summary, if S ε occurs, then T (C) and T (C * ) are disjoint. Thus, by the definition of random projection and the union bound,

P(T (C) ∩ T (C * ) = ∅) ≥ P(S ε ) ≥ 1 -2 np) 2 e -Cε 2 k
for some constant C > 0. Now we assume that b, c, a 1 , . . . , a n are all unit vectors. In order to deal with the CM problem, we consider the so-called A-norm of x ∈ cone{a 1 , . . . , a n } as

x A = min n i=1 λ i λ ≥ 0 ∧ x = n i=1 λ i a i . For each x ∈ cone{a 1 , . . . , a n }, we say that λ ∈ R n + yields a minimal A-representation of x if and only if n i=1 λ i = x A . We define µ A = max{ x A | x ∈ cone{a 1 , . . . , a n } ∧ x ≤ 1}; then, for all x ∈ cone{a 1 , . . . , a n }, x ≤ x A ≤ µ A x .
In particular µ A ≥ 1. Note that µ A serves as a measure of worst-case distortion when we move from Euclidean to • A norm.

P( T (b) / ∈ cone{T (a 1 ), . . . , T (a n )} ) ≥ 1 -2n(n + 1)e -Cε 2 k (3.5) for some constant C (independent of m, n, k, d), in which ε = d 2 µ 2 A +2 √ 1-d 2 µ A +1 .
Proof. For any 0 < ε < 1, let S ε be the event that both (1 -ε) x -y 2 ≤ T (x -y) 2 ≤ (1 + ε) x-y 2 and (1-ε) x+y 2 ≤ T (x+y) 2 ≤ (1+ε) x+y 2 hold for all x, y ∈ {b, a 1 , . . . , a n }.

By definition of random projection and the union bound, we have

P(S ε ) ≥ 1 -4 n + 1 2 e -Cε 2 k = 1 -2n(n + 1)e -Cε 2 k
for some constant C (independent of m, n, k, d). We will prove that if S ε occurs, then we have T (b) / ∈ cone{T (a 1 ), . . . , T (a n )}. Assume that S ε occurs. Consider an arbitrary x ∈ cone{a 1 , . . . , a n } and let n i=1 λ i a i be the minimal A-representation of x. Then we have:

T (b) -T (x) 2 = T (b) - n i=1 λ i T (a i ) 2 = T (b) 2 + n i=1 λ 2 i T (a i ) 2 -2 n i=1 λ i T (b), T (a i ) + 2 1≤i<j≤n λ i λ j T (a i ), T (a j ) = T (b) 2 + n i=1 λ 2 i T (a i ) 2 + n i=1 λ i 2 ( T (b-a i ) 2 -T (b+a i ) 2 )+ 1≤i<j≤n λ i λ j 2 ( T (a i +a j ) 2 -T (a i -a j ) 2 ) ≥ (1 -ε) b 2 + (1 -ε) n i=1 λ 2 i a i 2 + n i=1 λ i 2 ((1 -ε) b -a i 2 -(1 + ε) b + a i 2 ) + 1≤i<j≤n λ i λ j 2 ((1 -ε) a i + a j 2 -(1 + ε) a i -a j 2 ),
λ i a i 2 -ε 1 + n i=1 λ 2 i + 2 n i=1 λ i + 2 i<j λ i λ j = b - n i=1 λ i a i 2 -ε 1 + n i=1 λ i 2 = b -x 2 -ε 1 + x A 2
Denote by α = x and let p be the projection of b to cone{a 1 , . . . , a n }, which implies

b -p = min{ b -x | x ∈ cone{a 1 , . . . , a n }}.
Claim. For all b, x, α, p given above, we have b -

x 2 ≥ α 2 -2α p + 1.
By this claim (proved later), we have:

T (b) -T (x) 2 ≥ α 2 -2α p + 1 -ε 1 + x A 2 ≥ α 2 -2α p + 1 -ε 1 + µ A α 2 = 1 -εµ 2 A α 2 -2 p + εµ A α + (1 -ε).
The last expression can be viewed as a quadratic function with respect to α. We will prove this function is nonnegative for all α ∈ R. This is equivalent to

p + εµ A 2 -1 -εµ 2 A (1 -ε) ≤ 0 ⇔ µ 2 A + 2 p µ A + 1 ε ≤ 1 -p 2 ⇔ ε ≤ 1 -p 2 µ 2 A + 2 p µ A + 1 = d 2 µ 2 A + 2 p µ A + 1
, which holds for the choice of ε as in the hypothesis. In summary, if the event S ε occurs, then

T (b) -T (x) 2 > 0 for all x ∈ cone{a 1 , . . . , a n }, i.e. T (x) / ∈ cone{T (a 1 ), . . . , T (a n )}. Thus, P(T (b) / ∈ T C) ≥ P(S ε ) ≥ 1 -2n(n + 1)e -Cε 2 k
as claimed.

Proof of the claim. If x = 0 then the claim is trivially true, since b -

x 2 = b 2 = 1 = α 2 -2α p + 1.
Hence we assume x = 0. First consider the case p = 0. By Pythagoras' theorem, we must have

d 2 = 1 -p 2 . We denote by z = p α x, then z = p . Set δ = α p , we have b -x 2 = b -δz 2 = (1 -δ) b 2 + (δ 2 -δ) z 2 + δ b -z 2 = (1 -δ) + (δ 2 -δ) p 2 + δ b -z 2 ≥ (1 -δ) + (δ 2 -δ) p 2 + δd 2 = (1 -δ) + (δ 2 -δ) p 2 + δ(1 -p 2 ) = δ 2 p 2 -2δ p 2 + 1 = α 2 -2α p + 1.
Next, we consider the case p = 0. In this case we have b T (x) ≤ 0 for all x ∈ cone{a 1 , . . . , a n }.

Indeed, for an arbitrary δ > 0,

0 ≤ 1 δ ( b -δx 2 -1) = 1 δ (1 + δ 2 x 2 -2δb T x -1) = δ x 2 -2b T x which tends to -2b T x when δ → 0 + . Therefore b -x 2 = 1 -2b T x + x 2 ≥ x 2 + 1 = α 2 -2α p + 1,
which proves the claim.

Certificates for projected problems

In this section, we will prove that, under certain assumptions, the solutions we obtain by solving the projected feasibility problem are not likely to be solutions for the original problems.

They are unfortunately negative results, which reflects the fact that we cannot simply solve the projected problem to obtain a solution but need a smarter way to deal with it.

In the first proposition, we assume that a solution is found uniformly in the feasible set of the projected problem. However, this assumption does not hold if we use some popular methods (such as simplex) because in these cases we rather end up with extreme points. We make use of this observation in our second proposition.

Recall that, we want to study the relationship between the linear feasibility problem (LFP):

Decide whether there exists

x ∈ R n such that Ax = b ∧ x ≥ 0.
O v = {x ≥ 0 | Ax -b = v} ∩ P
Notice that here O 0 = O. We need to prove that Prob(x * ∈ O) = 0.

Proof. Assume for contradiction that

Prob(x * ∈ O) = p > 0.
We will prove that there exists δ > 0 and a family V of infinitely many v ∈ ker(T ) such For all N ≥ N and for all x ∈ O, we denote

that Prob(x * ∈ O v ) ≥ δ > 0. Since (O v ) v∈V is
x N = x+x 2 -1 N x. Then we have Ax N = b-1 N Ax = b + u N and x N = x 2 + ( x 2 -x N ) ≥ 0. Therefore, x + O 2 - 1 N x ⊆ O u N which implies that, for all N ≥ N , Prob(x * ∈ O u N ) = µ(O u N ) ≥ µ( x + O 2 ) ≥ cµ(O) = cp > 0
for some constant c > 0. The proposition is proved. For consistency, we use the same notations O, P as before to denote the feasible sets of the LFP and its projected problem. We also denote by O * , P * their vertex sets, respectively.

Proof. For contradiction, we assume that x * is also a certificate for the LFP. Then we claim that x * is an extreme point of the LFP feasible set, i.e. x * ∈ O * . Indeed, if this does not hold, then there are two distinct x 1 , x 2 ∈ O such that x * = 1 2 (x 1 + x 2 ). However, since O ⊆ P, then both x 1 , x 2 belong to P, which contradicts to the assumption that x * is an extreme point of the projected feasible set. where T ∈ R k×m is a real matrix. We will prove that Proposition 3.4.3. Assume that T is sampled from a probability distribution with bounded Lebesgue density, and the IFP is feasible. Then any certificate for the projected IFP will almost surely be a certificate for the original IFP.

We first prove the following simple lemma: Proof of the Proposition. Assume that x * is a (integer) certificate for the projected IFP. Let

y * = Ax * -b and let Z = {Ax -b | x ∈ Z n + }.
Then 0 belongs to Z due to the feasibility of the original IFP. Moreover, Z is countable, so the above lemma implies that (applied on

Y = Z \ {0}) ker(T ) ∩ Z = {0} almost surely.
However, y * belongs to both ker(T ) and Z, therefore, y * = 0 almost surely. In other words,

x * is a certificate for the IFP almost surely.

Preserving Optimality in LP

Until now, we have only discussed about Linear Programming in the feasible form. In this section, we will directly consider the following LP: (P ) min{c T x| Ax = b, x ≥ 0}, in which A is an R m×n matrix (m < n) with full row rank. Its projected problems is given by

(P T ) min{c T x| T Ax = T b, x ≥ 0}.
Let v(P ) and v(P T ) be the optimal objective value of the two problems (P ) and (P T ), respectively. In this section we will show that v(P ) ≈ v(P T ) with high probability. Our proof assumes that the feasible region of P is non-empty and bounded. Specifically, we assume that a constant θ > 0 is given such that there exists an optimal solution x * of P satisfying

n i=1 x * i < θ. (3.6)
For the sake of simplicity, we assume further that θ ≥ 1. This assumption is used to control the excessive flatness of the involved cones, which is required in the projected separation argument.

Transforming the cone membership problems

In this subsection, we will explain the idea of transforming a cone into another cone, so that the cone membership problem becomes easier to solve by random projection.

Given a polyhedral cone

K = n i=1 C i x i x ∈ R n + in which C 1 , .
. . , C n are column vectors of an m × n matrix C. For any u ∈ R m , we consider the following transformation φ u , defined by:

φ u (K) := n i=1 C i - 1 θ u x i x ∈ R n + .
In particular, φ u moves the origin in the direction u by a step 1/θ. For θ defined in the equation (3.6), we also consider the following set

K θ = n i=1 C i x i x ∈ R n + ∧ n i=1
x i < θ .

K θ can be seen as a set truncated from K. We shall show that φ u preserves the membership of u in the "truncated cone" K θ . Moreover, φ u , when applied to K θ , will result in a more acute cone, which is easier for us to work with.

Lemma 3.5.1. For any u ∈ R m , we have that u ∈ K θ if and only if u ∈ φ u (K).

Proof. For all 1

≤ i ≤ n, let C i = C i -1 θ u. (⇒) If u ∈ K θ , then there exists x ∈ R n + such that u = n i=1 C i x i and n i=1
x i < θ. Then u ∈ φ u (K) because it can be written as

n i=1 C i x i with x = x 1-1 θ n j=1 x j
. Note that, due to the assumption that n j=1

x j < θ, x ≥ 0 indeed.

(⇐) If u ∈ φ u (K), then there exists x ∈ R n + such that u = n i=1 C i x i .
Then u can also be written as

n i=1 C i x i , where x i = x i 1+ 1 θ n j=1 x j . Note that, n i=1 x i < θ because n i=1 x i = n i=1 x i 1 + 1 θ n i=1 x i < θ, which implies that u ∈ K θ .
Note that this result is still valid when the transformation φ u is only applied to a subset of columns of C. Given an index set I ⊆ {1, . . . , n}, we define ∀i ≤ n:

C I i = C i -1 θ u if i ∈ I C i otherwise.
We extend φ u to

φ I u (K) = n i=1 C I i x i x ∈ R n + , (3.7)
and define

K I θ = n i=1 C i x i x ∈ R n + ∧ i∈I x i < θ .
The following corollary is proved in the same way as Lemma 3.5.1, in which φ u is replaced by φ I u .

Corollary 3.5.2. For any u ∈ R m and I ⊆ {1, . . . , n}, we have u ∈ K I θ if and only if u ∈ φ I u (K).

The main approximate theorem

Given an LFP instance Ax = b ∧ x ≥ 0, where A is an m × n matrix and T is a k × m random projector. From the previous section, we know that

∃x ≥ 0 (Ax = b) ⇔ ∃x ≥ 0 (T Ax = T b)
with high probability. We remark that this also holds for a (k + h) × m random projector of the form

I h 0 T ,
where T is a k × m random projection. This allows us to claim the feasibility equivalence w.o.p. even when we only want to project a subset of rows of A. In the following, we will use this observation to handle constraints and objective function separately. In particular, we only project the constraints while keeping objective function unchanged.

If we add the constraint n i=1

x i ≤ θ to the problem P T , we obtain the following:

P T,θ ≡ min c x T Ax = T b ∧ n i=1 x i ≤ θ ∧ x ∈ R n + . (3.8)
The following theorem asserts that the optimal objective value of P can be well-approximated by that of P T,θ .

Theorem 3.5.3. Assume F(P ) is bounded and non-empty. Let y * be an optimal dual solution of P of minimal Euclidean norm. Given δ > 0, we have

v(P ) -δ ≤ v(P T,θ ) ≤ v(P ), (3.9)
with probability at least 1 -4ne -Cε 2 k , where ε < δ 2(θ+1)η , and η is O( y * ).

Proof. First, we will briefly explain the idea of the proof. Since v(P ) is the optimal objective value of problem P , for any positive δ, the value v(P ) -δ can not be attained. It means the following problem

Ax = b ∧ x ≥ 0 ∧ cx ≤ v(P ) -δ.
is infeasible. This problem can now be projected in such a way that it remains infeasible w.o.p. By writing this original problem as

c 1 A 0 x s = v(P ) -δ b , where x s ≥ 0, (3.10)
and applying a random projection of the form 1 0 0 T , where T is a k × m random projection, we will obtain the following problem, which is supposed to be infeasible w.o.p.

cx + s = v(P ) -δ T Ax = T b x ≥ 0        . (3.11)
The main idea is that, the prior information about the optimal solution x * (i.e. n i=1

x * i ≤ θ), can now be added into this new problem. It does not change the feasibility of this problem, but later can be used to transform the corresponding cone into a better one (more acute). Therefore, w.o.p., the problem

cx ≤ v(P ) -δ T Ax = T b n i=1 x i ≤ θ x ≥ 0                (3.12)
is infeasible. Hence we deduce that cx ≥ v(P ) -δ holds w.o.p. for any feasible solution x of the problem P T,θ , and that proves the LHS of Eq. (3.9). For the RHS, the proof is trivial since P T is a relaxation of P with the same objective function. Let I be the set of indices of the first n columns of Ã. Consider the transformation φ I b as defined above, using a step 1 θ instead of 1 θ , in which θ ∈ (θ, θ + 1). We define the following matrix:

A = Ã1 -1 θ b • • • Ãn -1 θ b Ãn+1
Since Eq. (3.10) is infeasible, it is easy to verify that the system:

Ãx = b n i=1 x i < θ x ≥ 0          (3.13)
is also infeasible. Then, by Cor.

x i T b, which implies that T Ãx = T b n i=1 xi < θ x ≥ 0         
is also infeasible with probability at least p (the proof is similar to that of Corollary 3.5.2).

Therefore, with probability at least p, the following optimization problem:

inf c x T Ax = T b ∧ n i=1 x i < θ ∧ x ∈ R n + .
has its optimal value greater than v(P ) -δ. Since θ > θ, it follows that with probability at least p, v(P T,θ ) ≥ v(P ) -δ, as claimed.

Proof of the claim η = O(θ y * ): We have b 2 = b 2 + (v(P ) -δ) 2 ≤ b 2 + 2v(P ) 2 = 1 + 2|c x * | ≤ 1 + 2 c ∞ . x * 1 (

by Hölder inequality)

≤ 1 + 2θ (since c 2 = 1 and x * i ≤ θ) ≤ 3θ (by the assumption that θ ≥ 1). Random projections for convex optimization with linear constraints

Introduction

For motivation, we first consider the following convex optimization problem with linear constraints: Instead of solving this problem, we can apply a random projection T ∈ R d×m to its linear constraints and study the projected version:

min{f (x) | Ax = b, x ∈ S}, in which A ∈ R m×n , b ∈ R m , f : R n → R
Projected CRLM (PCRLM). Given a convex set C ⊆ R n , A ∈ R m×n , b ∈ R m , decide whether the set {x ∈ C | T Ax = T b} is empty or not.
Usually, d is selected so that it is much smaller than m. Therefore, we are able to reduce the number of linear constraints significantly to obtain a simpler problem. We will show that the two problems are closely related under several choices of T such as sub-Gaussian random projection and randomized orthorgonal system (ROS).

In this chapter, we also discuss the noised version of this problem. Instead of requiring Ax = b, we require that they are close enough to each other. In particular, we replace it by the condition Ax -b ≤ δ for some δ > 0. In this way we can avoid the assumption m ≤ n, and we are able to assume that m is very large regardless how small the dimension n is.

Our contributions

The results in this chapter is inspired by the work of Mert Pilanci and Martin J. In this chapter, we are interested in the related but different question: what are the relations between the optimal objective functions of these two problems. We will prove that we can choose appropriate random projection T such that one objective value is the approximation of the other. This means that we no longer need to plug x back to validate the system Ax = b (or more generally Ax -b ≤ δ) but can make inference immediately from the projected problem.

This result can be interesting in the case when the access to the original data is limited or unavailable. For example, for private security, the user information is strictly confidential. We will find random projection T so that the projected problem is also infeasible, i.e.

min x∈C T Ax -T b > 0.
We consider two classes of random projections: σ-subgaussian matrices (see Section 2.3.1)

and randomized orthogonal systems (ROS, see Section 2.3.2). For σ-subgaussian matrices, we establish the relation between the two problems via the well-known concept of Gaussian width. For a given set Y ⊆ R n , the Gaussian width of Y, denoted by W(Y) is defined by

W(Y) = E g sup y∈Y | g, y |
where g is of N (0, I) distribution. Gaussian width is a very important tool used in compressed sensing [START_REF] Candès | Mathematics of sparsity (and few other things)[END_REF]. Our main result in this case is: Let T : R m → R k be a σ-subgaussian random projection. Then for any δ > 0, with probability

at least 1 -6e -c 2 kδ 2 σ 4 , the set {x ∈ C| T Ax = T b} is also empty if k > 25c 1 1 -17δ 2 W 2 (Y).
In the ROS case, our main result involve two generalized concept: Rademacher width and T -Gaussian width, which are defined respectively as follows. For any set Y ⊂ S m-1 :

R(Y) = E ε sup y∈Y | ε, y | ,
where ε ∈ {-1, +1} n is an i.i.d. vector of Rademacher variables; and

W T (Y) = E g,T sup z∈Y | g, T z √ m | .
Using these two concepts, we obtain the following result: Let T : R m → R k be an ROS random projection. Then for any δ > 0, with probability at least

1 -6 c 1 (mn) 2 + e - c 2 mδ 2 R 2 (Y)+log(mn)
, the set {x ∈ C| T Ax = T b} is also empty if

√ k > 736 1 -17 2 δ R(Y) + 6 log(mn) W T (Y).
The rest of this chapter is constructed as follows: Section 4.2 and 4.3 will be devoted to the proofs of Theorem 4.1.1 and Theorem 4.1.2. In Section 4.4, we discuss a new method to find a certificate for this system.

Random σ-subgaussian sketches

Recall from Chapter 2 that, a real-valued random variable X is said to be σ-subgaussian if one has

E(e tX ) ≤ e σ 2 t 2 2
for every t ∈ R.

Now, let T = (t ij ) ∈ R m×n be a matrix with i.i.d entries sampling from a zero-mean σ-subgaussian distribution and Var(s ij ) = 1 m . Such a matrix will be called a random σsubgaussian sketch.

Denote by Q = T T -I n×n . From [START_REF] Pilanci | Randomized sketches of convex programs with sharp guarantees[END_REF] we obtain the following important results: Lemma 4.2.1. There are universal constants c 1 , c 2 such that for any Y ⊆ S n-1 and any v ∈ S n-1 , we have

sup u∈Y u T Qu ≤ c 1 W(Y) √ m + δ with probability at least 1 -e -c 2 mδ 2 σ 4 . (4.1) sup u∈Y u T Qv ≤ 5c 1 W(Y) √ m + 3δ with probability at least 1 -3e -c 2 mδ 2 σ 4 . (4.2)
Now we will apply this lemma to prove Theorem 4.1.1.

Proof of Theorem 1:

Denote by e := x -x * . Then e belongs to the tangent cone K of the constraint set C at the optimum x * . Since x * is the minimizer of min{ Ax -b : x ∈ C}, then

Ax * -b 2 ≤ Ax -b 2 = Ax * -b 2 + 2 Ax * -b, Ae + Ae 2 .
Therefore, 2 Ax * -b, Ae + Ae 2 ≥ 0. On the other hand, since x is the minimizer of min{ T Ax -T b : x ∈ C}, then

T Ax * -T b 2 ≥ T Ax -T b 2 = T Ax * -T b 2 + 2 T Ax * -T b, T Ae + T Ae 2 . Therefore, T Ae 2 ≤ -2 T Ax * -T b, T Ae ≤ 2 T Ax * -T b . T Ae , which implies that T Ae ≤ 2 T Ax * -T b . Now we have T Ax -T b 2 = T Ax * -T b 2 + 2 T Ax * -T b, T Ae + T Ae 2 = T Ax * -T b 2 + 2 Ax * -b, Ae + Ae 2 + 2 Ax * -b, QAe + Ae, QAe ≥ T Ax * -T b 2 + 2 Ax * -b, QAe + Ae, QAe ≥ T Ax * -T b 2 -2 Ax * -b . Ae 5c 1 W(Y) √ m + 3δ -Ae 2 c 1 W(Y) √ m + δ with probability at least 1 -4e -c 2 mδ 2 σ 4
( by applying Lemma 4.2.1). For some arbitrary λ > 0 (we will fix it later), we have 2

Ax * -b . Ae ≤ λ Ax * -b 2 + 1 λ Ae 2 . Denote by ∆ 1 = 5c 1 W(Y) √ m + 3δ and ∆ 2 = c 1 W(Y) √
m + δ, and substitute them to the above expression, we have

T Ax -T b 2 ≥ T Ax * -T b 2 -λ∆ 1 Ax * -b 2 - 1 λ ∆ 1 + ∆ 2 Ae 2 (4.3)
with probability at least 1 -4e -c 2 mδ 2 σ 4 . Now, let y * = Ax * -b Ax * -b , we have

T Ax * -T b 2 = Ax * -b 2 + Ax * -b, Q(Ax * -b) ≥ Ax * -b 2 1 -c 1 W({y * }) √ m -δ ≥ (1 -∆ 2 ) Ax * -b 2 (4.4)
with probability at least 1 -e -c 2 mδ 2 σ 4 . Here, the first inequality is an direct application of Lemma 4.2.1 and the second inequality follows from the fact that W({y * }) ≤ W(Y).

Furthermore,

T Ae 2 = Ae 2 + Ae, Q(Ae) ≥ Ae 2 1 -c 1 W(Y) √ m -δ = (1 -∆ 2 ) Ae 2 , which implies Ae 2 ≤ 1 1 -∆ 2 T Ae 2 ≤ 4 1 -∆ 2 T Ax * -T b 2 (4.5)
with probability at least 1 -e -c 2 mδ 2 σ 4

(due to the fact that T Ae ≤ 2 T Ax * -T b ).

From (4.3), (4.4) and (4.5) we have

T Ax -T b 2 ≥ T Ax * -T b 2 -λ∆ 1 Ax * -b 2 -4 1 λ ∆ 1 + ∆ 2 1 -∆ 2 T Ax * -T b 2 = 1 -4 1 λ ∆ 1 + ∆ 2 1 -∆ 2 T Ax * -T b 2 -λ∆ 1 Ax * -b 2 ≥ 1 -4 1 λ ∆ 1 + ∆ 2 1 -∆ 2 (1 -∆ 2 ) Ax * -b 2 -λ∆ 1 Ax * -b 2 = (1 -∆ 2 - 4 λ ∆ 1 -4∆ 2 -λ∆ 1 ) Ax * -b 2 with probability at least 1 -6e -c 2 mδ 2 σ 4 . Select (the best possible) λ = 2, then T Ax -T b 2 ≥ (1 -4∆ 1 -5∆ 2 ) Ax * -b 2 = (1 -25c 1 W(Y) √ m -17δ) Ax * -b 2 with probability at least 1 -6e -c 2 mδ 2 σ 4 .
It follows that T Ax = T b with probability at least 1 -6e

-c 2 mδ 2 σ 4 , if m > 25c 1 1 -17δ 2 W 2 (Y),
which proves Theorem 4.1.1.

Random orthonormal systems

Sketched matrices resulted from σ-subgaussian distributions are often dense, therefore requiring us to perform expensive matrix-vector multiplications. In order to overcome that difficulty, a different kind of sketch matrices is proposed in [START_REF] Ailon | Fast dimension reduction using Rademacher series on dual BCH codes[END_REF]. The idea is to randomly sample rows from an orthogonal matrix to form the new matrix T . Formally, we define this matrix as follows: let H be an orthogonal matrix, we independently sample each row of T by

s i = √ nDH T p i ,
where p i is a vector chosen uniformly at random from the set of all n canonical basis vectors {e 1 , . . . , e n }, and D = diag (v) is a diagonal matrix of i.i.d Rademacher variables v ∈ {-1, +1} n . It is showed that if for certain choices of H (such as Walsh -Hadamard matrix), the matrix-vector product T x can be computed in O(n log m) time for any x ∈ R n . This is a huge save of time, comparing to the normal O(nm) time from an unstructured matrix.

For simplicity, we define a function Φ given by:

Φ(X ) = 8 R(X ) + 6 log(mn) W T (X ) √ m .
Then from [START_REF] Pilanci | Randomized sketches of convex programs with sharp guarantees[END_REF], we have the following important properties (note that the parameters in this lemma have been corrected based on the original proof):

Lemma 4.3.1. There are universal constants c 1 , c 2 such that for any Y ⊆ B n and any v ∈ S n-1 , we have

sup u∈Y u T Qu ≤ Φ(Y) + δ 2 with probability at least 1 -c 1 1 (mn) 2 -c 1 e - c 2 mδ 2 R 2 (Y)+log(mn) . (4.6) sup u∈Y u T Qv ≤ 21Φ(Y) + 3δ 2 with probability at least 1 -3c 1 1 (mn) 2 -3c 1 e - c 2 mδ 2 R 2 (Y)+log(mn) . (4.7)
Proof of Theorem 4.

This proof follows almost the same line as that of Theorem 4.1.1. Denote by e := x -x * .

Then similar to the previous proof, we also have:

2 Ax * -b, Ae + Ae 2 ≥ 0 (4.8) T Ae ≤ 2 T Ax * -T b . (4.9)
Then we have

T Ax -T b 2 = T Ax * -T b 2 + 2 T Ax * -T b, T Ae + T Ae 2 = T Ax * -T b 2 + 2 Ax * -b, Ae + Ae 2 + 2 Ax * -b, QAe + Ae, QAe ≥ T Ax * -T b 2 + 2 Ax * -b, QAe + Ae, QAe ≥ T Ax * -T b 2 -2 Ax * -b . Ae 21 Φ(Y) + 3δ 2 -Ae 2 Φ(Y) + δ 2 with probability at least 1 -4 c 1 (mn) 2 + c 1 e - c 2 mδ 2 R 2 (Y)+log(mn)
( by applying Lemma 4.3.1). For some arbitrary λ > 0 (we will fix it later), we have 2

Ax * -b . Ae ≤ λ Ax * -b 2 + 1 λ Ae 2 . Denote by ∆ 1 = 21 Φ(Y)+ 3δ
2 and ∆ 2 = Φ(Y)+ δ 2 , and substitute them to the above expression, then we have

T Ax -T b 2 ≥ T Ax * -T b 2 -λ∆ 1 Ax * -b 2 - 1 λ ∆ 1 + ∆ 2 Ae 2 (4.10)
with probability at least 1 -4

c 1 (mn) 2 + c 1 e - c 2 mδ 2 R 2 (Y)+log(mn)
. Now, let y * := Ax * -b Ax * -b , we have

T Ax * -T b 2 = Ax * -b 2 + Ax * -b, Q(Ax * -b) ≥ Ax * -b 2 1 -Φ({y * }) - δ 2 ≥ (1 -4Φ(Y) - δ 2 ) Ax * -b 2 (4.11)
with probability at least 1-

c 1 (mn) 2 + c 1 e - c 2 mδ 2 R 2 (Y)+log(mn)
. Here we use the fact (from the proof of Lemma 5 in [START_REF] Pilanci | Randomized sketches of convex programs with sharp guarantees[END_REF]) that Φ({y * }) ≤ 4Φ(Y).

Similar to the previous proof, we also have

T Ae 2 = Ae 2 + Ae, Q(Ae) ≥ (1 -∆ 2 ) Ae 2 , therefore Ae 2 ≤ 1 1 -∆ 2 T Ae 2 ≤ 4 1 -∆ 2 T Ax * -T b 2 (4.12)
with probability at least 1 -

c 1 (mn) 2 + c 1 e - c 2 mδ 2 R 2 (Y)+log (mn)
.

From (4.10), (4.11) and (4.12) we have

T Ax -T b 2 ≥ T Ax * -T b 2 -λ∆ 1 Ax * -b 2 -4 1 λ ∆ 1 + ∆ 2 1 -∆ 2 T Ax * -T b 2 = 1 -4 1 λ ∆ 1 + ∆ 2 1 -∆ 2 T Ax * -T b 2 -λ∆ 1 Ax * -b 2 ≥ 1 -4 1 λ ∆ 1 + ∆ 2 1 -∆ 2 1 -4Φ(Y) - δ 2 Ax * -b 2 -λ∆ 1 Ax * -b 2 ≥ 1 -4Φ(Y) - δ 2 - 4 λ ∆ 1 -4∆ 2 -λ∆ 1 Ax * -b 2 with probability at least 1 -4 c 1 (mn) 2 + e - c 2 mδ 2 R 2 (Y)+log(mn)
. (Here we simplify by using the fact

that 1 -4Φ(Y) -δ 2 < 1 -∆ 2 )
. Now select λ = 2 (the best possible), then we have

T Ax -T b 2 ≥ (1 -4Φ(Y) - δ 2 -4∆ 1 -4∆ 2 ) Ax * -b 2 = (1 -92Φ(Y) - 17 2 δ) Ax * -b 2
with probability at least 1 -6

c 1 (mn) 2 + e - c 2 mδ 2 R 2 (Y)+log(mn)
.

The last expression is positive if and only if

1 - 17 2 δ -736 R(Y) + 6 log(mn) W T (Y) √ m > 0, or equivalently, √ m > 736 1 -17 2 δ R(Y) + 6 log(mn) W T (Y),
which proves Theorem 4.1.2.

Sketch-and-project method

Assume that the CRLM problem we considered in this chapter is feasible. As shown in Chapter 3, it is not possible to find a certificate for this system just by solving the projected problem. In this section, we will propose a method for finding such a certificate. The idea is to first sketch the constrained system by a random projection, and then to project a current solution to the new sketched feasible set. Construct a random projection matrix S ∼ D 5:

x k+1 = arg min x -x k 2 s.t. SAx = Sb, x ∈ C.

Update step

For any vector x and any set Q, we will denote by

x -Q = min y∈Q x -y . Let P = {x ∈ C | Ax = b} and P S = {x ∈ C | SAx = Sb}.
Then we can rewrite the update step simply as

x k+1 = arg min x∈P S x -x k 2 .
In other word, x k -x k+1 = x k -P S .

We have the following result:

Lemma 4.4.1. Given x k , x k+1 , P, P S defined as above, then (i) For any x ∈ P , x k -x k+1 , x -x k+1 ≤ 0.

(ii) x k+1 -P 2 ≤ x k -P 2 -x k -P S 2 .
Proof. (i) Assume there is some x ∈ P such that x k -x k+1 , x -x k+1 > 0. For any λ ∈ (0, 1), let define x λ = λx+(1-λ)x k+1 . Since P ⊆ P S , x ∈ P S . Then by the convexity of P S (followed from the convexity of C), we have x λ ∈ P S . However,

x k -x λ 2 = x k -x k+1 + λ(x k+1 -x) 2 = x k -x k+1 2 + λ 2 x k+1 -x 2 -2λ x k -x k+1 , x -x k+1 < x k -x k+1 2 when λ is small enough.
But this contradicts to the definition of x k+1 .

(ii) Let denote by

x * k = arg min x∈P x -x k 2 , then x k -P 2 = x k -x * k 2 = x k -x k+1 + x k+1 -x * k 2 = x k -x k+1 2 + x k+1 -x * k 2 + 2 x k -x k+1 , x k+1 -x * k ≥ x k -x k+1 2 + x k+1 -x * k 2 (due to (i)) = x k -P S 2 + x k+1 -x * k 2 ≥ x k -P S 2 + x k+1 -P 2 ,
which proves (ii). Now, we are going to estimate the quantity x k -P S 2 for some special construction of the random matrix S. We will consider the case when the entries of S are i.i.d random variables sampled from a σ-subgaussian distribution.

Proposition 4.4.2. There are universal constants c 1 , c 2 such that, with probability at least

1 -e -c 2 dδ 2 σ 4
we have

x k+1 -P 2 ≤ W(AK) √ m + δ x k -P 2 ,
Denote by Q := S T S -E where E is the identity matrix. Then S T S = Q + E.

Proof. By the definition, we have

x k -P S 2 = min x∈C, SAx=Sb x k -x 2 .

52

Notice that, by using a penalty term, it can also be written as

max λ≥0 min x∈C x k -x 2 + λ SAx -Sb 2 . (4.13)
Indeed, if we denote by L λ = min x∈C x k -x 2 + λ SAx -Sb 2 for each λ ≥ 0. Then due to

x k+1 ∈ C, we have

L λ ≤ x k -x k+1 2 + λ SAx k+1 -Sb 2 = x k -P S 2 ,
which proves that the value in (4.13) is smaller than or equal to x k -P S 2 . But when λ ≥ 0 is very large, the penalty becomes so expensive that it forces SAx = Sb, and in those cases,

L λ = x k -P S 2 .
The claim is proved. Now, for any λ ≥ 0, we have,

L λ = min x∈C x k -x 2 + λ SAx -Sb 2 = min x∈C x k -x 2 + λ S(Ax -b), S(Ax -b) = min x∈C x k -x 2 + λ S T S(Ax -b), Ax -b = min x∈C x k -x 2 + +λ Ax -b 2 + λ Q(Ax -b), Ax -b . = min x∈C x k -x 2 + +λ Ax -b 2 -λ Ax -b 2 W(AK) √ m + δ
with probability at least 1 -δ. Therefore, we have

L λ ≥ 1 - W(AK) √ m -δ min x∈C x k -x 2 + λ Ax -b 2
Therefore, we have

x k -P S 2 = max λ≥0 L λ ≥ 1 - W(AK) √ m -δ max λ≥0 min x∈C x k -x 2 + λ Ax -b 2 = 1 - W(AK) √ m -δ min x∈C, Ax=b x k -x 2 = 1 - W(AK) √ m -δ x k -P 2
with probability at least 1 -δ. Therefore, we have, from part (ii) of Lemma ,

x k+1 -P 2 ≤ x k -P 2 -x k -P S 2 ≤ W(AK) √ m + δ x k -P 2 ,
with probability at least 1 -δ. Proof. We assume that d ≥ 3. For any x ∈ S, by the linearity of T , we have:

Prob T (b -x) ≤ τ = Prob T b -x b -x ≤ τ b -x ≤ Prob T b -x b -x ≤ τ R < τ d R d ,
due to (5.1). Therefore, by the union bound,

Prob min x∈S T (b) -T (x) > τ = 1 -Prob min x∈S T (b) -T (x) ≤ τ ≥ 1 - x∈S Prob T (b) -T (x) ≤ τ > 1 -|S| τ d R d .
The RHS is greater than or equal to 1 -δ if and only if

R d τ d ≥ |S| δ , which is equivalent to d ≥ log( |S| δ ) log( R τ ) , as claimed.
Note that R is often unknown and can be arbitrarily small. However, if both b, S are integral and τ < 1, then R ≥ 1 and we can select d >

Sets with low doubling dimensions

In many real-world applications, the data set S is not finite or countable, but it lies in some intrinsically low-dimensional space. Examples of such sets are various, including human motion records, speed signals, image and text data ( [START_REF] Dasgupta | Random projection trees and low dimensional manifolds[END_REF][START_REF] Bingham | Random projection in dimensionality reduction: Applications to image and text data[END_REF]). Random projections can provide a tool to extract the full information of the set, despite of the (high) dimension of the ambient space that it is embedded in.

In this section, we will use doubling dimension as a measure for the intrinsic dimension of a set. Let denote by B(x, r) = {y ∈ S : y -x ≤ r}, i.e. the closed ball centered at x with radius r > 0 (w.r.t S). We use the following definition: One popular example of doubling spaces is a Euclidean space R m . In this case, it is wellknown that its doubling dimension is a constant factor of m ( [START_REF] Verger-Gaugry | Covering a ball with smaller equal balls in R n[END_REF][START_REF] Gupta | Bounded geometries, fractals, and low-distortion embeddings[END_REF]). However, there are cases where the set S ⊆ R m is of much lower doubling dimension. It is also easy to see that Proof. Let d ≥ C log 2 (λ S ) for some universal constant C (large).

Assume that R > 0 is the distance between b and the set S. Let ε i , ∆ i , i = 0, 1, 2 . . . and R = r 0 < r 1 < r 2 < . . . be positive scalars (their values will be defined later). For each k = 1, 2, 3, . . . we define an annulus

X k = S ∩ B(b, r k ) B(b, r k-1 ).
Since X k ⊆ S∩B(b, r k ), by Lemma 5.3.2 we can find a point set

S k ⊆ S of size |S k | ≤ λ log 2 ( r k ε k ) S such that X k ⊆ s∈S k B(s, ε k ).
Hence, for any x ∈ X k , there is s ∈ S k such that x -s < ε k . Moreover, by the triangle inequality, any such

s satisfies r k-1 -ε k < s -b < r k + ε k (since x is inside the annuli X k ).
So without loss of generality we can assume that

S k ⊆ B(b, r k + ε k ) B(b, r k-1 -ε k ).
Using the union bound, we have:

Prob ∃x ∈ S s.t T (x) = T (b) = Prob ∃x ∈ ∞ k=1 X k s.t T (x) = T (b) ≤ ∞ k=1 Prob ∃x ∈ X k s.t T (x) = T (b) .
Now, we will try to estimate the individual probabilities inside this sum.

For each k ≥ 1, we denote by E k the event that:

∃s ∈ S k , ∃x ∈ X k ∩ B(s, ε k ) s.t. T s -T x > ∆ k .

Then we have

Prob ∃x ∈ X k s.t T (x) = T (b) ≤ Prob (∃x ∈ X k s.t T (x) = T (b)) ∧ E c k + Prob(E k ) (5.12)
For the second term in (5.12), by the union bound, we have

Prob(E k ) ≤ s∈S k Prob ∃x ∈ X k ∩ B(s, ε k ) s.t. T s -T x > ∆ k .
If we denote by X s k = {x -s| x ∈ X k }, then the RHS can be written as

s∈S k Prob ∃(x -s) ∈ X s k ∩ B(0, ε k ) s.t. T s -T x > ∆ k = s∈S k Prob ∃u ∈ X s k ∩ B(0, ε k ) s.t. T u > ∆ k ≤ s∈S k e -c 1 d( ∆ k ε k ) 2
(for the universal constant c 1 in Lemma 5.3.3)

≤ λ log 2 ( r k ε k ) S e -c 1 d( ∆ k ε k ) 2
.

(Note that here we must choose ∆ k ≥ 6ε k in order to apply the Lemma 5.3.3).

For the first term in (5.12), we have

Prob (∃x ∈ X k s.t T (x) = T (b)) ∧ E c k ≤ Prob ∃x ∈ X k , s ∈ S k ∩ B(x, ε k ) s.t T (x) = T (b) ∧ T (s) -T (x) ≤ ∆ k ≤ Prob ∃s ∈ S k s.t T (s) -T (b) < ∆ k ≤ λ log 2 ( r k ε k ) S Prob T (z) < ∆ k r k-1 -ε k for some unit vector z ≤ λ log 2 ( r k ε k ) S ( ∆ k r k-1 -ε k ) d (by inequality 5.8).
Putting all the estimations we have obtained together, we have:

Prob ∃x ∈ S s.t T (x) = T (b) ≤ ∞ k=1 λ log 2 ( r k ε k ) S e -c 1 d( ∆ k ε k ) 2 + ( ∆ k r k-1 -ε k ) d .
(5.13)

Next, we will show that there are choices of ε k , ∆ k , r k such that the RHS of (5.13) can be as small as needed.

Choices of ε k , ∆ k , r k : For some N > 1 large, we will choose ε k , ∆ k , r k as follows:

1. ε k = ε, for some ε > 0.

2. ∆ k = N kε

3. r k = (N 2 (k + 1) 2 + 1)ε
Now the RHS of (5.13) can be rewritten as follows

∞ k=1 λ log 2 (N 2 (k+1) 2 +1) S e -c 1 d(N k) 2 + ( 1 N k ) d ≤ ∞ k=1 λ 3 log 2 (N k) S e -c 1 d(N k) 2 + ( 1 N k ) d ≤ ∞ k=1 2 3 ddim(S) log 2 (N k) e -c 1 d(N k) 2 + ( 1 N k ) d .
(5.14)

Note that 2 3 ddim(S) log 2 (N k) does not increase fast enough compared to the decreasing speeds of both e -c 1 d(N k) 2 and ( 1 N k ) d when d ≥ Cddim(S) with C large enough (and also independent of N ). Therefore, there are universal constants c 2 , c 3 > 0 such that the value of (5.14) is less than or equal to

∞ k=1 e -c 2 (N k) 2 + ∞ k=1 ( 1 N k ) c 3 d (5.15)
Both the two infinite sums tend to 0 when N tends to ∞. This means that

Prob ∃x ∈ S s.t T (x) = T (b) = 0,
which proves our theorem.

Our next result in this section is an extension of Thm. 5.3.4 to the threshold case. 1-κ ) for some universal constant C (large). As before, let ε i , ∆ i , i = 0, 1, 2 . . . and r = r 0 < r 1 < r 2 < . . . be positive scalars whose values will be decided later.

The annuli X k and point sets S k are also defined similarly. Using the union bound, now we have:

Prob ∃x ∈ S s.t T (x) -T (b) < τ = Prob ∃x ∈ ∞ k=1 X k s.t T (x) -T (b) < τ ≤ ∞ k=1 Prob ∃x ∈ X k s.t T (x) -T (b) < τ .
Now, we will try to estimate the individual probabilities inside this sum.

For each k ≥ 1, we denote by E k the event that:

∃s ∈ S k , ∃x ∈ X k ∩ B(s, ε k ) s.t. T s -T x > ∆ k .
(5.16)

Then we have

Prob ∃x ∈ X k s.t T (x) -T (b) < τ ≤ Prob (∃x ∈ X k s.t T (x) -T (b) < τ ) ∧ E c k + Prob(E k ) (5.17)
For the second term in (5.17), from the previous proof, we already had:

Prob(E k ) ≤ λ log 2 ( r k ε k ) S e -c 1 d( ∆ k ε k ) 2 .
(5.18) (Note that here we must choose ∆ k ≥ 6ε k in order to apply the Lemma 5.3.3). Now, for the first term in (5.17), we have

Prob (∃x ∈ X k s.t T (x) -T (b) < τ ) ∧ E c k ≤ Prob ∃x ∈ X k , s ∈ S k ∩ B(x, ε k ) s.t T (x) -T (b) < τ ∧ T (s) -T (x) ≤ ∆ k ≤ Prob ∃s ∈ S k s.t T (s) -T (b) < ∆ k + τ (by triangle inequality) ≤    λ log 2 ( r k ε k ) S Prob T (z) < ∆ k +τ r k-1 -ε k for some unit vector z if k ≥ 2 λ log 2 ( r 1 ε 1 ) S Prob T (z) < ∆ 1 +τ r for some unit vector z if k = 1 ≤    λ log 2 ( r k ε k ) S ( ∆ k +τ r k-1 -ε k ) d if k ≥ 2 λ log 2 ( r k ε k ) S ( ∆ 1 +τ r ) d if k = 1.
Putting all the estimations we have obtained together, we have:

Prob ∃x ∈ S s.t T (x) -T (b) < τ ≤ ∞ k=1 λ log 2 ( r k ε k ) S e -c 1 d( ∆ k ε k ) 2 + ∞ k=2 λ log 2 ( r k ε k ) S ( ∆ k + τ r k-1 -ε k ) d + λ log 2 ( r 1 ε 1 ) S ( ∆ 1 + τ r ) d . ( 5

.19)

Here we separate one term out, and we will prove that the remaining expression can be made as small as wanted by certain choices of parameters.

Choices of ε k , ∆ k , r k : Let N > 0 be the number such that ( 7 N +1) = r τ . From the assumption, we have N < 7κ 1-κ < 7 1-κ . We will choose ε k , ∆ k , r k as follows:

1. ε k = ε = τ N , 2. ∆ k = 6 √ kε, 3. r k = (6k + 7)ε + √ k + 1 τ .
(Our purpose is to choose the parameters so that

∆ k +τ r k-1 -ε k = 1 √ k and ∆ k ≥ 6ε k ).
From this choice, it is obvious r 0 = r. Now the RHS of (5.19) can be rewritten as follows with some large constant C:

∞ k=1 λ log 2 (6k+7+N √ k+1) S e -c 1 d(36k 2 ) + ∞ k=2 λ log 2 (6k+7+N √ k+1) S ( 1 √ k ) d + λ log 2 (13+N √ 2) S (( 6 N + 1) τ r ) d . ≤ ∞ k=1 λ c 3 log 2 (N (k+1)) S e -c 1 d(36k 2 ) + ∞ k=2 λ c 3 log 2 (N (k+1)) S ( 1 √ k ) d + λ c 2 S (( 6 N + 1) τ r ) d (
Prob [dist (T x 0 , T (X \ {x 0 })) ≤ (1 + ε)dist (x 0 , X \ {x 0 })] < δ 2 .
(5.24)

Now, assume that dist (x 0 , X \{x0}) = 1. Let set b = x 0 and S = {x ∈ X : x-x 0 ≥ 1+2ε} and τ = 1 + ε as in Theorem 5.3.5. We then have r :

= min x∈S x -b ≥ 1 + 2ε, which implies τ r ≤ 1+ε 1+2ε = 1 -ε 1+2ε < 1 -ε 2 .
Therefore, we can choose κ = 1 -ε/2. Applying Theorem 5.3.5, we have:

Prob(dist(T (b), T (S)) ≤ τ ) ≤ δ 2 (5.25) if the projected dimension d = Ω( log( λ S δ ) 1-κ ) = Ω( log( λ S δ ) ε ).
From (5.24) and (5.25), we conclude that the two required conditions hold for some

d = max O( log( 1 δ ) ε 2 ), O( log( λ S δ ) ε ) , as claimed.
solve the following problems, which are often called trust-region sub-problems:

min {m(x) | x ∈ B(c, r) ∩ D}.
Here the balls B(c, r) and the models m(.) are updated at every iteration. The newly found solutions of these problems will then be evaluated under the objective function f (.). Based on their values, we can adaptively adjust the model as well as the trust region, i.e. either to expand, contract, or switch their centers . . .

The models m(.) are often chosen to be simple so that the TR subproblems are easy to solve.

The most common choices for m(.) are linear and quadratic functions. However, when the instances are large, solving TR subproblems becomes difficult and sometimes they are the bottle-neck in applying TR methods for large-scale problems. For example, it is known that quadratic programming is NP-hard, even with only one negative eigenvalue.

In this chapter, we propose to use random projections to speed up the solving of highdimensional TR subproblems. We assume that linear and quadratic functions are used as TR models and . 2 is used for norm. Moreover, we assume that D is a polyhedron defined by explicit linear inequality constraints. When scaling properly, a TR subproblem can be rewritten as

min {x Qx + c x | Ax ≤ b, x 2 ≤ 1}, (6.1) in which Q ∈ R n×n , A ∈ R m×n , b ∈ R m .
Now, let P ∈ R d×n be a random projection with i.i.d. N (0, 1) entries, we can "project" x to P x and study the following projected problem min {x (P P QP P )x + c P P x | AP P x ≤ b, P x 2 ≤ 1}.

By setting u = P x, c = P c, A = AP , we can rewrite it as min {u

(P QP )u + c u | Au ≤ b, u 2 ≤ 1}. (6.2)
This problem is of much lower dimension than the original one, so it is expected to be much easier. However, as we will show later, with high probability, it still provides us a good approximate solution. This result is interesting, especially for DFO and black-box problems.

In these cases, it is unwise to spend too much time on solving TR subproblems and we are often happy with approximate solutions. Moreover, since the surrogate models might not even fit the true objective function, we are more or less tolerative to the small probability of failure.

Random projections for linear and quadratic models

In this section, we will explain the motivations for the study of the projected problem (6.2).

We start with the following simple lemma, which says that linear and quadratic models can be approximated well under random projections:

Approximation results

Lemma 6.2.1. Let P : R n → R d be a random projection and 0 < ε < 1. Then there is a constant C such that (i) For any x, y ∈ R n : P x, P y = x, y ± ε x . y with probability at least 1 -4e -Cε 2 d .

(ii) For any x ∈ R n and A ∈ R m×n whose rows are unit vectors:

AP T P x = Ax ± ε x     1 . . . 1    
with probability at least 1 -4me -Cε 2 d .

(iii) For any two vectors x, y ∈ R n and a square matrix Q ∈ R n×n , then with probability at least 1 -8ke -Cε 2 d , we have:

x T P T P QP T P y = x T Qy ± 3ε x . y . Q * , in which Q * is the nuclear norm of Q and k is the rank of Q.

Proof.

(i) This property has already been proved in Lemma 2.2.2, Chapter 2.

(ii) Let A 1 , . . . , A m be (unit) row vectors of A.

Then AP P x -Ax =     A 1 P P x -A 1 x . . . A m P P x -A m x     =     P A 1 , P x -A 1 , x . . . P A m , P x -A m , x     .
The claim is then followed by applying Part (i) and the union bound. the k-dimensional column vector of all 1 entries. Then

x T P T P QP T P y = (U P P x) Σ(V P P y)

= (U x ± ε x 1 k ) Σ (V y ± ε y 1 k )
with probability at least 1 -8ke -Cε 2 d (by applying part (ii) and the union bound). Moreover

(U x ± ε x 1 k ) Σ (V y ± ε y 1 k ) = x T Qy ± ε x .(1 k ΣV y) ± ε y .(x U Σ1 k ) ± ε 2 x . y . k i=1 σ i = x T Qy ± ε(σ 1 , . . . , σ k ) x V y ± y U x ± ε 2 x . y . k i=1 σ i .
Therefore,

|x T P T P QP T P y -x T Qy| ≤ x . y .(2ε k i=1 σ 2 i + ε 2 k i=1 σ i ) ≤ 3ε x . y . k i=1 σ i = 3ε x . y . Q * with probability at least 1 -8ke -Cε 2 d .
It is known that singular values of random matrices often concentrate around their expectations. In the case when the random matrix is sampled from Gaussian ensemble, this phenomenon is well-understood due to many current research efforts. The following lemma, which is proved in [START_REF] Zhang | Recovering optimal solution by dual random projection[END_REF], uses this phenomenon to show that when P ∈ R d×n is a Gaussian random matrix (with the number of row significantly smaller than the number of columns), then P P is very close to the identity matrix. Lemma 6.2.2. Let P ∈ R d×n be a random matrix in which each entry is an i.i.d N (0, 1 √ n ) random variable. Then for any δ > 0 and 0 < ε < 1 2 , with probability at least 1 -δ, we have:

P P -I 2 ≤ ε provided that n ≥ (d + 1) log( 2d δ ) cε 2 ,
where . 2 is the spectral norm of matrix and c > 1 4 is some universal constant.

In order to estimate the quality of the objective values, we define another projected problem, which can be considered as a relaxation for the previous one:

min {(P c) u | AP u ≤ b + ε, u 2 ≤ 1 + ε, u ∈ R d } (P + ε )
Intuitively, these two projected problems are very close to each other when ε is small enough (under some additional assumptions). Moreover, for practical use, we need to assume that they are both feasible. Let u - ε and u + ε be optimal solutions for these two problems, respectively. Denote by x - ε = P u - ε and x + ε = P u + ε . Let x * be an optimal solution for the original problem (6.1). We will try to bound c x * between c x - ε and c x + ε , the two values that are expected to be approximately close to each other. Theorem 6.2.4. Let P ∈ R d×n be a random matrix in which each entry is an i.

i.d N (0, 1 √ n ) random variable. Let δ ∈ (0, 1). Assume further that n ≥ (d + 1) log( 2d δ ) cε 2 ,
for some universal constant c > 1 4 and

d ≥ C log(m/δ) ε 2 ,
for some universal constant C > 1.

Let x * be an optimal solution for the original problem (6.1). Then (i) With probability at least 1 -δ, the solution x - ε is feasible for the original problem (6.1). (ii) With probability at least 1 -δ, we have:

c T x - ε ≥ c T x * ≥ c T x + ε -ε c .
Proof. (i) From the previous theorem, with probability at least 1 -δ, for any feasible point u of the projected problem (P - ε ), P u is also feasible for the original problem (6.3). Therefore, it must hold also for x - ε .

(ii) From part (i), with probability at least 1 -δ, x - ε is feasible for the original problem (6.1). Therefore, we have

c T x - ε ≥ c x * ,
with probability at least 1 -δ.

Moreover, due to Lemma 6.2.1, with probability at least 1 -4e -Cε 2 d , we have c x * ≥ c P P x * -ε c . x * ≥ c P P x * -ε c , since x * ≤ 1. On the other hand, let û := P x * , due to Lemma 6.2.1, we have

AP û = AP P x * ≤ Ax * + ε x *     1 . . . 1     ≤ Ax * + ε     1 . . . 1     ≤ b + ε,
with probability at least 1 -4me -Cε 2 d , and

û = P x * ≤ (1 + ε) x * ≤ (1 + ε),
with probability at leats 1 -2e -Cε 2 d (this is the norm preservation property of random projections). Therefore, û is a feasible solution for the problem (P + ε ) with probability at least 1 -(4m + 2)e -Cε We have established that c x * is sandwiched between c T x - ε and c T x + ε . Now we will compare these two values. For simplicity, we assume that the feasible set

S * = {x ∈ R n | Ax ≤ b, x 2 ≤ 1}
is of full dimension. We associate with each set P a positive number full(P ) > 0, which is considered as a fullness measure of P and is defined as the maximum radius of any closed ball contained in P . Now, assume that full(S * ) = r * > 0.

The following lemma characterizes the fullness of S + ε with respect to r * , in which

S + ε := {u ∈ R d | AP u ≤ b + ε, u 2 ≤ 1 + ε},
that is, the feasible set of the problem (P + ε ).

Lemma 6.2.5. Let S * be of full dimension with full(S * ) = r * . Then with probability at least 1 -3δ, S + ε is also full dimensional with the fullness measure:

full(S + ε ) ≥ (1 -ε)r * .
In the proof of this lemma, we will extensively use the fact that, by Cauchy-Schwartz, for any Moreover, since B(x 0 , r * ) is contained in S * , which is the subset of the unit ball, then x 0 ≤ 1 -r * .

With probability at least 1 -δ, for all vectors u in ball(P x 0 , (1 -ε)r * ), we have

u ≤ P x 0 + (1 -ε)r * ≤ (1 + ε) x 0 + (1 -ε)r * ≤ (1 + ε)(1 -r * ) + (1 -ε)r * ≤ 1 + ε.
Therefore, by the definition of S + ε we have ball P x 0 , (1 -ε)r * ⊆ S + ε , which implies that the fullness of S + ε is at least (1 -ε)r * , with probability at least 1 -3δ. Now, assume that B(u 0 , r 0 ) is a closed ball with maximum radius that is contained in S + ε .

In order to establish the relation between u + ε and u - ε , our idea is to move u + ε a bit closer to u 0 (defined in the above lemma), so that the new point is contained in S - ε . Therefore, its objective value will be at least that of u - ε , but quite close to the objective value of u + ε .

We define û := (1 -λ)u + ε + λu 0 for some λ ∈ (0, 1) specified later. We want to find λ such that û is feasible for P - ε while its corresponding objective value is not so different from c T x + ε .

Since for all u ≤ r 0 :

AP (u 0 + u) = AP u 0 + AP u ≤ b + ε, then AP u 0 ≤ b + ε -r 0     A 1 P . . . A m P     .
Therefore, we have, with probability 1 -δ,

AP u 0 ≤ b + ε -r 0 (1 -ε)     A 1 . . . A m     v = b + ε -r 0 (1 -ε).
Hence

AP û = (1 -λ)AP u + ε + λAP u 0 ≤ b + ε -λr 0 (1 -ε) ≤ b + ε - 1 2 λr 0 ,
as we can assume w.l.o.g. that ε ≤ 1 2 . Hence, AP û ≤ b if we choose ε ≤ λ r 0 2 . Moreover let u ∈ B(u 0 , r 0 ) such that u is collinear to u 0 and u = r 0 , we have

u 0 ≤ u 0 + u -r 0 ≤ 1 + ε -r 0 , so we have û ≤ (1 -λ) u + ε + λ u 0 ≤ (1 -λ)(1 + ε) + λ(1 + ε -r 0 ) = 1 + ε -λr 0 ,
which is less than or equal to 1 -ε for ε ≤ 1 2 λr 0 .

We can choose λ = 2 ε r 0 . With this choice, û is a feasible point for the problem P - ε . Therefore, we have c P u - ε ≤ c P û = c P u + ε + λc P (u 0 -u + ε ) ≤ c P u + ε + 4(1 + ε)ε r 0 P c .

By the above Lemma, we know that r 0 ≥ (1 -ε)r * , therefore, we have:

c P u - ε ≤ c P û ≤ c P u + ε + 4(1 + ε)ε r 0 P c ≤ c P u + ε + 4(1 + ε) 2 ε (1 -ε)r * c ,
with probability at least 1 -δ. Theorem 6.2.6. With probability at least 1 -2δ, we have

c x + ε ≤ c x - ε ≤ c x + ε + 18ε r * c .
Proof. It follows directly from the above discussions, with the notice that, when 0 ≤ ε ≤ 1 2 , we can simplify:

2(1 + ε) 2 (1 -ε) ≤ 2(1 + 1 2 ) 2 (1 -1 2 )
= 9.

Trust-region subproblems with quadratic models

In this subsection, we consider the case when the surrogate models using in TR methods are quadratic and defined as follows:

min {x Qx | Ax ≤ b, x 2 ≤ 1, x ∈ R n }. (6.5)
Similar to the previous section, we also study the relations between this and two other problems:

min {u P QP u | AP u ≤ b, u 2 ≤ 1 -ε, u ∈ R d } (Q - ε )
and

min {u P QP u | AP u ≤ b + ε, u 2 ≤ 1 + ε, u ∈ R d }. (Q + ε )
We will just state the similar feasibility result in this case: Theorem 6.2.7. Let P ∈ R d×n be a random matrix in which each entry is an i.i.d N (0, 1 √ n ) random variable. Let δ ∈ (0, 1). Assume further that n ≥ (d + 1) log( 2d δ ) cε 2 , for some universal constant c > 1 4 . Then with probability at least 1 -δ, for any feasible solution u of the projected problem (Q - ε ), P u is also feasible for the original problem (6.5).

Let u - ε and u + ε be optimal solutions for these two problems, respectively. Denote by x - ε = P u - ε and x + ε = P u + ε . Let x * be an optimal solution for the original problem (6.1). We will try to bound x * Qx * between x - ε Qx - ε and x + ε Qx + ε , the two values that are expected to be approximately close to each other. Theorem 6.2.8. Let P ∈ R d×n be a random matrix in which each entry is an i.i.d N (0, for some universal constant C > 1.

Let x * be an optimal solution for the original problems (6.5). Then (i) With probability at least 1 -δ, the solution x - ε is feasible for the original problem (6.5). (ii) With probability at least 1 -δ, we have:

x - ε Qx - ε ≥ x * Qx * ≥ x + ε Qx + ε -3ε Q * .
Proof. (i) From the previous theorem, with probability at least 1 -δ, for any feasible point u of the projected problem (P - ε ), P u is also feasible for the original problem (6.5). Therefore, it must hold also for x - ε .

(ii) From part (i), with probability at least 1 -δ, x - ε is feasible for the original problem (6.5). Therefore, we have

x - ε Qx - ε ≥ x * Qx * ,
with probability at least 1 -δ.

Moreover, due to Lemma 6. with probability at leats 1 -2e -Cε 2 d (this is the norm preservation property of random projections). Therefore, û is a feasible solution for the problem (P + ε ) with probability at least 1 -(4m + 2)e -Cε 2 d . Due to the optimality of u + ε for the problem (P + ε ), it follows that

x * Qx * ≥ x * P P QP P x * -3ε

Q * = û P QP û -3ε Q * ≥ u + ε P QP u + ε -3ε Q * = x + ε Qx + ε -3ε Q * ,
with probability at least 1-(4m+6)e -Cε 2 d , which is at least 1-δ for some universal constant C.

The above result implies that the value of x * Qx * lies between x - ε Qx - ε and x + ε Qx + ε . It remains to prove that these two values are not so far from each other. For that, we also use the definition of fullness measure. We have the following result: Theorem 6.2.9. Let 0 < ε < 0.1. Then with probability at least 1 -2δ, we have

x + ε Qx + ε ≤ x - ε Qx - ε < x + ε Qx + ε + 36ε full(S * ) c .
Proof. Let B(u 0 , r 0 ) be a closed ball with maximum radius that is contained in S + ε .

We define û := (1 -λ)u + ε + λu 0 for some λ ∈ (0, 1) specified later. We want to find "small" λ such that û is feasible for Q - ε while its corresponding objective value is still close to x + ε Qx + ε .

Similar to the above proof, when we choose λ := 2 ε r 0 , then û is feasible for the problem Q - ε with probability at least 1 -δ.

Therefore, u - ε P QP u - ε is smaller than or equal to û P QP û = u + ε + λ(u 0 -u + ε ) P QP u + ε + λ(u 0 -u + ε ) = u + ε P QP u + ε + λu + ε P QP u 0 -u + ε + λ(u 0 -u + ε ) P QP u + ε + λ 2 (u 0 -u + ε ) P QP (u 0 -u + ε ).

However, from the Lemma 6.2.1 and the Cauchy-Schwartz inequality, we have

u + ε P QP u 0 -u + ε ≤ P u + ε • Q 2 • P (u 0 -u + ε ≤ (1 + ε) 2 u + ε • Q 2 • (u 0 -u + ε ≤ 2(1 + ε) 4 Q 2 (Since u + ε and u - ε ≤ 1 + ε)
Similar for other terms, then we have

û P QP û ≤ u + ε P QP u + ε + (4λ + 4λ 2 )(1 + ε) 4 Q 2 .
Since ε < 0.

Dans le chapitre 2 ,

 2 nous allons présenter brièvement les projections aléatoires et le lemme de Johnson-Lindenstrauss. Nous allons présenter plusieurs constructions des projecteurs aléatoires et expliquer la raison pour laquelle ils fonctionnent. En particulier, les matrices aléatoires sous-gaussienne seront traitées en détail, ainsi que des discussions rapides sur d'autres projections aléatoires. Dans le chapitre 3, nous étudions les problèmes d'optimisation dans leurs formes de faisabilité. En particulier, nous étudions la soi-disant problème d'adhésion linéaire restreint, qui regarde la faisabilité du système {Ax = b, x ∈ C} où C est un ensemble qui limite le choix des paramètres x. Cette classe contient de nombreux problèmes importants tels que la faisabilité linéaire et en nombres entiers. Nous proposons d'appliquer une projection aléatoire T aux 1 contraintes linéaires et d'obtenir le problème projeté correspondant: {T Ax = T b, x ∈ C}. Nous voulons trouver des conditions sur T , de sorte que les deux problèmes de faisabilité sont équivalents avec une forte probabilité. La réponse est simple quand C est fini et borné par un polynôme (en n). Dans ce cas, toute projection aléatoire T avec O (log n) lignes est suffisante. Lorsque C = R n + , nous utilisons l'idée de l'hyperplan séparateur pour séparer b du cône {Ax | x ≥ 0} et montrer que T b est toujours séparé du cône projeté {T Ax | x ≥ 0} sous certaines conditions. Si ces conditions ne tiennent pas, par exemple lorsque le cône {Ax | x ≥ 0} est non-pointue, nous employons l'idée dans le Johnson-Lindenstrauss lemme pour prouver que, si b / ∈ {Ax | x ≥ 0}, alors la distance entre b et ce cône est légèrement déformée sous T , reste donc toujours positive. Cependant, le nombre de lignes de T dépend de paramètres inconnus qui sont difficiles à estimer. Dans le chapitre 4, nous continuons à étudier le problème ci-dessus dans le cas où C est un ensemble convexe. Sous cette hypothèse, on peut définir un cône tangent K de C à x * ∈ arg min x∈C Ax -b . Nous établissons les relations entre le problème original et le problème projeté sur la base du concept de largeur gaussienne, qui est populaire dans les problèmes de compressed sensing. En particulier, nous montrons que les deux problèmes sont équivalents avec une forte probabilité pour autant que la projection aléatoire T est échantillonnée à partir des distributions sous-gaussiennes et a au moins O(W 2 (AK)) lignes, où W(AK) est le largeur Gaussienne de AK. Nous généralisons également ce résultat au cas où T est échantillonnée à partir de systèmes orthonormés randomisés afin d'exploiter leurs propriété de multiplication matrice-vecteur avec des algorithmes plus rapides. Nos résultats sont similaires à ceux de [21], mais ils sont plus utiles dans les applications de préservation de confidentialité, lorsque l'accès aux données originales A, b est limitée ou indisponible. Dans le chapitre 5, nous étudions le problème d'adhésion euclidienne: " Étant donné un vecteur b et un ensemble fermé X dans R n , décider si b ∈ X ou pas". Ceci est une généralisation du problème de l'appartenance linéaire restreinte. Nous employons une projection gaussienne aléatoire T pour intégrer à la fois b et X dans un espace de dimension inférieure et étudier la version projetée correspondant: "Décidez si T b ∈ T (X) ou non." Lorsque X est fini ou dénombrable, en utilisant un argument simple, nous montrons que les deux problèmes sont équivalents presque sûrement quelle que soit la dimension projetée. Toutefois, ce résultat n'a qu'un intérêt théorique, peut-être en raison d'erreurs d'arrondi dans les opérations à virgule flottante qui rendent difficile son application pratique. Nous abordons cette question en introduisant un seuil τ > 0 et étudier le problème correspondant seuillée:

  x ∈ D, in which x ∈ R n , D ⊆ R n and f : R n → R is a given function. The feasible set D is often defined by multiple constraints such as: bound constraints (l ≤ x ≤ u), integer constraints (x ∈ Z or {0, 1}), or general constraints (g(x) ≤ O for some g : R n → R m ).

  Σ is a diagonal matrix with nonnegative entries that are ordered in the decreasing way. The matrix T k (discussed previously) can now be written as T k = U k Σ k , by truncating the singular values in that decomposition.

Corollary 3 . 1 . 1 .

 311 Let T : R m → R k be a random projection as in the definition 2.2.1 and let

  x∈C b -x and D = max 1≤i≤n b -a i . Let T : R m → R k be a random projection as in the definition 2.2.1. Then P T (b) / ∈ T (C) ≥ 1 -2n 2 e -Cε 2 k (3.3) for some constant C (independent of m, n, k, d, D) and ε < d 2 D 2 .

Theorem 3 . 3 . 3 .

 333 Given unit vectors b, a 1 , . . . , a n ∈ R m such that b / ∈ C = cone{a 1 , . . . , a n }, let d = min x∈C b -x and T : R m → R k be a random projection as in the definition 2.2.1. Then:

  29 because of the assumption that S ε occurs. Since b = a 1 = • • • = a n = 1, the RHS can be written as b -n i=1

Proposition 3 . 4 . 1 .

 341 and it projected version (PLFP):Decide whether there exists x ∈ R n such that T Ax = T b ∧ x ≥ 0, where T ∈ R k×m is a real matrix. To keep all the following discussions meaningful, we assume that k < m and the LFP is feasible. Here we use the terminology certificate to indicate a solution x that verifies the feasibility of the associated problem. Assume that b belongs to the interior of cone(A) and x * is uniformly chosen from the feasible set of the PLFP. Then x * is almost surely not a certificate for the LFP.In a formal way, let O = {x ≥ 0 | Ax = b} and P = {x ≥ 0 | T Ax = T b} denote the feasible sets for the original and projected problems, and let x * be uniformly distributed on P, i.e. P is equipped with a uniform probability measure µ. For each v ∈ ker(T ), let

  a family of disjoint sets, we deduce that Prob x * ∈ v∈V O v ≥ v∈V δ = +∞, leading to a contradiction. Because dim(ker(T )) ≥ 1, then ker(T ) contains a segment [-u, u]. Furthermore, since 0 ∈ int{Ax -b | x ≥ 0} (due to the assumption that b belongs to the interior of cone(A)), we can choose u small enough such that [-u, u] also belongs to {Ax -b | x ≥ 0}.Also due to the assumption that b belongs to the interior of cone(A), there exists x > 0 such that Ax = b. Let x ∈ R n be such that Ax = -u. There always exists an N > 0 large enough such that 2x ≤ N x (since x > 0).

Proposition 3 . 4 . 2 .

 342 Assume that b does not belong to the boundary of cone(A B ) for any basis A B of A and x * is an extreme point of the projected feasible set. Then x * is not a certificate for the LFP.

For

  that reason, we can write x * = (x * B , x * N ), where x * B = (A B ) -1 b is a basis solution and x * N = 0 is a non-basis solution. It then follows that b ∈ cone(A B ), and due to our first assumption, b ∈ int(C B ). Let b = A B x for some x > 0. Since A B x = A B x * B , it turns out that x * B = x > 0 (due to the non-singularity of A B ). Now we have a contradiction, since every extreme point of the projected LFP has at most k non-zero components, but x * has exactly m non-zero components (m > k). The proof is finished. Please notice that the assumptions in the above two propositions hold almost surely when the instances A, b are uniformly generated. This explains the results we obtained for random instances. Now we consider the Integer Feasibility Problem (IFP) Decide whether there exists x ∈ Z n + such that Ax = b and it projected version (PIFP): Decide whether there exists x ∈ Z n such that T Ax = T b ∧ x ≥ 0,

Lemma 3 . 4 . 4 .

 344 Let ν be a probability distribution on R mk with bounded Lebesgue density. Let Y ⊆ R m be an at most countable set such that 0 / ∈ Y . Then, for a random projection T : R m → R k sampled from ν, we have 0 / ∈ T (Y ) almost surely, i.e. P 0 / ∈ T (Y ) = 1. Proof. Let f be the Lebesgue density of ν. For any 0 = y ∈ Y , consider the set E y = {T : R m → R k | T (y) = 0}. If we regard each T : R m → R 1 as a vector t ∈ R mk , then E y is a hyperplane {t ∈ R mk | y • t = 0} and we have P(T (y) = 0) = ν(E y ) = Ey f dµ ≤ f ∞ Ey dµ = 0 where µ denotes the Lebesgue measure on R m . The proof then follows by the countability of Y .

  rest of the proof, we prove that b ∈ cone( Ã) iff T b ∈ cone(T Ã) w.o.p.

3 . 5 . 2 ,

 352 it follows that b ∈ cone(A ).Let y * ∈ R m be an optimal dual solution of P of minimal Euclidean norm. By the strong duality theorem, we have y * A ≤ c and y * b = v(P ). We define ỹ = (1, -y * ) . We will prove that ỹ A > 0 and ỹ b < 0. Indeed, since ỹ Ã = c -y * A 1 ≥ 0 and ỹ b = v(P ) -δ -v(P ) = -δ < 0, then we have ỹ A = c -y * A + proves the claim. Now we apply the scalar product preservation property and the union bound, to get ( T ỹ) ( T A ) -ỹ A ∞ ≤ εη (3.15) holds with probability at least p = 1 -4ne -Cε 2 k . Here, η is the normalized constant η = max ỹ . b , max 1≤i≤n ỹ . A i , in which η = O(θ y * ) (proof is given at the end). Let us now fix ε = δ 2(θ+1)η . By (3.14) and (3.15), we have, with probability at least p, the system ( T ỹ) ( T A ) ≥ 0 ( T ỹ) ( T b) < 0 holds, which implies that the problem T A x = T b x ≥ 0 is infeasible (by Farkas' Lemma). By definition, T A x = T Ãx -1 θ n i=1

  is a convex function, and S ⊆ R n is a convex set. One example is from constrained model fitting, in which Ax = b expresses the interpolation constraints, x ∈ S restricts the choices for model parameters to a certain domain and f (x) indicates some cost (such as squared error . 2 ). Using bisection method, we can write this problem in the feasibility form as follows: Given c ∈ R, decide whether the set {x| x ∈ S, f (x) ≤ c k , Ax = b} is empty or not. Let denote by C = {x ∈ S | f (x) ≤ c}. Since f (x) is convex, C is also a convex set. Then, similar as the previous chapter, this feasibility problem can be viewed as a Convex Restricted Linear Membership problem (CRLM). Formally, we ask Convex RLM (CRLM). Given a closed convex set C ⊆ R n , A ∈ R m×n , b ∈ R m , decide whether the set {x ∈ C | Ax = b} is empty or not.

  Wainwright ([22]) on the Constrained Linear Regression problem. In that work, they propose to approximate x * ∈ arg min x∈C Ax -b by a "sketched" solution x = arg min x∈C T Ax -T b .In particular, they provide bounds for the dimension d of the projected space to ensure that Ax -b ≤ (1 + ) Ax * -b for any given > 0. Therefore, if the original CRLM is feasible, then Ax * -b = 0 and it implies that Ax = b. In other words, x provides a feasible solution for the original problem. In order to apply these results to our feasibilty setting, we first solve the projected problem, obtain a feasible solution x and plug it back to check if Ax = b or not.

  Random projections provide a way to encode the problem without leaking the data of any particular people. The ability to make a decision based only on T A, T b therefore become crucial. Now, if the original problem is feasible, i.e. {x ∈ C | Ax = b} is not empty, then there is x ∈ C such that Ax = b. It follows that T Ax = T b and the projected problem is also feasible. Therefore, we only consider the infeasible case: {x ∈ C | Ax = b} is empty. In particular, we assume that Ax * -b = min x∈C Ax -b > 0.

Theorem 4 . 1 . 1 .

 411 Assume that the set {x ∈ C| Ax = b} is empty. Denote by Y = AK ∩ S n-1 , in which K is the tangent cone of the constraint set C at an optimum x * = arg min x∈C Ax -b .

Theorem 4 . 1 . 2 .

 412 Assume that the set {x ∈ C| Ax = b} is empty. Denote by Y = AK ∩ S n-1 , in which K is the tangent cone of the constraint set C at an optimum x * = arg min x∈C Ax -b .

Algorithm 1 2 : 3 :

 123 Randomized sketch-and-project (RSP) 1: parameter: D = distribution over random matrices Choose x 0 ∈ R n Initialization step for k = 0, 1, 2, . . . do 4:

53Proposition 5 . 2 . 2 .Proposition 5 . 2 . 3 .

 522523 It means that for any y = b, then T (y) = T (b) almost surely. Since the event T (b) / ∈ T (S) can be written as the intersection of at most countably many "almost sure" events T (b) = T (y) (for y ∈ S), it follows that Prob T (b) / ∈ T (S) = 1, as claimed.Proposition 5.2.1 is simple, but it looks interesting because it suggests that we only need to project the data points to a line (i.e. d = 1) and study an equivalent membership problem on a line. Furthermore, it turns out that this result remains true for a large class of random projections. Let ν be a probability distribution on R m with bounded Lebesgue density f . Let S ⊆ R m be an at most countable set such that 0 / ∈ S. Then, for a random projectionT : R m → R 1 sampled from ν, we have 0 / ∈ T (S) almost surely, i.e. Prob 0 / ∈ T (S) = 1.Proof. For any 0 = s ∈ Y , consider the setE s = {T : R m → R 1 | T (s) = 0}. If we regard each T : R m → R 1 as a vector t ∈ R m , then E s is a hyperplane {t ∈ R m | s • t = 0}and we have Prob(T (s) = 0) = ν(E s ) = Es f dµ ≤ f ∞ Es dµ = 0 where µ denotes the Lebesgue measure on R m . The proof then follows by the countability of S, similarly to Proposition 5.2.1. This idea, however, does not work in practice: we tested it by considering the ESMP given by the IPF defined on the set {x ∈ Z n + ∩ [L, U ] | Ax = b}. Numerical experiments indicate that the corresponding PESMP {x ∈ Z n + ∩ [L, U ] | T (A)x = T (b)}, with T consisting of a one-row Gaussian projection matrix, is always feasible despite the infeasibility of the original IPF. Since Prop. 5.2.1 assumes that the components of T are real numbers, the reason behind this failure is possibly due to the round-off error associated to the floating point representation used in computers. Specifically, when T (A)x is too close to T (b), floating point operations will consider them as a single point. In order to address this issue, we force the projected problems to obey stricter requirements. In particular, instead of only requiring that T (b) / ∈ T (S), we ensure that dist(T (b), T (S)) = min x∈S T (b) -T (x) > τ, (5.4) where dist denotes the Euclidean distance, and τ > 0 is a (small) given constant. With this restriction, we obtain the following result. Given τ > 0, 0 < δ < 1 and b / ∈ S ⊆ R m , where S is a finite set. Let R = min x∈S b -x > 0 and T : R m → R d be a Gaussian random projection with d ≥ Prob min x∈S T (b) -T (x) > τ > 1 -δ.

Definition 5 . 3 . 1 .

 531 The doubling constant of a set S ⊆ R m is the smallest number λ S such that any closed ball in S can be covered by at most λ S closed balls of half the radius. A set S ⊆ R m is called a doubling set if it has a finite doubling constant. The number log 2 (λ S ) is then called the doubling dimension of S and denoted by ddim (S).

Theorem 5 . 3 . 5 .

 535 Let b / ∈ S where S ⊆ R m is a closed doubling set, T : R m → R d be a Gaussian random projection, and r = min x∈S b -x . Let κ < 1 be some fixed constant. Then for all 0 < δ < 1 and 0 < τ < κr, we have Prob(dist(T (p), T (S)) > τ ) > 1 -δ if the projected dimension d = Ω(

(

  iii) Let Q = U ΣV T be the Singular Value Decomposition of Q. Here U, V are (n × k)real matrices with orthogonal unit column vectors u 1 , . . . , u k and v 1 , . . . , v k , respectively and Σ = diag(σ 1 , . . . , σ k ) is a diagonal matrix with positive entries. Denote by 1 k = (1, . . . , 1)

  2 d . Due to the optimality of u + ε for the problem (P + ε ), it follows thatc x * ≥ c P P x * -ε c = c P û -ε c ≥ c P u + ε -ε c = c x + ε -ε c ,with probability at least 1-(4m+6)e -Cε 2 d , which is at least 1-δ for some universal constant C.

  row vector a ∈ R n sup u ≤r au = r a . Proof. For any i ∈ [1, ..., n] let A i denotes the ith row of A. Let B(x 0 , r * ) be a closed ball contained in S * . Then for any x ∈ R n with x ≤ r * , we have A(x 0 + x) = Ax 0 + Ax ≤ b, which implies that for any i ∈ [1, ..., n],b i ≥ (Ax 0 ) i + sup x ≤r * A i x = (Ax 0 ) i + r * A i = (Ax 0 ) i + r * ,(6.4)hence b ≥ Ax 0 + r * By Lemma 6.2.1, with probability at least 1 -δ, we haveAP P x 0 ≤ Ax 0 + ε ≤ b + ε -r * .Let u ∈ R n with u ≤ (1 -ε)r * , for any i ∈ [1, ..., n], we have:(AP (P x 0 + u)) i ≤ b i + ε -r * + (AP ) i u = b i + ε -r * + A i P uwhere (AP ) i denotes the ith row of AP . Hence, by Cauchy-Schwartz, (AP (Px 0 + u)) i ≤ b i + ε -r * + (1 -ε)r * A i PUsing Eq. (??), we can prove that with probability 1 -2me -Cε 2 d ≥ 1 -δ, we have that forall i ∈ [1, ..., m], A i P ≤ (1 + ε) A i = (1 + ε). Hence AP (P x 0 + u) ≤ b i + ε -r * + (1 -ε)r * (1 + ε) ≤ b + ε therefore,with probability 1 -2δ the closed ball B * centered at P x 0 with radius (1 -ε)r * is contained in {u : AP u ≤ b + ε}.

2 . 1 ,

 21 with probability at least 1 -8ke -Cε 2 d , where k is the rank of Q, we havex * Qx * ≥ x * P P QP P x * -3ε x * 2 . Q * ≥ x * P P QP P x * -3ε Q * , since x * ≤ 1.On the other hand, let û := P x * , due to Lemma 6.2.1, we haveAP û = AP P x * ≤ Ax * + ε x * b + ε,with probability at least 1 -4me -Cε 2 d , andû = P x * ≤ (1 + ε) x * ≤ (1 + ε),

Table 3 .

 3 1: LP: above, IP: below. Acc.: accuracy (% feas./infas. agreement), Orig.: original (CPU),

	Proj.: projected instances (CPU).
				Uniform	Exponential			Gamma
	m	n	Acc.	Orig. Proj.	Acc.	Orig.	Proj.	Acc.	Orig.	Proj.
	600		99.5%	1.57s 0.12s 93.7%	1.66s	0.12s 94.6%	1.64s	0.11s
	700		99.5%	2.39s 0.12s 92.8%	2.19s	0.12s 93.1%	2.15s	0.11s
	800		99.5%	2.55s 0.11s 95.0%	2.91s	0.11s 97.3% 2.78 s	0.11s
	900		99.6%	3.49s 0.12s 96.1%	3.65s	0.13s 97.0%	3.57s	0.13s
	1000 99.5% 16.54s 0.20s 93.0% 18.10s	0.20s 91.2% 17.58s	0.20s
	1200 99.6% 22.46s 0.23s 95.7% 22.46s	0.20s 95.7% 22.58s	0.22s
	1400 100% 31.08s 0.24s 93.2% 35.24s	0.26s 95.0% 31.06s	0.23s
	1500 99.4% 48.89s 0.30s 91.3% 51.23s	0.31s 90.1% 51.08s	0.31
	1600 99.8% 58.36s 0.34s 93.8% 58.87s	0.34s 95.9% 60.35s 0.358s
	500		100% 20.32s 4.15s 100%	4.69s 10.56s 100%	4.25s	8.11s
	600		100% 26.41s 4.22s 100%	6.08s 10.45s 100%	5.96s	8.27s
	700		100% 38.68s 4.19s 100%	8.25s 10.67s 100%	7.93s 10.28s
	600		100% 51.20s 7.84s 100% 10.31s	8.47s 100%	8.78s	6.90s
	700		100% 73.73s 7.86s 100% 12.56s 10.91s 100%	9.29s	8.43s
	800		100% 117.8s 8.74s 100% 14.11s 10.71s 100% 12.29s	7.58s
	900		100% 130.1s 7.50s 100% 15.58s 10.75s 100% 15.06s	7.65s
	1000 100% 275.8s 8.84s 100% 38.57s 22.62s 100% 35.70s	8.74s

  5.20) Proof. Similar as the proof of Theorem 4.1 in ([START_REF] Indyk | Nearest neighbor preserving embeddings[END_REF]), we have: for d ≥ C

	log( 1 δ ) ε 2

  1, we have (1 + ε) 4 < 2 and we can assume that λ < 1. Then we have û P QP û < u + ε P QP u + ε + 16λ Q 2

	= u + ε P QP u + ε +	32ε r 0	(since Q 2 = 1)
	≤ u + ε P QP u + ε +	32ε (1 -ε)full(S * )	(due to Lemma 6.2.5)
	< u + ε P QP u + ε +	36ε full(S

* ) (since ε ≤ 0.1), with probability at least 1 -2δ. The proof is done.

Therefore, we conclude that η = max ỹ . b , max 1≤i≤n ỹ . A i = O(θ y * )

Computational results

Let T be the random projector, A the constraint matrix, b the RHS vector, and X either R n + in the case of LP and Z n + in the case of IP. We solve Ax = b ∧ x ∈ X and T (A)x = T (b) ∧ x ∈ X to compare accuracy and performance. In these results, A is dense. We generate (A, b) componentwise from three distributions: uniform on [0, 1], exponential, gamma. For T , we only test the best-known type of projector matrix T (y) = P y, namely P is a random k × m matrix each component of which is independently drawn from a normal N (0, 1 √ k ) distribution. All problems were solved using CPLEX 12.6 on an Intel i7 2.70GHz CPU with 16.0 GB RAM. All the computational experiments were carried out in JuMP (a modeling language for Mathematical Programming in JULIA).

Because accuracy is guaranteed for feasible instances by Lemma 3.1.2 (i), we only test infeasible LP and IP feasibility instances. For every given size m × n of the constraint matrix, we generate 10 different instances, each of which is projected using 100 randomly generated projectors P . For each size, we compute the percentage of success, defined as an infeasible original problem being reduced to an infeasible projected problem. Performance is evaluated by recording the average user CPU time taken by CPLEX to solve the original problem, and, comparatively, the time taken to perform the matrix multiplication P A plus the time taken by CPLEX to solve the projected problem.

In the above computational results, we only report the actual solver execution time (in the case of the original problem) and matrix multiplication plus solver execution (in the case of the projected problem). Lastly, although Tables 3.1 tell a successful story, we obtained less satisfactory results with other distributions. Sparse instances yielded accurate but poorly performant results. So far, this seems to be a good practical method for dense LP/IP.

Chapter 5

Gaussian random projections for general membership problems

Introduction

In this chapter we employ random projections to study the following general problem:

This is a generalization of the convex hull and cone membership problems that we consider in Chapter 2. However, in this chapter, we consider the general case where the data set S has no specific structure. We will use Gaussian random projections in our arguments to embed both b and S to a lower dimensional space, and solve its associated projected version:

Projected ESMP (PESMP). Given b ∈ R m and S ⊆ R m , and let T : R m → R d be some given mapping. Decide whether T (b) ∈ T (S).

Our objective is to investigate the relationships between ESMP and PESMP. As before, it is obvious that when b ∈ S then T (b) ∈ T (S). We are therefore only interested in the case when b / ∈ S, i.e. we want to estimate Prob(T (b) / ∈ T (S)), given that b / ∈ S.

Our contributions

In the case when S is at most countable (i.e. finite or countable), using a straightforward argument, we prove that these two problems are equivalent almost surely. However, this result is only of theoretical interest due to round-off errors in floating point operations, which make its practical application difficult. We address this issue by introducing a threshold τ > 0 and study the corresponding "thresholded" problem:

Threshold ESMP (TESMP): Given b, S, T as above. Let δ > 0. Decide whether T (b) -T (S) ≥ τ .

In the case when S may also be uncountable, we prove that ESMP and PESMP are also equivalent if the projected dimension d is proportional to some intrinsic dimension of the set S. In particular, we employ the definition of doubling dimension (defined later) to prove that, if b / ∈ S, then T (b) / ∈ T (S) almost surely as long as the projected dimension d ≥ c • ddim(S).

Here, ddim(S) is the doubling dimension of S and c is some universal constant.

We also extend this result to the threshold case, and obtain a more useful bound for d.

Finite and countable sets

In this section, we assume that S is either finite or countable. Let T ∈ R d×m be a random matrix drawn from Gaussian distribution, i.e. each entry of T is independently sampled from N (0, 1). It is well known that, for an arbitrary unit vector a ∈ S m-1 , then T a 2 is a random variable with a Chi-squared distribution χ 2 d with d degrees of freedom ( [START_REF] Mood | Introduction to the Theory of Statistics[END_REF]). Its corresponding density function is

, where Γ(•) is the gamma function. By [START_REF] Dasgupta | An elementary proof of a theorem of Johnson and Lindenstrauss[END_REF], for any 0 < δ < 1, taking z = δ d yields a cumulative distribution function (CDF)

.

(5.1) Thus, we have

or, more simply, Prob( T a ≤ δ) < δ d when d ≥ 3.

Using this estimation, we immediately obtain the following result. Proof. First, note that for any u = 0, T u = 0 holds almost certainly. Indeed, without loss of generality we can assume that u = 1. Then for any 0 < δ < 1:

ddim (S) does not depend on the dimension m. Therefore, doubling dimension becomes a powerful tool for reducing dimensions in several classes of problems such as nearest neighbor [START_REF] Krauthgamer | Navigating nets: Simple algorithms for proximity search[END_REF][START_REF] Indyk | Nearest neighbor preserving embeddings[END_REF], low-distortion embeddings [START_REF] Agarwal | Embeddings on surfaces, curves, and moving points in Euclidean space[END_REF], and clustering [START_REF] Magen | Dimensionality reductions in 2 that preserve volumes and distance to affine spaces[END_REF].

In this section, we assume that ddim (S) is relatively small compared to m. Note that, computing the doubling dimension of S is generally NP-hard ( [START_REF] Gottlieb | Proximity algorithms for nearly doubling spaces[END_REF]). For simplicity, we assume that λ S is a power of 2, i.e. the doubling dimension of S is a positive integer number.

We shall make use of the following simple lemma.

Lemma 5.3.2. For any b ∈ S and ε, r > 0, there is a set S 0 ⊆ S of size at most λ

(5.5)

Proof. By the definition of the doubling dimension, B(b, r) is covered by at most λ S closed balls of radius r 2 . Each of these balls in turn is covered by λ S balls of radius r 4 , and so on:

We will also use the following lemma:

(5.6)

This lemma is proved in [START_REF] Indyk | Nearest neighbor preserving embeddings[END_REF] using concentration estimations for sum of squared gaussian variables (Chi-squared distribution). In particular, we recall two important inequalities: for all δ > 0 and a mapping T as above,

Prob( T a ≤ δ) < δ d when d ≥ 3 (already used in the previous section). (5.8) For the sake of completeness, we will present the original proof ( [START_REF] Indyk | Nearest neighbor preserving embeddings[END_REF]). Here, we use an additional requirement that δ ≥ 6 instead of δ > 1 to make the proof more rigorous (than the original), however the main argument is unchanged.

Proof. Choose b = 0, r = 1 and ε k = 1 2 k in the Lemma 5.3.2. By earlier convention that B(x, r) = {y ∈ S : y -x ≤ r}, obviously we have S = B(0, 1). Then there is a set

(5.9) Therefore, for any x ∈ S, there is a sequence {0 = x 0 , x 1 , x 2 , x 3 , . . .} that converges to x, with

x k ∈ S k and x k -x k+1 ≤ 1 2 k for each k. We claim that, if T x ≥ δ, then there must be some k such that

Indeed, if no such k exists, then

Now, if we want to neglect x, we can treat x k and x k+1 (found above) as two points u, v, in

Therefore, we have

) k for some unit vector z (by the union bound).

Since δ ≥ 6, for any k ≥ 0 we have δ 3 ( 4 3 ) k ≥ 1 + δ 6 ( 4 3 ) k . Therefore, from the inequality (5.7), the above expression is less than or equal to for some universal constants c 1 , c 2 , c 3 .

It is easy to show that the expression is the big bracket is bounded above by e -c 4 d as long as

.

(5.22)

, from the Taylor series of the logarithm function. Therefore, (5.22) holds if we select

for some universal constants C.

The proof follows immediately from (5.21) and (5.23) by apply the union bound.

One of the interesting consequence of Theorem 5.3.5 is the following application to the Approximate Nearest Neighbour problem.

Corollary 5.3.6. For X ⊆ R d , ε ∈ (0, 1/2) and δ ∈ (0, 1/2), there exists

, O log( λ S δ ) ε such that for every x 0 ∈ X, with probability at least 1 -δ,

Note that, this result improves the bound provided by Indyk-Naor in ( [START_REF] Indyk | Nearest neighbor preserving embeddings[END_REF]). In that paper, the authors give the bound for the projected dimension to be

which is significantly larger than our bound.

Chapter 6

Random projections for trust-region subproblems

Derivative-free optimization and trust-region methods

Derivative-free optimization (DFO) is a branch of optimization that has attracted a lot of attentions recently. In the general form, a DFO problem is defined as follows:

in which D is a subset of R n and f (.) is a continuous function such that no derivative information about it is available. In many cases, we have to treat the objective function as a black-box. It means that we can only understand f (.) by evaluating it at a limited number of input points.

Because of the lack of derivative information, traditional gradient-based methods cannot be applied. Moreover, when the objective function is expensive, meta-heuristics such as evolutionary algorithms, simulated annealing or ant colony optimization (ACO) are not desirable, since they often require a very large number of function evaluations. Recently, trust-region (TR) method stands out as one of the most efficient methods for solving DFO. TR methods involve the construction of surrogate models to approximate the true function (locally) in small subsets of D and relying on those models to search for optimal solutions. These local subsets are called trust-regions and often chosen as closed balls with respect to certain norms.

There are several ways to update the new data points, but the most common way is to find them as minima of the current model over the current trust-region. Formally, we need to This lemma also tells us that when we go from low to high dimensions, with high probability we can ensure that the norms of all the points endure small distortions. Indeed, for any vector u ∈ R d , then P u 2 -u 2 = P u, P u -u, u = (P P -I)u, u = ±ε u 2 , due to the Cauchy-Schwarz inequality. Moreover, it implies that P 2 ≤ (1 + ε) with probability at least 1 -δ.

Trust-region subproblems with linear models

We will first work with a simple case, when the surrogate models using in TR methods are linear and defined as follows:

We will establish the relations between problem (6.3) and its corresponding projected problems:

min

We first obtain the following feasibility result: Theorem 6.2.3. Let P ∈ R d×n be a random matrix in which each entry is an i.i.d N (0,

for some universal constant c > 1 4 . Then with probability at least 1 -δ, for any feasible solution u of the projected problem (P - ε ), P u is also feasible for the original problem (6.3).

We should notice a universal property in this theorem, in which with a fixed probability, the feasibility holds for "all" (instead of a specific) vectors u.

Proof. Let u be any feasible solution for the projected problem (P - ε ) and take x = P u. Then we have Ax = AP u ≤ b and

with probability at least 1 -δ (by Lemma 6.2.2). Since u ≤ 1 -ε, we have

which proves the theorem.

Chapter 7

Concluding remarks 7.1 Summary

This thesis focuses on some applications of random projections in optimization. It shows that random projections is a potential dimension reduction tool for many important optimization problems. In order to effectively apply this technique, the desired problem should be of really high dimension. Therefore, it is suitable for problems arising from "big-data" scenarios, such as those in machine learning and image processing. The thesis studies several other popular problems.

1. Linear and Integer Programming. We first use random projections to solve LPs and IPs in their standard form. Using bisection arguments, we can transform them into feasibility problems and apply random projections to their set of linear equality constraints. We show that the original and projected feasibility problems are strongly related (under some conditions) with high probability. Taking these results as a starting point, we then develop some algorithms to solve linear programming directly (without having to use binary search), thanks to the LP duality theory.

2. Convex Programming with linear system of constraints. We next consider the feasibility problem where a linear system is accompanied by other convex constraints.

Similarly, the projected problem is formed by applying random projections to the set of linear equalities while keeping others unchanged. We consider two choices of random projections: one is sampled from a sub-gaussian distributions, one is from a randomized orthogonal system. The relations between the two problems are established through the so-called "Gaussian width". 80 3. Membership problem. We extend our study to the general case of membership problem, in which we ask whether a given point belongs to a given set . In this case, we prove that if we reach the "true dimension" of the set, we can always separate the projected point from the projected set. In order to do that, we use the concept of "doubling dimension" to quantify the intrinsic dimension of a point set. We also generalize this result to the case when a threshold distance between a point and a set is required.

4.

Trust-region subproblem. Lastly, we apply random projections to study trust-region subproblems. This is the only time we are able to reduce the number of variables but not the number of constraints. We prove that the linear and quadratic models can be well approximated by those in a lower projected dimension. We quantify the error between the two problems using the so-called "fullness measure" of a set. The results suggest that random projection can be used to study high dimensional derivative-free optimization problems, which is intractable at the current time.

Further research

• It should be noted that, if a problem consists of linear constraints, we can directly apply a random projection to them. Therefore, we are able to reduce the number of (linear) constraints. On the other hand, if those linear constraints are written in the inequality form, then we can reduce the number of variables (as in the case of the trustregion subproblems in Chapter 6). However, we can not reduce both of them. One of our future researches therefore will focus on reducing both these two quantities (at the same time): the number of variables and the number of constraints. Our intuition tells us that using random projections alone will not work, and we need to combine random projections with other dimension reduction techniques. At the moment, we are looking at the multiplicative weight update (MWU) algorithm, which seems to be a potential candidate.

• Another research direction would be to extend the results and techniques developed in this thesis to study other different problems. Currently, we are studying the use of random projection and measure concentration in semidefinite programming (SDP).

We also planned to look at several problems arising from "machine learning" such as constrained linear regression and support vector machine. They seem to be very amenable to random projection techniques.

• One of the weaknesses of this thesis is the lack of numerical tests and "real-work appli-cations". We will try to improve this facet by looking at more practical problems with similar form as those being studied here. At the moment, we are studying the "quantile regression", a problem that can be reformulated as a (dense) linear feasibility problem.

The preliminary computational results are quite promising. It seems to be the right application to illustrate the success of random projections.

• In addition to reducing dimension, we also want to investigate some side effects of random projections. For example, they turn a very ill-scaled system (of linear equalities) into a good one. Therefore, we want to know how the condition number of the projected matrix T A changes, compared to the condition number of the original matrix A. Nous nous sommes particulièrement intéressés aux cas où les dimensions du problème sont si élevés que les méthodes traditionnelles ne peuvent pas être appliquées. Dans ces conditions, au lieu de traiter directement avec les problèmes d'origine, nous appliquons des projections aléatoires pour les transformer en des problèmes de dimensions beaucoup plus faibles. Nous montrons que, tout en obtenant des problèmes beaucoup plus facile à résoudre, ces nouveaux problèmes sont de très bonnes approximations des originaux. Cela permet de suggérer que les projections aléatoires sont un outil très prometteur de réduction de dimension pour beaucoup d'autres problèmes.. Title : Random projection for high dimensional optimization.

Keywords : Dimension reduction, randomized algorithm, Johnson-Lindenstrauss lemma

Résumé : Random projection is a very useful technique for reducing data dimension and has been widely used in numerical linear algebra, image processing, computer science, machine learning and so on. A random projection is often defined as a random matrix constructed in certain ways such that it preserves many important features, including distances, inner products, volumes… of the data set. One of the most famous examples is the Johnson-Lindenstrauss lemma, which asserts that a set of m points can be projected by a random projection, to an Euclidean space of dimension O(log m) whilst still ensures that the inner distances between them approximately unchanged.

In this PhD thesis, we apply random projections to study a number of important optimization problems such as linear and integer programming, convex membership problems and derivative-free optimization. We are especially interested in the cases when the problem dimensions are so high that traditional methods can not be applied. In those circumstances, instead of dealing directly with the original problems, we apply random projections to transform them into much lower dimensional problems. We prove that, while getting much easier to solve, these new problems are very good approximation of the original ones.

It is suggested that random projection is a very promising dimension reduction tool for many other problems as well.catervis mixtae praedonum.