Charlotte Fourcroy

Faïz Gallouj

Clersé

Fabrice Decellas

Economics, Challenging the myth of non-materiality: energy consumption

Keywords: Service industries, Energy consumption, Materiality

This paper addresses the issue of energy consumption in service industries. Official energy statistics show that the amount of energy consumed in service industries is quite small, and this is explained in the theoretical literature by the presumed intangibility of these services. Our hypothesis, however, is that the energy consumed by services has been underestimated. After identifying and analyzing the full range of sources of energy consumption in service industries, we show that official energy statistics account for only a part of this consumption. Our work is based on a thorough rereading of the economics literature on services (especially concerning the definition of services and the specifics of the service provision process), done in light of our knowledge about energy consumption.

Introduction

In economic theory, services are often described as "non-material", "immaterial" or "intangible" [START_REF] Smith | The wealth of nations[END_REF]Say, 1803;[START_REF] De | Nouveaux principes d'économie politique ou De la richesse dans ses rapports avec la population[END_REF]. This non-materiality would explain their having smaller negative impact on the environment and lower energy consumption than does industry. Inasmuch as growth in recent decades has been largely driven by the development of services, a number of studies, particularly in the early 1990s, have argued that we are trending towards an ever more non-material society creating less environmental wear (Ettighoffer, 1992;[START_REF] Joseph | The internet economy and global warming, The Center for Energy and Climate Solutions SAY Jean-Baptiste[END_REF]. Against such conclusions, however, we would note that the most service-intensive countries are as a whole greater consumers of energy, with a larger ecological footprint, than countries whose tertiary sector is less developed (Gadrey, 2010). Given the vital stakes involved in bringing energy demand under control, primarily due to the threats of diminished fossil resources and climate change, it is important to come down on one side or the other of these opposing arguments and identify the conditions that might foster sustainability in the service economies.

In this study we consider the question of the non-materiality of services from the viewpoint of their energy consumption. The following are our hypotheses: (1) service businesses are not as non-material as has been imagined, and (2) they consume non-trivial amounts of energy, which are underestimated in the official statistics. To consider this question it is necessary to understand the forms which energy demand takes in the service sector. There are rather few theoretical studies concerned with energy consumption in the services sector. Our analyses are based on a review, guided by the question of energy consumption, of the theoretical literature on services which is concerned with their definition and an analytical breakdown of how they are provided.

The first part of the paper is devoted to a discussion of what might be called the myth of the non-materiality of services. In the second part we attempt, on the basis of a theoretical breakdown of the provision of services, to identify all the sources of direct energy consumption by services. We show that the official energy statistics account for only a part of energy consumption. By taking a life-cycle perspective on services, we have broadened our view so as to identify energy consumption indirectly related to the provision of services. The third and final part of the paper is devoted to an attempt to estimate the magnitude of neglected energy consumption, or at least, within the limited scope of this paper, some of it.

The myth of the non-materiality of services

One can trace the origin of the term non-materiality (or intangibility) of services to Adam Smith and his analysis of the accumulation of capital. In his work The Wealth of Nations (1776), Smith distinguishes two types of economic activity: productive work, like that of the worker who adds value to the materials he handles and transforms, and unproductive work which adds no value. Among the unproductive activities Smith identifies the activities we today term services. 1 Although the adjective "non-material" is never directly used, the idea of non-materiality is implicit, as the following examples illustrate: "the [unproductive] labour does not fix or realize itself in any permanent subject, or vendible commodity, which endures after that labour is past, or for which an equal quantity of labour could afterwards be procured" (ibid., p. 430), "the work of all [the services] perishes in the very instant of its production" (ibid., p. 431).

In a discussion of the accumulation of capital, Jean-Baptiste Say (1803) questions the term unproductive. Indeed, although they produce no value, the services are to Say useful and sources of visible outcomes (e.g. the cure produced by a physician). He therefore introduces the term immaterial.

Most of his contemporaries used some version of this term, which was to become the leading feature used in describing service businesses. To 19th century economists the non-materiality of a service meant that the service is consumed and produced simultaneously (Say, 1803), that its outcome does not take a material form, that it cannot be accumulated [START_REF] De | Nouveaux principes d'économie politique ou De la richesse dans ses rapports avec la population[END_REF] and that it does not produce an exchangeable value (H. Storch) 2 ).

In the 20th century, when the notion of a services sector first appeared, the adjective non-material was settled on it as well. The idea of non-materiality of services was then fleshed out by an assumed lesser usage of plant and equipment (i.e. less capital intensity). Thus Colin Clark observed that most service businesses require far less in the way of capital goods than industry or agriculture (Clark, 1940, p. 207) A number of contemporary studies, however, question the notion that non-materiality fairly characterizes services (Fuchs, 1968;Delaunay, Gadrey, 1987;[START_REF] Illeris Sven | Services and regions in Europe[END_REF]Gadrey, 1992).

Transportation and communications services are among the most capital intensive. They require the use of a great deal of equipment. Furthermore, certain services are performed upon media which are tangible goods (book and newspaper publishing, sculpture, painting, 3 etc.), while other services repair, maintain or transform tangible goods (repair and maintenance services, not to mention restaurants and food services), or move them about (transportation, wholesale and retail trade, etc.) or make them available to users (rental services). In contemporary economies, the invasiveness of information and communications technologies also casts doubt on this notion of non-materiality. All service businesses today make use of information and communications technologies (ICTs), which in some cases give a physical form to the service (a recording of a course, for example).

Be that as it may, the notion of the non-materiality of services remains a chief feature by which service operations can be distinguished from other economic activities. In their attempts to propose a positive definition of services4 , Peter Hill and Jean Gadrey preserve non-materiality as an essential characteristic of services. Thus Peter Hill (1977) 3 These activities are classified as services since it is generally acknowledged that their informational content exceeds their physical content (Illiens, 1989). According to INSEE, printing and the mass production of recordings belong in the industrial sector. person or a good5 , and Jean Gadrey stresses that a service business does not result "in the production of a good that can circulate economically apart from its medium" (Gadrey, 1992, p. 19). Other arguments can be brought in to support the continued notion of non-materiality as a relevant analytic category to describe services. Such is the case, for instance, with the analysis of the post-industrial society dominated by service businesses and founded on knowledge and information (Bell, 1973;[START_REF] Stehr | Theories of the information age[END_REF]Aoyama et Castells, 2002;Foray, 2000).

Against the current background of diminishing natural resources and environmental deterioration, the notion of non-materiality of services has often been taken to mean that services have a low impact on the environment and in particular that they consume less energy [START_REF] Illeris Sven | The nature of services[END_REF][START_REF] Rifkin | Quand tout devient service" in Rifkin Jeremy. L'âge de l'accès : la révolution de la nouvelle économie[END_REF]OCDE, 2000). This idea is corroborated by a number of empirical observations. In France's energy accounting, services in 2006 represented only 14% of total consumption [START_REF] Mairet | Déterminants de la demande d'énergie dans le secteur tertiaire en France, une analyse technico-économique[END_REF] whereas in the same year they represented 75.1% of value added and 74.7% of total domestic employment (INSEE national accounts). Thus the energy intensity of the value added by service businesses is on average much lower than by other sectors. Likewise, in France's CO2 emissions accounting (data from CITEPA6 ), the services sector represented only 7% of emissions in 2008. The idea that services, being non-material, consume less energy and exert less pressure on the environment is a highly attractive one, as it means that the increasing service orientation of an economy, which is the unstinting trend in every developed country, will automatically foster sustainability. This idea has taken hold with governments and is defended by the OECD (OECD, 2000) and the European Union in its Lisbon Strategy.

We will devote the sections that follow to demonstrating that the non-materiality of services-the presumed basis of their low environmental impact-is a myth and to examining the consequences of that in terms of energy consumption.

Finding overlooked sources of energy consumption

The task before us at this point is to propose a theoretical breakdown of service provision, which reveals the main dimensions of its materiality and therefore its main sources of energy consumption.

We distinguish between direct energy consumption, which is that required for and during the provision of services, and indirect energy consumption, which is brought about in the rest of the economy by service businesses.

Breakdown of service provision and direct energy consumption

Our theoretical breakdown of service provision is based on a rereading, from an energy viewpoint, of works that focus on the definition of services. The earliest works dealt largely with the distinction between goods and services and with the shared characteristics apparent among all services [START_REF] Smith | The wealth of nations[END_REF]Say, 1803;[START_REF] De | Nouveaux principes d'économie politique ou De la richesse dans ses rapports avec la population[END_REF]Marx, 1971;Fisher, 1939;Clark, 1940;Fourastié, 1949). Although a number of contemporary authors have attempted to work out a truly positive definition of services (Hill, 1977 and[START_REF] Joseph | The internet economy and global warming, The Center for Energy and Climate Solutions SAY Jean-Baptiste[END_REF]Gadrey, 1992) 7 none of their definitions is entirely satisfactory, and the boundaries of the services sector remain fuzzy and dependent on the conventions chosen [START_REF] Illeris Sven | Services and regions in Europe[END_REF]. Still other studies have concentrated on describing service businesses within themselves (Gadrey, 1991;Gallouj, 1999;Eiglier, Langeard, 1987). And this is the perspective we take as well.

A service rendered by a provider for one or more customers (consumer or user, payer or beneficiary) will be a combination of various operations (Gadrey, 1991;Gallouj, 1999):

 logistics and material transformation (M), which consist of transforming, moving or maintaining tangible objects;

 logistics and information processing (I), which consist of producing, entering, circulating, archiving and processing coded information;

 the mental processing of knowledge (K); 7 The definitions of services formulated by these two authors are mentioned in part in the preceding section.

 relational services (R), which are direct services performed on the customer himself.

Performing these operations results in an outcome that can be described in terms of the final features of the service (Gallouj, Weinstein, 1997;Gallouj, 2002). In the case of lodging services, for example, the service features are primarily rest, comfort, cleanliness, access to recreation, or information, etc. Weinstein, 1997 ;Gallouj, 1999 ;Gallouj, 2002).

The values prized by providers and their customers will also play a part in the provision of services.

Values and competencies, when aligned with motivation, determine the behaviour of individuals [START_REF] Mcclelland David | How motives, skills, and values determine what people do[END_REF]. The customer is at the centre of the provision of services. 9 His or her part in the production of a service can take different forms-from self-service when using an automated cash dispenser to collaboration with the provider in the case of advisory services. This participation can even be solicited in advance of the production of service; the customer must at times travel to where the service is performed. The customer's level of involvement will vary. For certain services (a plane trip, for instance) only the customer's presence is necessary; for others (such as a training program) his attention is required (Eiglier, Langeard, 1987;[START_REF] Christopher | Marketing des services[END_REF]. One portion of the service often takes place in direct contact with the customer 10 ; another portion is invisible to him, this being the internal organization of the service company (also called the back-office), consisting, for example, of the marketing, finance, human resources or logistics departments (Eiglier, Langeard, 1987).

8 These features are not always easy to identify, especially in the case of non-standardized services requiring a high level of qualification, such as intellectual and professional services (Gallouj, 2002;Gallouj, Weinstein, 1997).

9 It is even the view of Eiglier and Langeard (1987) that without the customer there is only a "potential" for service. Thus, for example, if a hotel room is not occupied for one night, there are no services. One may object, however, that it all depends on the definition of services that is used, since a part of the production of the service has taken place-the preparation of the hotel room. We shall return to this point when considering a broader definition of services. Furthermore, the participation of the customer is not necessary with respect to prevention services (defense, police, security patrols, etc.)

10 However, ICTs include the remote delivery of services.

Most of the above-mentioned technologies consume energy in order to function. These energyconsuming technologies are a major part of the information and communications technologies used in information processing operations. They include office machinery (computers, fax, telephones, photocopiers, etc.) and network and telecommunications infrastructure (servers, hubs, data centres, telephone exchanges, etc.). Today in France, almost all service businesses are equipped with computers and connected to the Internet [START_REF] Sessi | Tableau de bord des TIC et du commerce électronique, Édition décembre 2008[END_REF]; and 20% of the energy consumption in the services sector is directly attributable to the use of ICTs 11 [START_REF] Mairet | Déterminants de la demande d'énergie dans le secteur tertiaire en France, une analyse technico-économique[END_REF]. In the area of materials processing operations, moreover, certain service activities require the use of other specialized equipment. Here we are talking about such things as equipment for material handling, cooling systems, cooking (restaurants), sanitary hot water12 (swimming pools) or other particular production processes (such as laundries or bakeries).

Services, however, are not limited to the M, I, K and R operations we have just mentioned and that we propose designating "service delivery". Other activities related to the provision of services must be brought into any discussion of energy consumption.

Indeed, service deliveries necessitate interactions between provider and customer, and thus usually travel by one to the other, before the delivery. Students and teachers travel to their campus, patients to their doctor, etc. 13 This travel is a source of pollution (Gadrey, 2010; Desmarchelier and Gallouj, 2010) and energy consumption.

Service delivery also requires various preparatory activities, such as preparing the place where the service is to occur (improvements, cleaning, heating, etc.), as well as the preparation of the provider (training, lodging, etc.). This preparation does occur only in advance of the delivery; it can be extended during the delivery (heating or illuminating the space, for example). For this reason, rather than the term "preparation" we prefer to use "conditioning" to denote this type of activity. A portion of this conditioning requires energy consumption, primarily for heating, sanitary hot water, lighting and air-conditioning the premises where the service occurs. This energy consumption is not specific to services, in that it also affects industry. What is specific is the weight it has in a company's total energy balance. Heating represents half the energy consumed in the services sector. One explanation for this trait is that, as opposed to industrial operations, service operations generally use less heavy equipment needing high energy inputs. Another explanation is the importance of personal meeting and meeting places in the provision of services. A service is produced jointly; customers and providers usually interact in a common space, which has to be conditioned for the services to be provided.

11 That is, about 4% of final energy consumption in the tertiary sector.

In sum, service provision is a combination of the following three elements: delivery, conditioning and travel-each of which represents a separate, direct consumption of energy. Depending on the type of service business considered, there will be some variance in the activity level, operating cycle, need for delivered services, conditioning or travel involved. Performing these various services prompts a need for "energy services", which is to say, for example, a task, a change of place or an increase in temperature. This need for "energy services" varies as a function of a number of exogenous factors, including the outdoor climate and sources of indoor or cost-fee heat 14 . The actual energy consumption necessary to meet this need for "energy services" is, for its part, a function of the tangible property used and its technical characteristics-such as energy-using machinery and the building in which it is located-as well as how this property is used-i.e., individual behaviour. 15 The general process by which energy demand is formed is illustrated in Erreur ! Pas de séquence spécifié.

Figure 2. General Process of the Formation of Energy Demand

Not all the sources of energy consumption and related consumption that we have just identified in this analysis are accounted for in the official statistics (Erreur ! Référence non valide pour un signet.).

In the CEREN statistics 16 , the energy consumption of the services sector is limited to those associated with the buildings used by the sector, that is, to the energy consumption of the equipment used on the premises 17 of service companies (CEREN scope 18 ). Thus, no accounting is given of energy consumed 14 Indoor or cost-free heat largely derives, respectively, from other occupants or machinery in the building and sunshine.

15 This approach to energy consumption is inspired by that proposed by Château and Lapillonne, cited by Nicolas [START_REF] Mairet | Déterminants de la demande d'énergie dans le secteur tertiaire en France, une analyse technico-économique[END_REF].

16 CEREN: Centre d'Etude et de Recherches Economiques sur l'Energie [Centre for study and research into energy economics]. This is the major organization in France supplying energy statistics on the tertiary sector. 17 By service business premises we mean the entire floor area of service companies, including any parking lots or other outside areas. The premises may be owned or leased. in the course of providing the services from the operation of off-site equipment or means of transportation (for travel services, but at times for delivered services). Yet it is true that services, especially as they are produced jointly, require considerable travel and sometimes occur completely or in part outside of the service company. We have identified three sources of materiality in services that constitute as many sources of direct energy consumption: service delivery, travel and conditioning. Yet still other energy consumption is necessary for services, even if the energy in question is not directly consumed during the provision of the service. That is the topic of the following section.

Type of operation

Level of activity

Energy consumption indirectly related to the provision of services

As we have just emphasized, the operation of equipment enlisted for delivery, conditioning and travel makes up a sizable source of energy consumption. We must not forget, however, that this equipment had to be made and that its manufacture is also a source of energy consumption-energy for the design of the project, the extraction and transportation of the necessary raw materials, the processing of raw materials and fabrication of the product. Marketing this equipment, maintaining and recycling it also give rise to energy expenditures. All of this energy consumption, although indirectly related to the provision of services, cannot be excluded from a discussion of energy consumption in the tertiary sector. By including this indirect energy consumption into our analysis we are adopting a product life-cycle approach. The value of such an approach is that it gives a truer picture of the energy impact 18 CEREN defines the boundaries of the services sector in terms rather similar to those proposed by INSEE. (and more broadly, the environmental impact) of service operations. But to do so means defining the boundaries of the system we are studying.

Accordingly, in the indirect energy consumption of a given service, which we shall call "the final service", one must include the grey energy 19 of equipment used in delivery, conditioning and travel.

Producing the final service also requires other types of goods, such as buildings, furnishings, infrastructure (transportation and telecommunication) and other intermediary consumption of goods (food products, for example, in a food service business). The grey energy of these goods is tied to the production of the final service, and we choose to include it in our approach.

Apart from equipment and tangible goods, producing a final service also at times requires the intermediary consumption of other services. The marginal increase in activity of these intermediary services and the associated marginal energy consumption are tied to the production of the final service.

The energy consumption of these intermediary services is itself defined as the sum of energy consumption in the operation of their energy-using equipment and the grey energy of their equipment, furnishings, buildings, infrastructure, etc. represents the system as seen at the scale of the final service. This energy consumption indirectly related to service operations is plainly not included in the official statistics on the tertiary sector. 19 The expression grey energy or embodied energy of a good means the total energy consumption necessary for the production, manufacture and recycling of a good, i.e. the phases that precede and follow the use of a good. Lastly, we are proposing an alternative methodology to account for energy consumption, one that derives from our theoretical construction of the sources of energy consumption in the tertiary sector.

Our hope is to contribute a more realistic assessment-which is to say, a reassessment-of the amount of energy necessary to provide a service. It is not our claim, however, that we are proposing a re-allocation of energy consumption among the various economic sectors. It might become necessary to consider that some portion of services is directed towards industrial production.

Within the scope of the French tertiary sector, the energy consumption overlooked by the official statistics is as follows:

-One part of energy consumption that goes for operating service equipment:

(1) Energy consumption for the operation of means of transportation (in service travel and delivery);

(2) Energy consumption for the operation of off-site equipment used for service delivery and conditioning.

Etc.

*Production in the broad sense. This includes: the design of the project, the extraction and transportation of the necessary raw materials, the processing of raw materials and fabrication of the product.

-Energy consumption indirectly related to the provision of services:

(3) The grey energy of equipment, furnishings, buildings, infrastructure and all intermediary consumables;

(4) The energy it took to produce imported intermediary services 20 .

The total of this energy consumption is not available in the form of invoices or shipping statements.

This consumption is classified with other energy consumption not related to services-in the energy consumption of other institutional sectors. The total therefore has to be estimated. Such work generally requires using surveys of a representative sample of the population. To the traditional biases that characterize surveys 21 , one might have to add occasional lack of information or ignorance on the part of the respondents 22 . On account of such difficulties and given the available data, we restrict ourselves in this paper to estimating energy consumption for the operation of means of transportation, i.e., type 1 consumption. By demonstrating that type 1 energy consumption is not trivial compared to the official tertiary sector energy consumption figures and that it represents a significant portion of energy consumption in the transportation sector, we are confirming empirically what we had previously conceived theoretically: that the tertiary sector consumes more energy than the official energy statistics would lead one to believe.

Nor is the total amount of type 1 energy consumption available on invoices or shipping statements. To estimate its size we have made use of the findings of the 1993-1994 French national transportation and travel survey (French acronym ENTD) 23 . Although this survey is nearly 20 years old, it does allow us, by comparing the findings made about energy consumption in the tertiary sector in 1993, to estimate the approximate extent of the consumption for travel overlooked by the official statistics. A representative sample of the French population was questioned as to the trips they had made. For a few representative days (one weekday and one weekend), the respondents furnished the reasons for, the distances involved in and the means of conveyance of all of trips they made. The respondents also supplied information about themselves, including their socio-professional status. Making a few assumptions, which we lay out in Section 4.1, we have estimated the travelling done by consumers and providers of services (section 4.2). 20 Within the French tertiary sector and to avoid double counting services, intermediary services are limited to imported intermediary services. 21 Especially the bias that misunderstanding or social acceptability can throw into responses. 22 This is particularly the case with households who do not know their energy consumption by type of use. 23 The transportation survey was repeated in 2007, but the data to which we have access are incomplete and do not permit us to estimate type 1 consumption.

Assumptions

In order to estimate from the INSEE transportation survey the energy consumption created by all the travel originating in the consumption or production of services, we formulated several assumptions relative to the reasons for trips made, the business sectors involved, the combination of means used and the energy efficiency of those means. a) Reasons for travel For every trip made, the survey results show the reason for it, taken from a predefined list. We have organized this list by distinguishing those reasons we deemed to be directly related to the consumption of a service and those we deemed to be job-related (including commuting from home to work). The survey provides no information on the business sector of the individuals surveyed. We therefore relied on their socio-professional status (SPS), which was part of the questionnaire, and we posited that within a single socio-professional status the distances travelled are spread evenly among those working in the different sectors-i.e., that the share of distance travelled by service providers is proportional to the share of workers in the tertiary sector. INSEE gives the data for the intersection of socio-professional status and business sector. The data are not available for the 1993-1994 year of the survey. The closest date for which they are available is 1999. 24The data are presented in Erreur ! Référence non valide pour un signet. given on the total distance travelled and the different conveyances used, but distance is not broken down by conveyance. We have therefore made estimates. We made the assumption that for each trip the first two means of travel mentioned are the chief, if not the only, means used. We then formulated a number of assumptions as to the breakdown of distance travelled between these two means (Table 3), based on a study conducted as part of the ETHEL project. 25 The results of this study show, for example, that on average an individual who makes a trip by car and by train covers 15% of the distance by car and 85% of the distance by train. Lastly, we made assumptions as to the per unit consumption of each means of transportation. For mass transit, we made assumptions about the energy consumption per kilometre travelled and per traveller.

With regard to two-wheeled vehicles and cars, insofar as in both cases the number of people in or on the vehicle is indicated in the ENTD survey26 , we preferred to consider the energy consumption by kilometre travelled and then divide it by the number of people in or on the vehicle. For truck transport, we assumed that the driver is alone in the vehicle.

We ignored energy consumption related to travel by foot, bicycle, boat and conveyances not in the survey. (This approximation seems reasonable in that according to the findings of the ENTD 1993 survey, these last two means of transportation represent less than 6% of the kilometres travelled by the French public.)

The ENTD survey provides useful data for estimating the energy consumption of automobiles. It provides various data about vehicles owned, in particular their average consumption, in and out of the city, by type of energy consumed (diesel or petrol). We make the assumption that the weighted average of these consumption numbers (weighted by the proportion of households in the French population) is representative of the average consumption per kilometre of all cars and taxis. The results obtained are presented in Erreur ! Référence non valide pour un signet. A litre of petrol equals about 9.85 kWh and a litre of diesel, 10.58 kWh. According to the ENTD 1993 survey, 72.3% of cars on the road in France run on petrol.

The breakdown of trips between city and non-city driving can also be estimated from some of the survey data. The survey results cover total trips, as well as, at times, the number of kilometres travelled in the city, on the highway and on other roads. We made the following assumption: trips made on highways and other roads equal the non-city trips. Trips for which the kilometres travelled on each type of road are reported in the ENTD survey allow us to calculate a pattern of trips among the different geographic areas. We made the assumption that this pattern applies to the breakdown of all trips. We found that 20% of the kilometres are travelled in the city and the rest outside the city.

Finally, according to our calculations, cars and taxis in 1993 consumed on average 0.81 kWh/vehiclekilometre.

To estimate the consumption of the other means of transportation, we relied on a study conducted by the Deloitte firm for ADEME (ADEME/Deloitte 2008). This study is recent, whereas the ENTD survey dates from 1993. We therefore made assumptions regarding the improvements in energy efficiency of transportation between these two years. Between 1990 and 2009, the total energy efficiency of transportation appears to have improved by about 12%. 27 We therefore made the assumption that for each means of transportation the per unit consumption when in use decreased by 12% between the time of the ENTD survey and the ADEME/Deloitte study. In addition, our transportation categories are not completely identical to those in the study. We made assumptions to establish some correspondence between them. The per unit consumption of school and company buses (codes 41 and 42) are thought to be similar to coaches; that of trolleys and other unlisted roadway mass transit (codes 55 and 59), similar to buses; that of trains would be the average of high-speed trains, regional express trains and Paris commuter trains. 28 The per unit consumption supplied by the ADEME/Deloitte study is expressed in grams of petroleum equivalent per passenger-kilometre and we have converted that to kilowatt-hours per passenger-kilometre. Using the international energy conversion tables, 1,000 GPE equals about 11.63 kWh. For mass transit, per unit consumption is 27 http://www.odyssee-indicators.org/publications/country_profiles_PDF/fra_nl.pdf 28 These assumptions could be improved upon, especially by studying the breakdown of trips among high-speed rail, regional express lines and Parisian commuter rail. But we believe that these assumptions are satisfactory for our current purpose, which is to estimate approximate amounts of energy consumption.

presented in The breakdown of trips between city and non-city driving can also be estimated from some of the survey data. The survey results cover total trips, as well as, at times, the number of kilometres travelled in the city, on the highway and on other roads. We made the following assumption: trips made on highways and other roads equal the non-city trips. Trips for which the kilometres travelled on each type of road are reported in the ENTD survey allow us to calculate a pattern of trips among the different geographic areas. We made the assumption that this pattern applies to the breakdown of all trips. We found that 20% of the kilometres are travelled in the city and the rest outside the city. Finally, according to our calculations, cars and taxis in 1993 consumed on average 0.81 kWh/vehicle-kilometre.

. Lastly, in the ADEME/Deloitte study, the per unit consumption of two-wheeled vehicles is defined for different geographic areas (urban, peri-urban, regional and interregional). As for car travel, the ENTD survey provides us with total trips on two-wheeled vehicles, as well as, at times, the kilometres travelled on two wheels in the city, on the highway and on other roads. We make the following assumptions: travel in the city corresponds to urban travel; travel on highways, to interregional travel; travel on other roads, half to peri-urban travel and half to regional travel. Trips for which the kilometres travelled on each type of road are reported in the ENTD survey allow us to calculate a pattern of trips among the different geographic areas. We made the assumption that this pattern applies to the breakdown of all trips (Erreur ! Référence non valide pour un signet.). Finally, according to our calculations, two-wheeled vehicles in 1993 consumed on average 0.41 kWh/vehicle-kilometre.

Results of our estimates

From the assumptions made, we estimated the energy consumption for all trips related to the consumption and production of services. The energy consumption is estimated using the following formulas:

-Energy consumption due to travel by service consumers:

t t s i j j i sij C p p d                                

52

-Energy consumption due to travel by service providers, for commuting and work-related trips: In 1993, about 126 TWh of final energy appear to have been consumed for travel associated with service operations. This amount represents about 25% of the consumption in the transportation sector for that year and 70% of the consumption in the tertiary sector. If one reassigns the type 1 energy consumption, the weight of the tertiary sector in the total energy balance increases from about 10.5% to over 18%. By further updating the results of the 1993 survey based on these data 31 , we obtain an estimate of the energy consumption for travel related to service businesses on the order of 140 TWh. It thus seems a reasonable inference that the energy consumption required today for travel to consume services and to provide services is on the order of 140 to 160 TWh. If one reassigns this energy consumption to the tertiary sector, the latter's weight in the total energy balance would then almost reach 20%.

t t p i j j i j pi C p p d                                ' ' '

Conclusion

In economic theory, the supposed non-materiality of services has suggested that a highly service-oriented society would consume less energy. But the non-materiality of services is a myth. The very interactivity that is understood to be one of the essential characteristics of a service shows itself as the major source of their materiality, since it relies upon physical communications and transportation systems. In this paper we have identified various sources of materiality in the service sector, and they are all sources of energy consumption. We have also shown that services consume energy through the different stages of their provision, whether by travel and the conditioning of service premises or by the actual delivery of services. We have also shown that their production requires numerous goods (equipment, buildings, infrastructure, etc.) whose grey energy needs to be taken into account when considering the energy impact of the service sector. In the energy statistics of the tertiary sector, only a portion of the energy consumption truly required by the provision of services is recognized.

Within the limited scope of this paper, we have only estimated one of the sources of energy consumption that have been overlooked in the official statistics: that pertaining to mobility. (That is, we estimated travel by service consumers to consume the service, and the commuting travel and the interactivity of services, which is one of their major characteristics, and secondly, because it is a major source of their materiality. We estimate that the reassignment of this energy consumption has the effect of multiplying the tertiary sector's consumption by a factor of about 1.7. Efforts need to be undertaken to make estimates of the other sources of energy consumption, for the energy required by the entire tertiary sector is far greater than what we have estimated here.

We have confirmed all of our assumptions theoretically and some of them empirically, as follows: the tertiary sector is in reality far from non-material, and the provision of services calls for significant amounts of energy consumption that the official statistics underestimate due to their accounting methodology. The increasing service orientation of an economy therefore does not constitute a solution to its energy, or more broadly, environmental issues.

  defines services as a change in the condition of a 2 Heinrich Storch, 1823. The Course of Political Economy, or an Exposition of the Principles which Determine the Prosperity of Nations. Cited in Delaunay and Gadrey, 1987.

Figure 1 .

 1 Figure 1. Energy intensity of value added, by sector (Mtoe/BEUR 2000 ) in 2006

  the service (esp. their floor area)

Figure 3 .

 3 Figure 3. The Scope of Energy Consumption in the tertiary sector as assumed in CEREN statistics

Figure 4 .

 4 Figure 4. The total direct and indirect sources of energy consumption in a final service

Figure 4 .

 4 Figure 4. The total direct and indirect sources of energy consumption in a final service

  25 ETHEL:Energie, Transport, Habitat, Environnement, Localisations [= Energy, Transportation, Habitat, Environment, Locations]. A project conducted in 2003 whose findings are available at http://ethel.ishlyon.cnrs.fr/index.htm. The assumptions about multiple means of transportation are based on analyses of surveys.

  52 where: t = means of transportation; s = trips occasioned by the consumption of services; p = work-related trips (including commuting); i = individuals surveyed; i' = individuals surveyed who work in the tertiary sector; j = day of the week; C t : estimate of the average consumption of the means of transportation, per km and per passenger; d sij and d pi'j : distance travelled per trip, per individual and per day; p i and p i' : occurrence of such an individual in the French population (how representative he or she is); p j : weight given to the day the questionnaire was administered so that the results can be representative of one week;The results obtained are presented in Erreur ! Référence non valide pour un signet..

  If one places these results into the current situation, in which the consumption in the transportation sector amounts to 584 TWh and that of the tertiary sector to 225 TWh 30 , one comes up with 145 TWh and 158 TWh respectively. Furthermore, INSEE supplies an estimate of the change in travel distances between 1993 and 2007 for a few travel purposes (Erreur ! Référence non valide pour un signet.).

  work-related travel by service providers). Travel is important for two reasons: first, because it captures 31 Also in need of updating are the per unit consumption of the means of transportation and the intersection between SPS and business sector. Here we have relied on the results of the ADEME/Deloitte study and the results of the INSEE 2007 census, respectively.

  Degree of decreasing relatedness between energy consumption and provision of the final serviceGrey energy of equipment, furniture & furnishings, buildings, infrastructure, etc.

		Direct relationship		Indirect relationship
	In advance of the final service		Production* and marketing of equipment, furnishings, buildings, infrastructure and other intermediary goods consumed.	Production* and marketing of equipment, furnishings, etc.
	t 0 Provision of final service	Operation of equipment that consumes energy (delivery, conditioning, transportation)	Energy consumption of intermediary services	Operation of equipment of the intermediary service
				Recycling
			Recycling	of equipment,
			of equipment,	furnishings,
	After the		furnishings, buildings, infrastructure or other	buildings, etc.
	final		intermediary consumables.
	service

Table 1 . Reason for travel and consumption of services Reason for travel related to the consumption of services Work-related reasons for travel

 1

	Place of study (school, high school, university)	Going to a fixed, customary workplace
	Day care, nursery school	Going to an unfixed workplace (construction site,
	Shopping mall or downtown stores	business meeting, business trip, etc.)
	Neighbourhood store and other shopping	Coming home from workplace
	Medical treatment or personal care (doctor, hairdresser,
	etc.)
	Government-related errands	Other work-related reasons
	Accompanying or picking up someone at a train station,
	airport, subway stop, etc.
	Cultural and athletic events or meetings (cinema, theatre,
	concert, sports match, etc.)
	Visiting monuments and historical places	Other reasons for travel
	Playing sports (gymnastics, soccer, etc.)	Going home
	Recreational locations (parks, fairs, bowling, etc.)	Visiting family
	Going on vacation	Visiting friends
	Cafés, restaurants, bars	Going to a second home or occasional dwelling
	Going to a training program, lecture, conference, etc.	Other personal reasons
	Accompanying or picking up someone at one of the
	aforementioned places
	Returning home from one of the aforementioned places
	b) Business sectors
	With regard to work-related travel, our estimate must only include that done by individuals who work
	in service firms or organizations.

Table 2 . Intersection of socio-professional category and business sector

 2 To estimate the energy consumption from distances travelled, it is necessary to know the means of transportation used and its average consumption rate. It is not unusual for a person to use more than one means of transportation for a single trip. For each trip reported in the ENTD survey, information is

		SPS	Tertiary sector		SPS	Tertiary sector
	10 Farmers	0.0%	47 Technicians	52.6%
	21 Craftsmen	38.4%	48 Foremen	39.4%
	22 Wholesalers, Retailers	97.9%	52 Government employees	99.3%
	23 Business owners	60.9%	53 Police and military	96.9%
	31 Members of the professions	98.7%	54 Business employees	81.1%
	33 Government white-collar	98.3%	55 Wholesale/retail employees	90.2%
	34	Teachers, secondary & higher	98.9%	56 Personal services	98.7%
	35 IT, arts professionals	83.6%	62 Skilled industrial workers	16.5%
	37 Business executives	82.9%	63 Skilled craftspersons	51.9%
	38 Engineers	52.3%	64 Drivers	85.6%
	42 School teachers	99.0%	65	Skilled maintenance, warehousing workers	68.5%
	43	Healthcare intermediary professions	97.2%	67 Unskilled industrial workers	36.0%
	44 Clergy, religious vocations	98.1%	68 Unskilled craftsmen	66.4%
	45	Government intermediary workers	99.0%	69 Farm workers	14.1%
	46	Business intermediary professions	77.9%
			Source: INSEE, 1999 census of the population
		c) Multiple means of transportation

Table 3 . Assumptions about multiple means of transportation Means of transportation Breakdown of distances travelled

 3

	On foot, by bicycle and all other means of transportation	100% of the distance attributed to the other means
	Airplane and all other means	100% of the distance attributed to the airplane
	Train and car	15% of the distance attributed to the car
	Train and coach	85% of the distance attributed to the train
	Train and other means	100% of the distance attributed to the train
	Coach and car	30% of the distance attributed to the car
	Coach and bus	50% of the distance attributed to each means
	Coach and other means	100% of the distance attributed to the coach
	Car and bus	35% of the distance attributed to the car
	Car and two-wheeled vehicles	100% of the distance attributed to the car
	Car and other means	35% of the distance attributed to the car
	Bus and other means	50% of the distance attributed to each means

Source: Data from the ETHEL project, arranged to match our means of transportation d) The energy efficiency of means of transportation

Table 4 . Average energy consumption per vehicle per 100 km

 4

		City driving Outside the city
	Petrol	7.6 L	8.5 L
	Diesel	6.8 L	7.4 L
	Source: Author's calculations based on the ENTD survey results

Table 5 . Energy consumption of various means transportation

 5

	Means of transportation	Energy consumption per passenger per kilometre (kWh/passenger-km)
	High-speed rail	0.09
	Trains	0.15
	Parisian rapid transit rail system	0.09
	Coach	0.13
	Bus	0.46
	Tram	0.08
	Subway	0.09
	Airplane	0.53
	Truck	4.10
	Source: Author's calculations based on data from the ADEME/Deloitte study (2008)

Table 6 . Breakdown of two-wheeled vehicle travel by geographic area

 6

	Urban Peri-urban Regional Interregional

Table 7 . Estimate of energy consumption for travel related to service operations

 7 Sources: Calculations by the author based on the results of the ENTD 1993 survey and the assumptions established in Section 4.1.

			Trips occasioned by the	Work-related trips of service
			consumption of services	providers	Corresponding energy
			(in km)	(in km)	consumption (TWh)
	On foot and by bicycle	5,893,092,030	958,519,983	0.0
	Two-wheeled vehicles	1,476,415,676	973,440,727	0.9
	Car and taxi	29	117,731,351,689	79,858,954,616	107.9
	Truck		3,371,509	353,113,534	1.5
	Coach		13,295,234,475	1,418,965,640	1.8
	Bus		5,181,805,725	1,592,388,322	3.1
	Subway		1,816,700,221	1,942,969,762	0.3
	Parisian rapid transit rail system	889,974,273	1,301,089,674	0.2
	Tram		204,965,724	114,212,944	0.0
	High-speed rail	2,525,628,236	740,213,412	0.3
	Other trains	4,380,144,378	5,464,916,676	1.5
	Airplane		12,349,394,854	2,752,202,840	8.0
	Other		1,485,687,260	246,192,283	0.0
	Total		167,233,766,049	97,717,180,413	125.7

Table 8 . Change in distance travelled, by purpose (%)

 8

					Home to other	Other
		Work	Study	Shopping	activities	trips	Total
	Rural and thinly settled areas	26	22	29	2	0	12
	Densely populated areas	10	Not sig.	Not sig.	-10	-1	-1
	Source: Insee/SOeS/Inrets, ENTD 1993, transportation and travel survey 2007-2008

GALLOUJ Faïz, WEINSTEIN Olivier, 1997. "

  "Macroeconomics of unbalanced growth: the anatomy of urban crisis", American Economic Review, Vol. LVII, n°3, June, pp. 415-426. BELL Daniel, 1973. The coming of post-industrial society, a venture in social forecasting, Basic Books, New-York ; trad. fr. 1976. Vers la société post-industrielle, Laffont, Paris, 446p. BOURG Dominique, BUCLET Nicolas, 2005. "L'économie de la fonctionnalité. Changer la consommation dans le sens du développement durable", Futuribles, n°313, November, pp. 27-37. BUCLET Nicolas, 2005. "Vendre l'usage d'un bien plutôt que le bien lui-même : une piste pour concilier meilleurs prise en compte de l'environnement et rentabilité des entreprises", XV conférence internationale de RESER, Granada, 22-24 September 2005. "Un modèle d'analyse de la dynamique de l'innovation dans les services : le cas des services de types architecturaux", Économies et Sociétés, EGS, n°7, pp. 1973-2010. DU TERTRE Christian, 2007. "Des services aux entreprises à l'économie de la fonctionnalité : les enjeux du développement durable" in Heurgon Édith, Landrieu Josée (coord.). L'économie des services pour un développement durable. Nouvelles richesses, nouvelles solidarités, Colloque de Cerisy, Prospective, Essais & Recherches, L'Harmattan, 390p. ETTIGHOFFER Denis, 1992. L'entreprise virtuelle. Ou les nouveaux modes de travail, Editions Odile Jacob, Paris, 346p. FORAY Dominique, 2000. L'économie de la connaissance, La Découverte, Paris, 124p. FOURASTIÉ Jean, 1949. Le grand espoir du XXème siècle. Progrès technique, progrès économique, progrès social, Presses Universitaires de France, Paris, 224p.; 2 nd edition, 1963, Gallimard, 372p. FOURCROY Charlotte, 2010. Services et énergie. Formation de la demande d'énergie d'une activité de services, Mémoire de Master 2 Recherche ESII, University of Lille 1. FUCHS Victor R., 1968. The service economy, National Bureau of Economic Research, New-York, 280p. GADREY Jean, 1991. "Le service n'est pas un produit. Quelques implications pour l'analyse économique et pour la gestion", Politiques et management public, Vol. 9, n°1, March, pp. 1-24. Innovation in the service economy. The new wealth of nations, Edward Elgar, Innovation in Services", Research Policy, Vol. 26, n°4-5, pp. 537-556. After industrial society. The emerging of self-service economy, "Tangibles, intangibles and services: a new taxonomy for the classification of output", Canadian Journal ofEconomics, Vol. 32, n°2, April,

	BIBLIOGRAPHY
	ADEME/Deloitte, 2008. Efficacité énergétique, emissions de CO2 et autres émissions gazeuses
	spécifiques des modes de transport, Rapport final.
	This conclusion raises the question of the reciprocal relationship between service sector innovation and tighter energy constraints. BAUMOL William, 1967. Cheltenham, 226p.
	MacMillan, Londres, 181p.
	HILL T.P, 1977. "On goods and services", Review of Income and Wealth, Vol. 23, n°4, December,
	pp. 315-338.
	HILL T.P, 1999.

CASTELLS Manuel, AOYAMA Yuko, 2002. "Une évaluation empirique de la société informationnelle : structures de l'emploi dans les pays du

G7, 1920[START_REF] Rifkin | Quand tout devient service" in Rifkin Jeremy. L'âge de l'accès : la révolution de la nouvelle économie[END_REF]". Revue Internationale du Travail, Vol. 141, n°1-2, pp. 133-173. CLARK Colin, 1940

. The conditions of progress and security, MacMillan and co., Londres; trad. fr. 1960. Les conditions du progrès économique, Presses Universitaires de France, Paris, 500p. DELAUNAY Jean-Claude, GADREY Jean, 1987. Les enjeux de la société de services, Les Presses de Sciences Po, Paris, 333p. DESMARCHELIER Benoit, GALLOUJ Faïz, 2010. "Croissance endogène et politique environnementales : les processus de croissance et de tertiarisation des économies développées sont-ils réversibles ? Une perspective évolutionniste.", RESER conference paper, Gothenburg, Sweden. DJELLAL Faridah, GALLOUJ Faïz, 2005. EIGLIER Pierre, LANGEARD Eric, 1987. Servuction. Le marketing des services, Ediscience international, Paris, 205p. GADREY Jean, 1992. Socio-économie des services, Éditions La Découverte, Paris ; 3rd edition, 2003, 124p. GADREY Jean, 1994. "Les relations de service et l'analyse du travail des agents". Sociologie du travail, n°3, pp. 381-389. GADREY Jean, 2010. "The environmental crisis and the economics of services : the need for revolution", in DJELLAL Faridah, GALLOUJ Faïz, The handbook of innovation and services, Edward Elgar, Cheltenham. GALLOUJ Faïz, 1999. "Les trajectoire de l'innovation dans les services : vers un enrichissement des taxonomies évolutionnistes", Économies et Sociétés, Série EGS, n°1, 5, pp. 143-169. GALLOUJ Faïz, 2002. GERSHUNY Jonathan I., 1978.

IFEN, 2004. "La tertiarisation de l'économie et la réduction des émissions de CO2", Les données de l'environnement, lettre thématique mensuelle de l

'IFEN, n°95, September, 4p.

He specifically mentions the services of the State, artists, etc.

The positive definition is distinct from a residual definition, as rounding out all the other economic activities.

"A service may be defined as a change in the condition of a person, or a good belonging to some economic unit, which is brought about as the result of the activity of some other economic unit, with the prior agreement of the former person or economic unit"(Hill, 1977, p. 318). In another article(Hill, 1999), however, Hill states that non-materiality is not an exclusive feature of services and that there is also such a thing as a non-material good.

Data from CITEPA for 2008 relating to CO2 emissions, excluding LULUCF (Land Use, Land-Use Change and Forestry).

This is hot water for sanitary uses: rest rooms, food preparation, etc. It is often shortened to SHW.

The different choices as to how service is delivered and therefore of travel, as well as the thinking behind them, are discussed in Section 3.

Despite the gap in time, we believe that these data are useful, inasmuch as we are trying to estimate the approximate amount of energy consumption.

With respect to the few trips for which the number of people is not indicated (less than 1% of trips by motorbike and by car), we made the assumption that the person was alone on/in the vehicle. Since the number of trips without data is very low, this assumption will have very slight effect on the final result.

Distances travelled by car, taxi and two-wheeled vehicles appearing in the table equal the total distances travelled by all French people. To estimate the corresponding energy consumption, we first divided these distances by the number of passengers travelling by that means.

These data are from 2008 and are provided bySOeS and CEREN, respectively.

WILLIAMS Eric, TAGAMI Takashi, 2003. "Energy use in sales and distribution via e-commerce and conventional retail. A case study of the Japanese book sector", Journal of Industrial Ecology,vol.6,n°2,


Olga Klopp

Matrix completion by singular value thresholding: sharp bounds

Keywords: matrix completion, low rank matrix estimation, minimax optimality AMS 2000 subject classification: 62J99, 62H12, 60B20, 15A83

We consider the matrix completion problem where the aim is to estimate a large data matrix for which only a relatively small random subset of its entries is observed. Quite popular approaches to matrix completion problem are iterative thresholding methods. In spite of their empirical success, the theoretical guarantees of such iterative thresholding methods are poorly understood. The goal of this paper is to provide strong theoretical guarantees, similar to those obtained for nuclear-norm penalization methods and one step thresholding methods, for an iterative thresholding algorithm which is a modification of the softImpute algorithm. An important consequence of our result is the exact minimax optimal rates of convergence for matrix completion problem which were known until know only up to a logarithmic factor.

Introduction

Suppose that we observe a small subset of entries of a large data matrix. The problem of inferring the many missing entries from this small set of observations is known as the matrix completion problem. This problem has attracted considerable attention in the past five years. The first works [START_REF] Candès | Exact matrix completion via convex optimization[END_REF][START_REF] Candès | The power of convex relaxation: near-optimal matrix completion[END_REF][START_REF] Candès | Matrix completion with noise[END_REF][START_REF] Gross | Recovering low-rank matrices from few coefficients in any basis[END_REF][START_REF] Recht | A simpler approach to matrix completion[END_REF] introduce nuclear-norm minimization method. A different approach, called OP-TISPACE has been proposed in [START_REF] Keshavan | Matrix completion from a few entries[END_REF][START_REF] Keshavan | Matrix completion from noisy entries[END_REF]. More recently, a method based on max-norm minimization was studied in [START_REF] Cai | Matrix completion via max-norm constrained optimization[END_REF][START_REF] Foygel | Concentration-based guarantees for low-rank matrix reconstruction[END_REF]. Other methods include, for example, GROUSE (Grassmannian Rank-One Update Subspace Estimation) [START_REF] Balzano | Absolute and monotonic norms[END_REF] and orthogonal rank-one matrix pursuit [START_REF] Wang | Orthogonal rankone matrix pursuit for low rank matrix completion[END_REF].

A quite popular direction in the matrix completion literature are the thresholding methods which can be divided in two groups: one-step thresholding methods and iterative thresholding methods. Strong theoretical guarantees were obtained for one-step thresholding procedures. For example, Koltchinskii et al in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] introduce a soft-thresholding method and show that it is minimax optimal up to a logarithmic factor. In [START_REF] Klopp | Rank penalized estimators for high-dimensional matrices[END_REF] Klopp consider a hard thresholding proceedure. Chatterjee [START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF] propose an universal singular value thresholding that can be applied to a large number of matrix estimation problems, including matrix completion. Despite strong theoretical guarantees these one-step thresholding methods has two important drawbacks: they show poor behavior in practice and only work under the uniform sampling distribution which is not realistic in many practical situations.

Much better practical performances have been shown by iterative thresholding methods. For example, in [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF], Cai et al propose a first-order singular value thresholding algorithm SVT which approximately solves the nuclear norm minimization problem. In [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF], Mazmuder et al introduce softImpute algorithm. softImpute produces a sequence of solutions that converges to a solution of the nuclear norm regularized least-squares problem when the number of iterations goes to infinity. These iterative thresholding algorithms are simple to implement, scale to relatively large matrices and in practice achieve competitive errors compared to the state-of-the-art algorithms. More recently Dhanjal et al [START_REF] Dhanjal | Online matrix completion through nuclear norm regularisation[END_REF] propose an improvement for the softImpute algorithm using randomized SVDs along with a novel updating method. This improvement allows to bypass the bottleneck in the algorithm which consists in the use of the singular value decomposition of a large matrix at each iteration.

The majority of existing algorithms for matrix completion are batch methods, that is, they operate on the full data matrix. However in some applications such as recommendation systems or localization in sensor networks we observe a sequence of data matrix M 1 , . . . , M T reviled sequentially where from M t to M t+1 we add new observations. In such situations the predictive rule should be refined incrementally. One advantage of iterative thresholding algorithms is that they can be adapted to such sequential learning, see for example [START_REF] Dhanjal | Online matrix completion through nuclear norm regularisation[END_REF].

In spite of their empirical success, the theoretical guarantees of such iterative thresholding methods are poorly understood. The goal of this paper is to provide strong theoretical guarantees, similar to those obtained for nuclearnorm penalization methods (see, for example [START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF]) and one step thresholding methods (see [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Klopp | Rank penalized estimators for high-dimensional matrices[END_REF][START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF]) for a modification of the softImpute algorithm.

Contributions and Related Work

The contributions of the present paper to the theoretical study of the modified softImpute algorithm are multifaceted. In Section 3.2 we prove an upper bound on the estimation error of the output M of our algorithm. Let M 0 ∈ R m1×m2 be the unknown matrix of interest. Suppose, for simplicity, that each entry is observed with the same probability p, then we prove the following upper bound on the estimation error of M

M -M 0 2 2 m 1 m 2 rank(M 0 ) p min(m 1 , m 2 ) . (1)
Here the symbol means that the inequality holds up to a multiplicative numerical constant. To the best of our knowledge, the upper bound on the estimation error given by ( 1) is strictly better than all upper bounds available in matrix completion literature.

For instance, for the same setting, Chatterjee in [START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF] obtains the following larger bound

M -M 0 2 2 m 1 m 2 rank(M 0 ) p min(m 1 , m 2 )
.

On the other hand, [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF], among some other papers, consider a slightly different setting where the matrix completion problem is viewed as a particular case of the trace regression model. In this setting the number of observations n is fixed. The drawback here is that in this model each entry can be observed multiple times which is not the case in a large number of practical situations. We consider a different setting where each entry can be observed at most once (see Section 2.1). However, it is easy to see that these two settings are closely related if we put n = pm 1 m 2 . Comparing to (1), the bounds obtained in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF] have an additional log(d 1 + d 2 ) factor. Koltchinskii et al in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] obtained lower bounds for the estimation error without this additional log(d 1 + d 2 ) factor. So our result answer the important theoretical question what is the exact minimax rate of convergence for matrix completion problem. As the lower bound in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] is obtained for a different setting, in Section 4 we adapt their proof to our setting, showing that the minimax rate of convergence for matrix completion problem is given by [START_REF] Balzano | Absolute and monotonic norms[END_REF] and that the estimator produced by our algorithm is minimax optimal. Note that our techniques can be adapted to the setting considered in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF] and lead to an upper bound without the additional log(d 1 + d 2 ) factor in this setting also.

Another important point is that a large part of matrix completion literature consider uniform sampling at random setting where each entry is observed with the same probability p. In many applications, such as recommendation systems, this assumption is not realistic. The theoretical analysis in the present paper is carried out for quite general sampling distributions and show that our iterative thresholding algorithm has good performances in such situations. Finally our results give theoretical insights for the chose of the parameters in the modified softImpute algorithm.

Organisation of the paper

The remainder of this paper is organized as follows. In Section 2.1 we introduce our model and the assumptions on the sampling scheme. For the reader's convenience, we collect notation which we use throughout the paper in Section 2.2.

In Section 3.1 we present a modification of the softImpute algorithm for matrix completion. The upper bounds on the estimation error are derived in Section 3.2. Finally the lower bounds are obtained in Section 4 and the Appendix contains the proofs.

Preliminaries

Model and sampling scheme

Suppose that we observe a relatively small number of entries of a data matrix

X = M 0 + E. (2)
Here M 0 = (m ij ) ∈ R m1×m2 is the unknown matrix of interest and E = (ξ ij ) ∈ R m1×m2 is the matrix containing the noise. We assume that the noise variables ξ ij are independent, zero mean and bounded:

Assumption 1. E(ξ ij ) = 0, E(ξ 2 ij ) = σ 2 and there exists a positive constant b > 0 such that max i,j |ξ ij | ≤ b.
We suppose that each entry of X is observed independently of the other entries. For the entry (i, j)

∈ [m 1 ] × [m 2 ]
, we denote the probability to be observed by π ij . Let η ij be the independent Bernoulli variables with parameters π ij and y ij = η ij (m ij + ξ ij ). Then, Y = (y ij ) is the matrix containing our observations. We denote by Ω the random set of observed indices.

In the simplest situation each coefficient is observed with the same probability, i.e. for every (i, j)

∈ [m 1 ]×[m 2 ], π ij = p.
Unfortunately, such an assumption on the sampling distribution is not realistic in many practical applications. In the present paper, we consider general sampling model. We suppose that each coefficient is observed with a positive probability: Assumption 2. There exists p > 0 such that for any

(i, j) ∈ {1, . . . , m 1 } × {1, . . . , m 2 } π ij ≥ p. For any A = (A ij ) ∈ R m1×m2 we define the weighted by π ij Frobenius norm of A A 2 L2(Π) = (i,j) π ij A 2 ij .
Assumption 2 implies that

A 2 L2(Π) ≥ p -1 A 2 2 . (3)
We denote the column and row marginals by

π •j = m1 Σ i=1 π ij and π i• = m2 Σ j=1 π ij .
Suppose that we know an upper bound L on it's maximum:

max i,j (π •j , π i• ) ≤ L. (4)
Note that we can easily get an estimation on this upper bound using the empirical frequencies

π•j = m1 i=1 η ij (i,j) η ij and πi• = m2 j=1 η ij (i,j) η ij .

Notation

We provide a brief summary of the notation used throughout this paper. Let A, B be matrices in R m1×m2 .

• For a matrix A, A ij is its (i, j)th entry.

• We denote by S λ (W ) ≡ U D λ V ′ the soft-thresholding operator where • For two matrices A, B ∈ R m1×m2 we define the scalar product A, B = tr(A T B).

D λ = diag [(d 1 -λ) + , . . . , (d r -λ) + ], U DV ′ is the SVD of W , D = diag [d 1 , . . .
• We denote by A 2 the usual l 2 -norm. Additionally, we use the following matrix norms: A * is the nuclear norm (the sum of singular values), A is the operator norm (the largest singular value), A ∞ is the largest absolute value of the entries:

A ∞ = max i,j | A ij | . • π ij is the probability to observe the (i, j)-th element. For j = 1 . . . m 2 , π •j = m1 Σ i=1 π ij and for i = 1 . . . m 1 , π i• = m2 Σ j=1 π ij . We have that max i,j (π •j , π i• ) ≤ L. • Let M = max(m 1 , m 2 ), m = min(m 1 , m 2 ) and d = m 1 + m 2 .
• Let I ⊂ {1, . . . m 1 }×{1, . . . m 2 } be a subset of indices. Given a matrix A = (A ij ), we define its restriction on I, A I , in the following way:

(A I ) ij = A ij if (ij) ∈ I and (A I ) ij = 0 if not. • We denote A 2 L2(Π) = (i,j) π ij A 2 ij and Assumption 2 implies A 2 L2(Π) ≥ p -1 A 2 2 .
• Let {ǫ ij } be an i.i.d. Rademacher sequence and X ij = e i (m 1 )e * j (m 2 ) where e k (l) are the canonical basis vectors in R l . We define

Σ R = (i,j) η ij ǫ ij X ij and Σ = (i,j) η ij ξ ij X ij . ( 5
)
3 The Singular Value Thresholding Algorithm

In this section we introduce an iterative singular value thresholding algorithm and discuss its theoretical properties. We show that it enjoys strong theoretical guarantees and, unlike one-step thresholding procedures, is well adapted for general non-uniform sampling distributions.

Algorithm

Our algorithm is based on the softImpute algorithm proposed by Mazumder et al in [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF]. SoftImpute algorithm is inspired by SVD-Impute of Troyanskaya et al [START_REF] Troyanskaya | Missing value estimation methods for dna microarrays[END_REF]. It alternates between imputing the missing values from a current SVD, and updating the SVD using the data matrix.

Algorithm 1

Require : Matrix Y , regularization parameter λ and a, an upper bound on the sup-norm of M 0 .

1. M old = 0 2. (a) Repeat (i) Compute M new ← S λ Y + (M old )Ω . (ii) If M new -M old Ω < λ/3 and M new -M old ∞ < a exit. (iii) Put M old = M old ij M old ij =            M new ij if |M new ij | ≤ a a if M new ij > a -a if M new ij < -a. ( 6
) (b) Assign M ← M new . 3. Output M .
This algorithm repeatedly replaces the missing entries with the current guess, update the guess by solving

M new ∈ minimize M f λ (M ) = 1 2 Y + (M old )Ω -M 2 2 + λ M * (7)
and truncating M new . Let us denote by (M k ) k≥0 the sequence of solutions produced by Algorithm 1. We have the following result :

Lemma 1.
For the successive differences of the sequence (M k ) k≥0 we have that

M k+1 -M k 2 → 0 as k → 0 (8)
which implies

M k+1 -M k Ω → 0 and M k+1 -M k ∞ → 0 as k → 0. ( 9
)

Upper bound on the estimation error

In this section we derive an upper bound on the estimation error of M produced by Algorithm 1. This bound is non-asymptotic and implies, in particular, that the proposed estimator is minimax optimal. We start by a general result which is proven in Appendix A.

Theorem 2. Let Assumptions 1 and 2 be satisfied and M 0 ∞ ≤ a. Assume that λ ≥ 3 Σ . Then, with probability at least 1 -8/d,

M -M 0 2 L2(Π) ≤ C p -1 rank(M 0 ) λ 2 + a 2 (E ( Σ R )) 2 + a 2 + log(d) .
where

d = m 1 + m 2 .
Using Assumption 2, Theorem 2 implies the following bound on the estimation error measured in normalized Frobenius norm Corollary 3. Under assumptions of Theorem 2 and with probability at least

1 -8/d, M -M 0 2 2 m 1 m 2 ≤ C p 2 m 1 m 2 rank(M 0 ) λ 2 + a 2 (E ( Σ R )) 2 + a 2 + log(d) .
In order to get a bound in a closed form we need to obtain a suitable upper bounds on E ( Σ R ) and, with probability close to 1, on Σ . Lemma 4. Suppose that (ξ ij ) are independent and satisfy Assumption 1. Then, there exists absolute constants c * , C * > 0 such that, for all t > 0 with probability at least 1me -t 2 we have

Σ ≤ 3σ √ 2L + c * b t ( 10
)
where L ≤ 1 is defined in (4). Moreover, we have

E Σ R ≤ C * √ L + log m . ( 11
)
This Lemma is proven in Appendix F. Taking t = 2 log(d) in Lemma 4, we get that with probability at least 1

-1/d, Σ ≤ 3σ √ 2L + c * b 2 log(d),
then, we can choose

λ = 3 3σ √ 2L + c * b 2 log(d) . (12)
With this choice of λ we obtain the following Theorem.

Theorem 5. Let Assumptions 1 and 2 be satisfied and M 0 ∞ ≤ a. Then, with probability at least 1 -8/d,

M -M 0 2 L2(Π) ≤ C p -1 rank(M 0 ) (a ∨ σ) 2 L + a 2 log(m) + b 2 log(d) . and M -M 0 2 2 m 1 m 2 ≤ C rank(M 0 ) p 2 m 1 m 2 (a ∨ σ) 2 L + a 2 log(m) + b 2 log(d) .
Remark 1. Note that π ij ≥ p yields L ≥ M p. Then, the upper bound on the estimation error in the Theorem 5 is at least a constant times rank(M 0 ) pm .

So, in order to get a small estimation error, p should be larger then rank(M 0 ) m .

We denote by n = ij π ij the expected number of observations. Condition p ≥ rank(M 0 ) m implies the following condition on

n n ≥ C rank(M 0 ) M. (13)
When the rank of the matrix M 0 is small, this necessary number of observations is close to the number of degree of freedom of the matrix M 0 , which is

(m 1 + m 2 )rank(M 0 ) -(rank(M 0 )) 2 .
Let us restrict our attention to the non-degenerated case M 0 = 0 (we can easily include this case replacing rank(M 0 ) by rank(M 0 )∨1). Assuming that the expected number of observations n is not too small, we can get simpler bound on the estimation error. Suppose that n > c * m log(d). Then, using Lm ≥ n ≥ c * m log d we get L ≥ c * log d and we can chose λ in the following way

λ = 18b √ 2L. ( 14
)
With this choice of λ we get the following bound on the estimation error Corollary 6. Let Assumptions 1 and 2 be satisfied and M 0 ∞ ≤ a. Assume that n ≥ c * m log(d) and M 0 = 0. Then, with probability at least 1 -8/d,

M -M 0 2 2 m 1 m 2 ≤ C rank(M 0 ) (a ∨ b) 2 L p 2 m 1 m 2 .
In order to compare this result with previous results on noisy matrix completion we consider a more restrictive assumption on the sampling distribution. That is, we assume that this distribution is close to the uniform one: Assumption 3. There exists positives constants µ 1 and µ 2 independent on m 1 and m 2 and a 0 < p < 1 such that for every (i, j) ∈ {1, . . . , m 1 } × {1, . . . , m 2 } we have

µ 2 p ≤ π ij ≤ µ 1 p.

Under this assumption Theorem 2 yields

Corollary 7. Let Assumptions 1 and 3 be satisfied and M 0 ∞ ≤ a. Assume that n ≥ m log(d) and λ given by [START_REF] Klopp | Rank penalized estimators for high-dimensional matrices[END_REF]. Then, with probability at least

1 -8/d, M -M 0 2 2 m 1 m 2 ≤ C rank(M 0 ) (a ∨ b) 2 pm .
Remark 2. Let us compare the bound given by Corollary 7 with bounds available in the literature. Our model was previously considered by Chatterjee in [START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF] in the case of uniform sampling distribution, that is π ij = p for any (i, j) ∈ {1, . . . , m 1 } × {1, . . . , m 2 }. In [START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF], Chatterjee introduces a simple estimation procedure, called Universal Singular Value Thresholding which is applied to a number of questions in low rank matrix estimation, blockmodels, distance matrix completion, latent space models and etc. For matrix completion problem and under the additional assumption p ≥ n -1+ǫ for some ǫ > 0, the bound obtained in [START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF] is the following one

M -M 0 2 2 m 1 m 2 ≤ C rank(M 0 ) (a ∨ b) 2 pm .
The rate of convergence given by Corollary 7 is faster and, as we will see in Section4, is minimax optimal. Note that the additional assumption p ≥ n -1+ǫ yields the following condition on the expected number of observations

n > m ǫ M. (15)
For low rank matrices, this necessary number of observations is larger than the number of observations required by our method and given by [START_REF] Keshavan | Matrix completion from noisy entries[END_REF].

In [START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF] a closely related set up for matrix completion problem using the trace regression model was considered. The main difference between these two settings is that in the case of the trace regression the number of observations is not random and each entry may be observed multiple times. In our setting the number of observations is random and each entry is observed at most once. Comparing with Corollary 7 and using n = pm 1 m 2 we see that bounds obtained in [START_REF] Negahban | Restricted strong convexity and weighted matrix completion: Optimal bounds with noise[END_REF][START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF][START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF] contain an additional logarithmic factor log(m 1 + m 2 ).

Minimax Lower bounds

In this section, we prove the minimax lower bound showing that the rates attained by our estimator are optimal. The minimax lower bound in a closely related problem was obtained by Koltchinskii et al in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF]. We adapt their proof to our set up.

We will denote by inf M the infimum over all the estimators. For any M 0 ∈ R m1×m2 , let P M0 denote the probability distribution of the observations (η 11 X 11 , . . . , η m1m2 X m1m2 ) satisfying [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF].

For any integer 0 ≤ r ≤ min(m 1 , m 2 ) and any a > 0, we consider the class of matrices

A(r, a) = M ∈ R m1×m2 : rank(M ) ≤ r, M ∞ ≤ a, . (16)
We will prove the lower bound in the case of the uniform sampling distribution, that is, we suppose that each entry is observed with the same probability p. As it was noted in Remark 1, in order to get a small estimation error we need to observe a sufficiently large number of entries, or, equivalently, the probability p should be larger then r/m. We prove a lower bound on the estimation risk when this condition is satisfied.

Theorem 8. Suppose that m 1 , m 2 ≥ 2 and p ≥ r m . Fix a > 0 and integer 1 ≤ r ≤ min(m 1 , m 2 ). Suppose that the variables ξ i are i.i.d. Gaussian N (0, σ 2 ), σ 2 > 0, for i = 1, . . . , n. Then, there exist absolute constants β ∈ (0, 1) and c > 0, such that

inf M sup M0∈ A(r,a) P M0 M -M 0 2 2 m 1 m 2 > c r (a ∧ σ) 2 pm ≥ β.
A Proof of Theorem 2

1. By Lemma 1 in [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF], M minimizes

f λ (M ) = 1 2 Y + (M old )Ω -M 2 2 + λ M * .
Then, using the sub-gradient stationary conditions we have

-Y + (M old )Ω -M , M -M 0 + λ V , M -M 0 ≤ 0 where V ∈ ∂ M * . A simple calculation yields M 0 -M Ω 2 2 ≤ (Y -M 0 ) Ω , M -M 0 I + M old -M Ω , M -M 0 II + λ V , M 0 -M III . (17)
2. We estimate each term in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] separately. For the first term, we have that (Y -M 0 ) Ω = Σ where Σ = (i,j) η ij ξ ij X ij . Then, by the duality between the nuclear and the operator norms, we obtain

(Y -M 0 ) Ω , M -M 0 ≤ Σ M -M 0 * . (18)
For the second term, using again the duality between the nuclear and the operator norms and the stopping criteria for the Algorithm 1, we obtain

M old -M Ω , M -M 0 ≤ M old -M Ω M -M 0 * ≤ λ/3 M -M 0 * . (19)
3. In order to estimate the third term, we use that by monotonicity of subdifferentails of convex functions we have that V -V, M -M 0 ≥ 0, for any V ∈ ∂ M 0 * . This implies

V , M 0 -M ≤ V, M 0 -M . (20)
Let P S be the projector on the linear vector subspace S and let S ⊥ be the orthogonal complement of S. Let u j (A) and v j (A) denote respectively the left and right orthonormal singular vectors of a matrix A. S 1 (A) is the linear span of {u j (A)}, S 2 (A) is the linear span of {v j (A)}. We set

P ⊥ A (B) = P S ⊥ 1 (A) BP S ⊥ 2 (A) and P A (B) = B -P ⊥ A (B). ( 21
) Since P A (B) = P S ⊥ 1 (A) BP S2(A) + P S1(A) B and rank(P Si(A) B) ≤ rank(A) we have that rank(P A (B)) ≤ 2 rank(A). (22)
Note that the subdifferential of the convex function A → A * is the following set of matrices (cf. [START_REF] Watson | Characterization of the subdifferential of some matrix norms[END_REF])

∂ A * =    rank(A) j=1 u j (A)v T j (A) + P ⊥ A (W ) : W ≤ 1    . (23)
Inequality ( 19) and ( 23) imply

III ≤ λ R j=1 u j (M 0 )v T j (M 0 ), M 0 -M + P ⊥ M0 (W ), M 0 -M . (24)
Using the fact that

R j=1 u j (M 0 )v T j (M 0 ) = 1 and R j=1 u j (M 0 )v T j (M 0 ), M 0 -M = R j=1 u j (M 0 )v T j (M 0 ), P M0 M 0 -M we obtain III ≤ λ P M0 M 0 -M * + P ⊥ M0 (W ), M 0 -M . (25)
Now, by the duality between the nuclear and the operator norms, there exists W with W ≤ 1 and such that

P ⊥ M0 (W ), M 0 -M = -W, P ⊥ M0 M = -P ⊥ M0 M * . (26)
For this particular choice of W , ( 25) and ( 26) imply

III ≤ λ P M0 M 0 -M * -P ⊥ M0 M * . (27)
Putting ( 18), [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF], and (27) into (17) and using λ ≥ 3 Σ we obtain

M 0 -M Ω 2 2 ≤ 2λ 3 M -M 0 * + λ P M0 M 0 -M * -P ⊥ M0 M * . (28)
4. The triangle inequality and ( 22) lead to

M 0 -M Ω 2 2 ≤ 5λ 3 P M0 M 0 -M * ≤ 5λ 2rank(M 0 ) 3 M 0 -M 2 (29)
and

λ 3 P ⊥ M0 M * ≤ 5λ 3 P M0 M 0 -M * . ( 30
)
Inequality (30) implies

P ⊥ M0 M * ≤ 5 P M0 M 0 -M * and M -M 0 * ≤ 6 P M0 ( M -M 0 ) * ≤ 72 rank(M 0 ) M -M 0 2 . ( 31
)
5. For a 0 < r ≤ m we consider the following constrain set

C(r) = A ∈ R m1×m2 : A ∞ = 1, A 2 L2(Π) ≥ log(d) 0.0006 log (6/5) p , A * ≤ √ r A 2 .
(32) Note that the condition A * ≤ √ r A 2 is satisfied if rank(A) ≤ r. We have the following result for matrices in C(r). Its proof is given in Appendix C. Lemma 9. For all A ∈ C(r)

A Ω 2 2 ≥ A 2 L2(Π) 2 -44 p -1 r (E ( Σ R )) 2 + 18
with probability at least 1 -8/d.

Note that condition M -M old ∞ < a and M old ∞ < a imply M -M 0 ∞ ≤ 3a.
We now consider two cases, depending on whether the matrix M -M 0 3a belongs to the set C (72 rank(M 0 )) or not. Then (31) implies that 1 3a M -M 0 ∈ C (72 rank(M 0 )) and we can apply Lemma 9. From Lemma 9 and (29) we obtain that with probability at least 1 -8/d one has

1 2 M -M 0 2 L2(Π) ≤ 5λ 2rank(M 0 ) 3 M 0 -M 2 + 369 a 2 p -1 72 rank(M 0 ) (E ( Σ R )) 2 + 18 ≤ 6λ 2 p -1 rank(M 0 ) + p 4 M -M 0 2 2 + 369 a 2 p -1 72 rank(M 0 ) (E ( Σ R )) 2 + 18 .
Now (3) imply that, there exist numerical constants C such that

M -M 0 2 L2(Π) ≤ C p -1 rank(M 0 ) λ 2 + a 2 (E ( Σ R )) 2 + a 2 ,
which leads to the statement of the Theorem 2.

B Proof of Theorem 8

We adopt the proof of Theorem 5 in [START_REF] Koltchinskii | Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion[END_REF] to our setting. Assume w.l.o.g. that m 1 ≥ m 2 . For a γ ≤ 1, define

L = L = (l ij ) ∈ R m1×r : l ij ∈ 0, γ(σ ∧ a) r p m 1/2 , ∀1 ≤ i ≤ m 1 , 1 ≤ j ≤ r ,
and consider the associated set of block matrices

A = L = ( L • • • L O ) ∈ R m1×m2 : L ∈ L ,
where O denotes the m 1 × (m 2 -r⌊m 2 /(2r)⌋) zero matrix, and ⌊x⌋ is the integer part of x. and, then, we replicate this matrix to obtain a block matrix L of size

m 1 × m 2 L =            L . . . L O            .
By construction, any element of A as well as the difference of any two elements of A has rank at most r. In addition, condition p ≥ r m implies that the entries of any matrix in A take values in [0, a]. Thus, A ⊂ A(r, a).

The Varshamov-Gilbert bound (cf. Lemma 2.9 in [START_REF] Tsybakov | Introduction to nonparametric estimation[END_REF]) guarantees the existence of a subset A 0 ⊂ A with cardinality Card(A 0 ) ≥ 2 (rM)/8 + 1 containing the zero m 1 × m 2 matrix 0 and such that, for any two distinct elements A 1 and

A 2 of A 0 , A 1 -A 2 2 2 ≥ M r 8 γ 2 (σ ∧ a) 2 r p m m r ≥ γ 2 16 (σ ∧ a) 2 m 1 m 2 r p m . ( 33
)
Using that, conditionally on X i , the distributions of ξ i are Gaussian, we get that, for any A ∈ A 0 , the Kullback-Leibler divergence K P 0 , P A between P 0 and P A satisfies

K P 0 , P A = 1 2σ 2 A 2 L2(Π) ≤ γ 2 M r 2 . (34)
From (34) we deduce that the condition 1 Card(A 0 ) -1

A∈A 0 K(P 0 , P A ) ≤ α log Card(A 0 ) -1 (35)
is satisfied for any α > 0 if γ > 0 is chosen as a sufficiently small numerical constant depending on α. In view of (33) and (35) and using the application of Theorem 2.5 in [START_REF] Tsybakov | Introduction to nonparametric estimation[END_REF] implies

inf M sup M0∈ A(r,a) P M -M 0 2 2 m 1 m 2 > C(σ ∧ a) 2 r pm ≥ β (36)
for some absolute constants β ∈ (0, 1), which implies the statement of Theorem 8.

C Proof of Lemma 9

This proof is close to the proof of Lemma 12 in [START_REF] Klopp | Noisy low-rank matrix completion with general sampling distribution[END_REF]. Set

E = 44 p -1 r (E ( Σ R )) 2 + 18 .
We will show that the probability of the following "bad" event is small

B = ∃ A ∈ C(r) such that A Ω 2 2 -A 2 L2(Π) > 1 2 A 2 L2(Π) + E .
Note that B contains the complement of the event that we are interested in.

In order to estimate the probability of B we use a standard peeling argument.

Let ν = log(d) 0.0006 log (6/5) p and α = 6 5 . For l ∈ N set

S l = A ∈ C(r) : α l-1 ν ≤ A 2 L2(Π) ≤ α l ν .
If the event B holds for some matrix A ∈ C(r), then A belongs to some S l and

A Ω 2 2 -A 2 L2(Π) > 1 2 A 2 L2(Π) + E > 1 2 α l-1 ν + E = 5 12 α l ν + E. (37)
For T > ν consider the following set of matrices

C(r, T ) = A ∈ C(r) : A 2 L2(Π) ≤ T
Next we bound the expectation E (Z T ). Using a standard symmetrization argument (see e.g. [START_REF] Ledoux | The concentration of measure phenomenon[END_REF]) we obtain

E (Z T ) = E   sup A∈C(r,T ) (i,j) η ij A 2 ij -E η ij A 2 ij   ≤ 2E   sup A∈C(r,T ) (i,j) ǫ ij η ij A 2 ij  
ǫ ij η ij A ij   = 8 E sup A∈C(r,T ) | Σ R , A |
where Σ R = (i,j) ǫ ij η ij X ij . For A ∈ C(r, T ) we have that

A * ≤ √ r A 2 ≤ r p -1 A L2(Π) ≤ r p -1 T
where we have used [START_REF] Cai | A singular value thresholding algorithm for matrix completion[END_REF]. Then, by the duality between nuclear and operator norms, we compute

E (Z T ) ≤ 8E   sup A * ≤ √ r p -1 T | Σ R , A |   ≤ 8 r p -1 T E ( Σ R ) .
Finally, using

E Proof of Lemma 1

It is easy to see that

(M k+1 -M k ) Ω ≤ (M k+1 -M k ) Ω 2 ≤ M k+1 -M k 2

F Proof of Lemma 4

In order to prove [START_REF] Foygel | Concentration-based guarantees for low-rank matrix reconstruction[END_REF], we use the following remarkable bound on the spectral norms of random matrices. It is obtained by extension to rectangular matrices via self-adjoint dilation of Corollary 3.12 and Remark 3.13 in [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF] (cf., Section 3.1 in [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF]).

Proposition 13 ([2]

). Let A be the m 1 × m 2 rectangular matrix whose entries A ij are independent centered bounded random variables. Then, for any 0 < ǫ ≤ 1/2 there exists a universal constant c ǫ such that, for every t ≥ 0

P A ≥ (1 + ǫ)2 √ 2(σ 1 ∨ σ 2 ) + t ≤ (m 1 ∧ m 2 ) exp -t 2 c ǫ σ 2 *
where we have defined

σ 1 = max i j E[A 2 ij ] σ 2 = max j i E[A 2 ij ] σ * = max ij |A ij |.
We apply Proposition 13 to Σ = (i,j) η ij ξ ij X ij . We compute

σ 1 = max i j E[η 2 ij ξ 2 ij ] = σmax i √ π i• and σ 2 = σmax j √ π •j .
Bound (4) implies that σ 1 ∨ σ 2 ≤ σ √ L. On the other hand, Assumption 1 implies max ij |η ij ξ ij | ≤ b. Now, taking in Proposition 13 ǫ = 1/2 we get [START_REF] Foygel | Concentration-based guarantees for low-rank matrix reconstruction[END_REF].

In order to prove [START_REF] Gross | Recovering low-rank matrices from few coefficients in any basis[END_REF] we use the following result Proposition 14 (Corollary 3.3 in [START_REF] Bandeira | Sharp nonasymptotic bounds on the norm of random matrices with independent entries[END_REF]). Let A be the m 1 ×m 2 rectangular matrix with A ij independent centered bounded random variables. Then, there exists a universal constant C * such that,

E A ≤ C * σ 1 ∨ σ 2 + σ * log(m 1 ∧ m 2 )
where σ 1 , σ 2 , σ * are defined in Proposition 13.

We apply Proposition 14 to Σ R = (i,j) η ij ǫ ij X ij where {ǫ ij } is i.i.d. Rademacher sequence. We have that σ 1 ∨ σ 2 ≤ √ L and σ * ≤ 1, then Proposition 14 implies [START_REF] Gross | Recovering low-rank matrices from few coefficients in any basis[END_REF].

•

  , d r ] and t + = max(t, 0). For any set I, |I| denotes its cardinal and Ī its complement. Let a ∨ b = max(a, b) and a ∧ b = min(a, b).

Case 1 : 2 L2Case 2 : 2 L2

 1222 Suppose first that M -M 0 It remains to consider the case M -M 0 log (6/5) p .

Remark 3 .

 3 In the case m 1 < m 2 , we only need to change the construction of the low rank component of the test set. We first build a matrix L = L O ∈ R r×m2 where L ∈ R r×(m2/2) with entries in 0, γ(σ ∧ a)

P Z T ≥ 5 12 T

 12 r p -1 T E ( Σ R ) r p -1 (E ( Σ R )) 2and the concentration bound (38) we obtain that + 44 p -1 r (E ( Σ R )) 2 + 18 ≤ 4e -c1 p T with c 1 ≥ 0.0006 as stated.

  where {ǫ ij } is an i.i.d. Rademacher sequence. Then, the contraction inequality (see e.g. [16, Theorem 2.2]) yields

		
	E (Z T ) ≤ 8E	 sup

A∈C(r,T ) (i,j)

and the following event

Note that A ∈ S l implies that A ∈ C(r, α l ν). Then (37) implies that B l holds and we get B ⊂ ∪ B l . Thus, it is enough to estimate the probability of the simpler event B l and then apply the union bound. Such an estimation is given by the following lemma. Its proof is given in Appendix D. Let

Lemma 10. We have that

with c 1 ≥ 0.0006.

Lemma 10 implies that P (B l ) ≤ 4 exp(-c 1 p α l ν). Using the union bound we obtain

where we used e x ≥ x. We finally compute for ν = log(d) 0.0006 p log (6/5)

.

This completes the proof of Lemma 9.

D Proof of Lemma 10

We will start by showing that Z T concentrates around its expectation and then we will upper bound the expectation. Recall that by definition,

We use the following Talagrand's concentration inequality :

Then for any t ≥ 0,

For a proof see [START_REF] Talagrand | A new look at independence[END_REF] and [START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF]. Let f (x 11 , . . . , x m1m2 ) : = sup

It is easy to see that f (x 11 , . . . , x m1m2 ) is a Lipschitz function with Lipschitz constant L = p -1 T . Indeed,

where we used ||a| -|b|| ≤ |a -b|, A ∞ ≤ 1 and A 2 L2(Π) ≤ T . Now, Theorem 11 and 2 p -1 T ≤ T + p -1 imply

Taking t = 1 9 1 3 T we get

with c 1 ≥ 0.0006. and

Thus, it is enough to show [START_REF] Chatterjee | Matrix estimation by universal singular value thresholding[END_REF]. The proof of ( 8) is close to the proof of Lemma 4 in [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF].

Let us denote for by Mk the solutions produced by Algorithm 1 after softthresholding step and before truncating step [START_REF] Candès | The power of convex relaxation: near-optimal matrix completion[END_REF]. We have that

where in the second inequality we used the following result (see, for example, Lemma 3 in [START_REF] Mazumder | Spectral regularization algorithms for learning large incomplete matrices[END_REF])

Proposition 12. The soft-thresholding operator S λ (•) satisfies the following:

The inequality (39) implies that the sequence { M k -M k-1 2 } k≥1 converges. It remains to show that it converges to zero. Note that the inequalities (39) imply that

So, we only need to show that (M k+1 -M k )Ω 2 → 0. We put

Note that [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] implies

where in the last inequality we used that

The inequality (40) shows that the sequence {Q(M k , M k )} k≥1 converges. This and (40) yield

Now, it is easy to see that

Indeed, for (i, j) in Ω such that M k+1 ij = M k+1 ij we have that

and for (i, j) in Ω such that M k+1 ij = M k+1 ij we have that

where we used (41). Now (42) together with (43) imply ( 8) which completes the proof of Lemma 1.