The impact of digital technologies on perceptions of proximity

Bastien Bernela*, Marie Ferru*, Alain Rallet* Draft, January 2019 * CRIEF, University of Poitiers, bastien.bernela@univ-poitiers.fr ** CRIEF, University of Poitiers, marie.ferru@univ-poitiers.fr *** RITM, University of Paris Sud, Paris Saclay, alain.rallet@u-psud.fr

Introduction: from objective to perceived proximity

The approach developed by the research group "Proximity Dynamics" (RERU, 1993) seeks to avoid reducing space to distance and transportation costs [START_REF] Bellet | Approches multiformes de la proximité[END_REF], and to deliver a qualitative characterization of distance through a more complex understanding of proximity. In an attempt to enrich the concept of proximity and expand it to embrace various forms of coordination, the authors introduce different types of proximity (Torre and [START_REF] Rallet | Proximity and localization[END_REF][START_REF] Boschma | Proximity and innovation. A critical assessment[END_REF]. The concept of proximity thus loses its exclusively geographical character, and needs to be distinguished from the notion of co-location.

In this context, the authors of the group have from the very outset stressed the crucial importance of perceptions of space. However, this latent program has not been kept in most subsequent empirical contributions by the "Proximity Dynamics" group, where a tendency towards objectivism (i.e. the assignation of proximity to pure objective contents) can be observed. Literature on proximity thus generally measures objective forms of proximity, although perceived proximity is also important in explaining actors' behaviors. Perception issues are crucial to understand socio-economic coordination issues arising between actors; for instance, this question is at the heart of the debate in the geography of innovation, when discussing constraints affecting interactions between partners in collaborative projects. From this perspective, we examined the growing development of digital technologies and the ways in which it can affect the actors' behavior (namely, the way they interact) and their perceptions of proximity (looking for instance at the increasing ease with which people can interact remotely).

The objective of this chapter is to analyze the impacts of the current digital revolution on proximity through the changes it brings about in the perception of proximity. In this chapter, we mainly focus on the perception of geographical proximity.

The first section is dedicated to an analysis of the perception of geographical proximity. We suggest that three determinants can affect this perception: distance obviously, but also constraints related to F2F interaction, as well as the effects of non-geographical proximity. In this perspective, we examine different types of literature -geography, sociology and psychology -, highlighting the contributions and evolutions brought by the multidisciplinary work of the group "Proximity Dynamics". The second section shows how the development of ICT has modified the perception of geographical proximity through its impact on these three determinants. We review literature on this issue among studies on proximity and related works. Finally, in the third section, we address an open issue by taking into account the impacts of the most recent generation of digital technologies on spatio-temporal representations of proximity. This leads us to propose a new concept of proximity: "proximity on the move", at the crossroads of mobility and proximity.

Geographical proximity as perceived proximity

As various social sciences have shown, the position of actors in space is not only a matter of rationality and objective factors but also a matter of how these actors represent themselves. The work of the "Proximity Dynamics" group forms part of this trend, as it highlights the importance of perceptions of space.

According to literature on this topic, the perception of geographical proximity is mainly based on three elements: distance, face-to-face constraints and feedback effects between types of proximity. a) First of all, the perception of proximity is related to distance, which itself depends on the perception of movement. On this first point, according to "proximist" literature, distance is relative to transportation costs and time. From this perspective, Torre and [START_REF] Rallet | Proximity and localization[END_REF] consider that two actors are considered as close if they can meet physically every day. A 300 km train journey between two cities may be faster than going from the south to the north of a metropolitan area. According to the authors, geographical proximity is also related to the assessment made by individuals, which consists in considering all the parameters that influence distance. This set of parameters includes objective data (km, time, price) but also the perceptions held by individuals (Torre and [START_REF] Rallet | Proximity and localization[END_REF]. Proximity is for instance related to the stress experienced as a result of distance [START_REF] Bourdeau-Lepage | Proximités et interactions : une reformulation[END_REF]: the possibility of meeting once a day may be perceived differently depending on the person, his/her age, social group, gender, occupation, etc. For the first time, such works finally presented the intuition that perceptions matter; however, in their further empirical developments, the authors propose an axiomatic measure (near vs. distant) or an objective one (km, time, costs) that negates their initial insights.

The analysis of perceptions of distance has been further developed by other social sciences and primarily by geographers, although this discipline mainly focused on the physical materiality of space. Building on the one hand on Simon's thesis on limited rationality and on the other on psychologists' work on cognitive biases, American geographers developed the "geography of perception" in the 1950s [START_REF] Golledge | Behavioral geography and the theoretical/quantitative revolution[END_REF][START_REF] Gould | Mental maps[END_REF]. In the 1970s, French geographers also argued for a geographical analysis focused on the perception of space (Frémont, 1974[START_REF] Frémont | L'espace vécu[END_REF]Claval, 1974;[START_REF] Bailly | La perception de l'espace urbain. Les concepts, les méthodes d'étude, leur utilisation dans la recherche urbanistique[END_REF][START_REF] Bailly | Subjective distances and spatial representations[END_REF]Bailly, , 1990)), leading to numerous debates on the relationship between subjective and objective categories of space.

The "geography of perception" is basically based on the idea that an individual perceives information depending on previously acquired knowledge and experience, which in turn have been built from previous actions or perceptions. This transformation of information produces a subjective representation of reality, which influences individual decisions [START_REF] Zenker | Innovation, perception and regions: Are perceptions of the environment related to firms' innovation behaviours? The cases of Alsace and Baden[END_REF]. The emphasis is placed on cognitive aspects and interactions between the individual and the social context within a territorial context. In methodological terms, the "geography of perception" uses various methods from declarative questionnaires to the examination of novels, speeches, reports and practices that provide complementary representations of space. Cartography as an instrument was adapted to integrate the perception of distances through anamorphic maps; mental maps were also developed as a subjective spatial investigation model [START_REF] Gould | Mental maps[END_REF].

More recently, a relatively abundant literature has developed on the geography of transport [START_REF] Vos | Travel and subjective wellbeing : a focus on findings, methods and future research needs[END_REF], expanding the scope of the perception of distance to include well-being. Authors seek to measure the levels of well-being associated with movement (i.e. the concept of "satisfaction with travel scale" (De [START_REF] Vos | How satisfying is the Scale for Travel Satisfaction?[END_REF]) and to analyze the explanatory factors associated with this well-being; and conversely, the impact of distance on the general wellbeing of individuals or on transport-related behaviors such as modal choices (De [START_REF] Vos | Travel satisfaction revisited. On the pivotal role of travel satisfaction in conceptualising a travel behaviour process[END_REF]. b) Once the distance has been traveled (i.e. the co-location has been made possible, at least temporarily), authors agree that physical contact provides an incomparable sensory perception of the actor you are coordinating with (for instance, a partner in a research collaboration). As explained by [START_REF] Urry | Mobility and Proximity[END_REF], "historically, the social sciences have overly focused upon ongoing geographically propinquitous communities based on more or less face-to-face social interactions between those present". This conventional wisdom is based on the assumption that it is difficult to develop effective teamwork at a distance without any significant "facetime" [START_REF] Winger | Face-to-face communication: Is it really necessary in a digitizing world?[END_REF], considering the various advantages of face-to-face (F2F) interaction. This is because 1) F2F mitigates problems to do with incentives and free riding since it is easier to observe and interpret a partner's behavior in a F2F situation. 2) F2F interaction promotes the development of trust, based on reputation effects [START_REF] Gambetta | Trust[END_REF][START_REF] Lorenz | Trust and the Theory of Industrial Districts[END_REF]. 3) F2F interactions offer "an unusual capacity for interruption, repair, feedback, and learning" (Nohria and Eccles, 1992, p. 292). 4) Tacit knowledge can easiest be transmitted in a F2F context, which justifies the co-location of innovative firms [START_REF] Maskell | Localised learning and industrial competitiveness[END_REF]. This F2F thesis was relatively well developed by the authors of the "Proximity Dynamics" group. They specify that F2F interactions are all the more crucial for some specific tasks: for knowledge-intensive activities such as innovation processes, the more tacit the shared knowledge is and, the more F2F is required [START_REF] Aguiléra | Transmission des connaissances dans les relations de coopération interentreprises : TIC versus face-à-face[END_REF]. In addition, the more frequent the interactions between partners and the greater the need for F2F contact. As these characteristics (tacit knowledge, frequency of interactions) vary according to the innovation cycle, the F2F constraint depends on the stage of the project (Torre and [START_REF] Rallet | Proximity and localization[END_REF]Gallié and Guichard, 2005). An in-depth case study of technology transfer in the biotechnology sector by [START_REF] Gallaud | Geographical proximity and the diffusion of knowledge (The case of SME's in biotechnology)[END_REF] confirms these findings and reveals that for most partnerships, interactions are frequent during partner search and contract negotiationespecially when actors have very different knowledge bases and the project is loosely structured.

This F2F thesis has also been augmented by non-proximist research developed for instance by [START_REF] Bathelt | Clusters and knowledge: Local buzz, global pipelines and the process of knowledge creation[END_REF], [START_REF] Bathelt | Local, global and virtual buzz: The importance of face-to-face contact in economic interaction and possibilities to go beyond[END_REF], or [START_REF] Storper | Buzz: Face-to-face contact and the urban economy[END_REF]. The latter authors interestingly highlighted four main features of F2F interaction: it provides an efficient communication technology; it can help solve incentive problems as well as facilitating socialization and learning; and it provides psychological motivation. These authors also specify how F2F can be crucial in environments where information is imperfect, rapidly changing and not easily codified. In this context, "corporeal proximity in diverse modes appears to make travel necessary and desirable" [START_REF] Urry | Mobility and Proximity[END_REF]: the F2F thesis therefore justifies the actors' mobility. Indeed, mobility involves occasional, intermittent face-to-face conversations and meetings within certain places at certain moments that seem obligatory to some or all of the participants (…) To maintain trust, people need to -at least intermittentlymeet and experience the effervescence of this collaborative live performance (ibid.).

c) The perception of geographical proximity is also determined by the existence (or the absence) of other forms of proximity. Researchers have found that physical proximity explains no more than half of a person's feeling of "subjective distance" [START_REF] Coshall | Social psychological variations in the distance cognitions of urban consumers in Britain[END_REF]. This depends on the context in which the situation is performed as defined by Goffman (1991) -i.e. a form of representation of reality that guides individuals' perceptions. This work, initially developed by psychologists, echoes recent developments in management studies (Wilson et al., 2008;O' Leary et al., 2014;etc.), which define "perceived proximity as a dyadic and asymmetrical construct that reflects one person's perception of how close or how far another person is" (Wilson et al., 2008(Wilson et al., , p. 1222)). Research later examined the paradoxical phenomenon of the « Far-but-Close » and its contrary the « Close-but-Far » (Wilson et al., 2008). This paradoxical phenomenon refers to the notion that a person can feel quite distant despite being in close physical proximity, while another may seem quite close although he or she is far away in objective terms. The authors argued that one can perceive proximity differently depending on each individual's relative situation. The findings obtained by these research projects suggested that distance does not affect the quality of relationships in geographically distributed teams but perceived proximity does.

Proximist literature enriched this debate with an empirical dimension through the notion of "activating geographical proximity". Geographical proximity is not perceived as such if it is not activated by non-geographical proximity. For instance, Aguilera et al (2015) show that some firms declare that proximity played a role in their cooperation with a partner when the partner was geographically distant and, conversely, that proximity did not matter when the partner was geographically close. To be close to someone is not only to be next to him/her, but it can also mean having a strong connection with a geographically distant person, whether they belong to the same circle of friendship, family or business, or professional network (Torre and [START_REF] Rallet | Proximity and localization[END_REF]. Strong organized (or relational) proximity can not only "compensate" for geographical distance but also impact the perception of geographical proximity itself. This thesis of the non-independence of proximity enables authors to take into account the role of perceptions: the perception of geographical proximity is altered by other forms of proximity [START_REF] Amin | Architectures of Knowledge: Firms, Capabilities, and Communities[END_REF][START_REF] Rallet | Proximity and localization[END_REF] and by the past construction of their combination [START_REF] Ferru | La géographie des collaborations pour l'innovation : le rôle des contraintes de ressources et de mise en relation[END_REF]. For instance, geographical proximity is less necessary if partners in an innovative project share the same field of knowledge (cognitive proximity), are embedded in the same social network (relational proximity), belong to the same organization or community (organizational proximity) or are immersed in the same system of values (institutional proximity). These various types of proximity do not remove the need for geographical proximity but minimize the perception of its importance. This leads many authors to distinguish between actual and activated geographical proximity [START_REF]Proximity relations at the heart of territorial development processes. From clusters, spatial conflicts and temporary geographical proximity to territorial governance[END_REF]. This interdisciplinary literature review allowed us to highlight three determining factors in the perception of geographical distance. The next section will examine the crucial and growing role of ICT, and its impact on perceived forms of proximity.

Impacts of ICT on perceived proximity

In literature on proximity, this factor has been mainly addressed as a coordination issue (see the critical survey carried out by [START_REF] Rallet | Geography of innovation, proximity and beyond[END_REF]. As a result, ICT has been considered as means of communication enabling economic agents to better coordinate across different locations [START_REF] Galliano | ICT Intensity of Use and the Geography of Firms[END_REF]. This gave rise to a debate about ICT's ability to lift the constraint of physical proximity to support certain interactions (Aguilera and Lethiais, 2011). A radical but also more naive approach raised the question of whether ICT would announce the end of geography (O' Brien 1990& 1992[START_REF] Cairncross | The Death of Distance[END_REF], or in other words the end of the constraint of physical proximity. Criticism of this thesis (Morgan 2004, Torre and[START_REF] Rallet | Proximity and localization[END_REF] has given rise to many theoretical and empirical works since the 90s. This section will outline the main directions and findings of these works. Their conclusions converge on the need to maintain face-to-face (F2F) relations on the one hand, and on the geographical extension of remote coordination on the other. It is interesting to note that reaching these conclusions involved taking into account the subjective dimension of proximity. We show this using the analytical framework presented in section 1. However, this literature considers the impact of digital technologies from a limited and somewhat outdated point of view. Limited, because it is restricted to coordination problems within production or innovation processes. Outdated because it does not take into account new generations of technologies that are deeply changing relations to space. The second part of this section examines how these limits are interrelated.

2-1 The impacts of ICT on the three dimensions of perceived proximity

What are the impacts of ICTs on the perception of geographical proximity? In other words, what are its impacts on the factors that explain this perception: objective distance, the requirement of F2F contact, and the intensity of non-spatial proximity? a) On distance ICT is mainly considered as a means of coordination. As such, it makes coordination easier by providing communication tools (telephone, e-mail, professional messaging, videoconferencing, etc.) and access to corporate information systems (intranet or extranet) and databases, whether for long-distance or short-distance coordination. In earlier literature on the relation between ICT and distance -i.e. studies published between the 80s and the beginning of this century -, ICT was considered as having no effect on the perception of physical distance because, as a (new) means of coordination, it was supposed to compete with another well-known way of coordinating in physical space: travel. The question was to what extent ICT could replace travel as a means of coordination. [START_REF] Moktarian | If telecommunication is such a good substitute for travel, why does congestion continue to get worse?[END_REF]. Most empirical papers showed that ICT could not provide a substitute for most professional trips but that it did in itself induce new reasons to travel (on this literature, see for instance the survey conducted by Aguilera and al., 2009). In terms of perception, this means that distance matters as much as it did before, even if ICT changed the nature of the activities for which distance remained necessary. For instance, some meetings can now be held remotely using videoconferencing (substitution effect), but the development of remote coordination induces new reasons for moving to solve interaction issues that require face-to-face relations (complementarity effect).

b) On F2F

As shown previously, the need for F2F interaction in literature on proximity is mainly analysed in innovation studies. It is explained by the tacit share of knowledge involved in processes while codified knowledge, which is disembodied from individuals, can more easily be transmitted at a distance [START_REF] Cowan | The Economics of Codification and the Diffusion of Knowledge[END_REF]. During this period, ICT was represented as a tool used for formalizing coordination routines (e.g. written communication) and objects (e.g. shared databases). As a result, the use of ICT was associated with a codification of coordination. This implicit association (linked to representations of ICT that were predominent at the time but not perceived as such) led to a simple conclusion: ICT tends to reduce the need for face-to-face contact only if it makes it possible to codify a larger part of the knowledge incorporated in the innovation process by digitizing it. In this case, ICT enhances the possibilities of remote communication. But insofar as innovation constantly recreates tacit knowledge in the emergence stage of projects, F2F is required because ICT is not suitable for the transfer of tacit knowledge [START_REF] Wallet | On the role played by temporary geographical proximity in knowledge transmission[END_REF].

c) On non-geographical proximity

ICT reinforces the effects of non-geographical forms of proximity on perceived proximity by lowering the cost of their channels (e.g. the global pipelines, see [START_REF] Bathelt | Clusters and knowledge: Local buzz, global pipelines and the process of knowledge creation[END_REF]): digitization of shared cognition, strengthening of geographically dispersed social ties (community effect) or distant organizational links (messaging, information systems), diaspora effect (sharing cultural values throughout geographical areas).

By reducing the need for F2F contact at certain stages of innovation projects and by increasing the power of non-spatial proximity to overcome distance barriers, ICT tends to decrease the perceived importance of the constraint of physical proximity. However, these technologies do not upset spatial patterns. They only accentuate past trends: geographical proximity continues to matter through co-location or temporary proximity, but remote coordination appears on the rise.

2-2 From ICT to the digital era: new perceptions of proximity

The impacts of ICT were mainly analyzed as the effects of the means of coordination between given locations on dyadic or bilateral relations. However, nowadays, the impacts of the digital cannot be reduced to the effects of coordination means applied within a dyadic framework between predefined locations. Digital technologies and markets are i) developing multilateral platform-based coordination, ii) transforming our relationship to space-time with the development of mobile communication tools, iii) renewing the question of F2F with the development of remote co-presence and introducing other mobility issues.

i) The ability to coordinate all the stakeholders of an innovation or production project is presumably greater when these are located in a localized ecosystem than in dispersed ones, because geographic proximity reduces the transaction costs involved in establishing relationships. However, the "platformization" of industries, which is one of the central features of the digital economy, tends to lower these transaction costs independently regardless of the location of stakeholders (except for certain specific platforms such as C-to-C platforms for second-hand goods). Multilateral coordination can therefore be expected to play less in favor of localized ecosystems, even if the proximity constraint does not disappear. Little work has been done so far on the impact of digital platforms on the geography of ecosystems (see [START_REF] Agrawal | Crowdfunding: Geography, Social Networks, and the Timing of Investment Decisions[END_REF] about crowdfunding platforms); this issue needs to become part of the research agenda, to assess how local ecosystem building and "translocal platforms" can be interwoven today [START_REF] Bathelt | The creation of knowledge: local building, global accessing and economic development-toward an agenda[END_REF].

ii) Mobile communication tools induce another relationship to space-time. The ability to communicate remotely and thus to coordinate at a distance was limited by the need to establish a connection from fixed locations. This is no longer the case: communication tools make it possible to continue to communicate and work from any point in space when there is network coverage. This property directly impacts the perception of geographical proximity insofar as individuals feel distant (due to geography) but at the same time close (due to their connection), whereas in the past geography imposed a binary situation: to be near or to be distant, to be there or elsewhere. In other words, co-presence is no longer the monopoly of geographical proximity: digital technologies make it possible to be both here and elsewhere to a certain extent.

iii) It should be added that, simultaneously, means of communication are becoming "warmer" thanks to new tactile and visual interfaces that deeply modify the previous generation of computer technologies marked by keyboard culture and written codification. O' Leary et al. (2014) show that even shared meaning and symbolic value between people separated by large distances can be conveyed by information systems, forming strong bonds between individuals. The need for F2F does not disappear but, because co-presence is enriched by these new media, it is no longer the preserve of geographical proximity.

Two major transformations of geographical proximity result from this change:

-What happens to the F2F constraint in this context? On the one side, F2F still matters for some interactions; on the other side, more and more interactions that previously required physical contact can be performed at a distance. This split is expected to develop in many areas, including those that traditionally involved rich human interactions (health, education, services, etc.). The perception of geographical proximity is divided into an irreducible component (when "thick" co-presence involves body language, facial gestures, voice intonation, etc. as stressed by [START_REF] Urry | Mobility and Proximity[END_REF]) and a distant component (see above, the "Far-but-Close" paradox).

-Relations between proximity and mobility must be redesigned. According to the initial configuration, mobility s the way of recreating a specific type of proximity: temporary proximity. But during the transportation process, any form of proximity was interrupted (except for very poor communication). Nowadays, mobile digital technologies make it possible to continue to develop interactions with remote people while on the move. We must therefore introduce, alongside temporary proximity, another type of proximity linked to mobility.

3-"Proximity on the move" as a dynamic type of proximity

The perception of geographical proximity is today affected by the development of a new form of proximity: proximity on the move. This proximity is based on mobility but in a different sense from that of temporary geographical proximity.

There is a natural and reciprocal link between mobility and proximity. But in studies on proximity, mobility has been mainly addressed from the point of view of proximity. Mobility is indeed the way of achieving a specific form of proximity: temporary geographical proximity [START_REF] Wallet | On the role played by temporary geographical proximity in knowledge transmission[END_REF][START_REF] Bathelt | Between luminaires and meat grinders: international trade fairs as temporary clusters[END_REF]. However, no contribution has so far focused specifically on the link between mobility and proximity (except for [START_REF] Urry | Mobility and Proximity[END_REF] who can be considered as external to this literature). In particular, there has been no analysis of proximity from the point of view of mobility. We argue in this section that i) mobility is not only a means of crossing over a distance, but also a new form of proximity that needs to be taken into account, ii) the rapid development of proximity on the move is due to a new generation of ICT that is deeply changing our relation to space and time.

3-1 From temporary geographical proximity to proximity on the move

As we have just pointed out, in literature on proximity mobility is connected to proximity, of which it is a specific form. Corporeal travel is necessary to have a F2F relationship with other people located in a different place.

Figure 1: Temporary geographical proximity

By analogy with comparative static analysis, we propose to define temporary proximity as a static form of proximity: it is a time interval between two locations -in the same way that comparative static analysis studies relations between two different states without analyzing the motion that leads from one to the other. In terms of temporary proximity, moving from one place to another is only a means for people to restore physical proximity when it has been broken by distance. Coordination is interrupted during the duration of travel, which is only a Move of A1 to meet A2

time interval between two spatial modes of coordination, between fixed locations on one side (left part of the figure 1) and within co-location on the other (right part).

Besides temporary proximity, it is necessary to consider another side of mobility defined as a dynamic form of proximity. It means that mobility is the (moving) place from which interactions with other people take place. This is made possible by the fact that trips no longer interrupt these interactions thanks to the use of mobile digital tools and communication networks (except for plane travel for the moment, but not for long). These tools and networks allow people to be continuously linked to colleagues, partners and firms by providing instant access to their resources (information, documents, databases, software, work tools...). The connection that supports interactions tends to be permanent (relying on both asynchronous and synchronous tools) and ubiquitous, subject to the conditions of network coverage. The activities performed on the move are sometimes limited by the network speed or the power and ergonomics of end-user devices. But these limitations tend to fade with broadband mobile networks and the ever-increasing power of user-friendly communication devices. As a result, almost all of a person's daily activities (including work and interactions) can be carried out during transport [START_REF]Is the bus boring?[END_REF][START_REF] Ettema | How in-vehicle activities affect work commuters' satisfaction with public transport[END_REF] or in connected places on the route called "third places" (so called because they are neither the workplace, nor the place of residence [START_REF] Oldenburg | The Great Good Place: Cafes, Coffee Shops, Community Centers, Beauty Parlors, General Stores, Bars, Hangouts, and How They Get You Through the Day[END_REF]). A fundamental change has thus been introduced by the new generation of ICT: transportation can no longer be considered as lost time [START_REF] Lyons | Travel time use in the information age[END_REF]. This mobility should not be restricted to the traditional mobility of professional nomads (sales representatives, maintenance engineers, consultants, etc.) whose jobs are located outside their companies. Today, it potentially affects everyone and already represents a significant share of our daily time, although transport statistics do not measure it yet.

We characterize this "proximity on the move" as a dynamic form of proximity, not only because it takes place on the move but also because its nature is temporal. Temporary geographical proximity is spatial by definition: proximity is achieved when the locations of A and B match after a displacement (see above). In contrast, the very nature of proximity on the move is temporal : the locations of A and B do not match but their temporalities do. Interactions are made possible by the permanency of this connection, not by an intermittent co-location. There is no reference to these aspects in the work of economists, but some have been developed by sociologists [START_REF] Urry | Mobility and Proximity[END_REF] his "mobility turn"; Bauman, 2002, and his "liquid society"; Kaufman, 2002, and his neologism "motility").

3-2 Impacts of proximity on the move on perceived proximity

Considering proximity on the move modifies the three elements of the perception of geographical proximity described in the first section:

-Distance is no longer a spatial operator of separation but the moving place of a temporal proximity;

-Co-presence is no longer restricted to a spatial phenomenon but is also a temporal one (temporal continuity of co-presence, not limited to F2F); -The feedback effects of non-geographical proximity are reinforced: individuals are continually caught in a network of relationships that constantly solicit them (messaging, conf calls, collaborative tools…).

Conclusion

The issue of geographical proximity is too often covered in a simplistic way, considering that 1) distance is the only metrics of proximity, in a spatial/temporal separation perspective, 2) F2F requires temporary proximity to address coordination issues in the case of remote partners. ICT is consequently considered as a means of coordination, more often as a substitute to than as a complement for proximity. This chapter proposes to contribute to these recurring debates by introducing more complexity into the way geographical proximity is understood.

First, we refer to old concerns about the perception of proximity that have been progressively disregarded: proximity is not only a matter of distance but is also related to face-to-face constraints and feedback effects with non-geographical forms of proximity. Modern ICT has impacts on this perceived proximity, as the sophistication of mobile communication tools has modified our relation to space and time: the continuous connection allowed by mobile technologies invites us to consider a new form of proximity that we call proximity on the move. We define this form of proximity in a spatio-temporal and dynamic way, whereas temporary geographical proximity is only defined in a spatial and static way. Proximity on the move makes a kind of co-presence possible while the parties involved are physically distant: mobility is no longer a tool to bring temporary actors together but it becomes a dynamic environment for activity.

This analytical grid faces methodological and empirical challenges, since forms of proximity are difficult to capture in all their complexity. Conceptual advances have often been insufficiently explored empirically, because they are faced with issues to do with data availability and collection. In order to maintain the subjective character of spatial proximity, Carriou et al. (2018) propose for instance to better understand individuals' perceptions of proximity through their representations of the places in which they work or transit. Qualitative approaches and more precisely mental maps are used to capture these representations, but the large amount of collected data makes it possible for researchers to carry out quantitative treatments.


Viscoelastic Simulation of P.E.T Stretch/Blow Molding Fabrice Schmidt, Jean-François Agassant, Michel Bellet, Luc Desoutter To cite this version: Fabrice Schmidt, Jean-François Agassant, Michel Bellet, Luc Desoutter. Viscoelastic Simulation of P.E.T Stretch/Blow Molding. 9th International Conference of the Polymer Processing Society, Apr 1993, Manchester, United Kingdom. hal-02053322 Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org) Powered by TCPDF (www.tcpdf.org)


Uy Hour Tan Fabien Arlery

Olivier Rabaste

Generalization and Improvement of the Levenshtein Lower Bound for Aperiodic Correlation

Keywords: Aperiodic correlation lower bound, Levenshtein bound, Welch bound

This article deals with lower bounds on aperiodic correlation of sequences. It intends to solve two open questions. The first one is on the validity of the Levenshtein bound for a set of sequences other than binary sequences or those over the roots of unity. Although this result could be a priori extended to polyphase sequences, a formal demonstration is presented here, proving that it does actually hold for these sequences. The second open question is on the possibility to find a bound tighter than Welch's, in the case of a set consisting of two sequences M = 2. By including the specific structure of correlation sequences, a tighter lower bound is introduced for this case. Besides, this method also provides in the cases M = 3 and M = 4 a tighter bound than the up-to-now tightest bound provided by Liu et al..

I. INTRODUCTION

Aperiodic correlation arises as the output of the matched filter in many applications, such as asynchronous Direct-Sequence Spread-Spectrum (DSSS) systems in digital communications, or pulse radars [START_REF] Majumder | Design and analysis of radar waveforms achieving transmit and receive orthogonality[END_REF]. It is usually of interest to consider sequences with the lowest possible sidelobe level. For instance, in radar applications, a low-sidelobe sequence may avoid a weak target to be buried in the sidelobes generated by a stronger one. Depending on the applications, such as the MIMO radar [START_REF] Majumder | Design and analysis of radar waveforms achieving transmit and receive orthogonality[END_REF], it may be necessary to consider families of several sequences with low aperiodic auto-and cross-correlations. Lower bounds on the maximum aperiodic correlation sidelobes are thus interesting to determine the best performance a system could achieve.

The computation of lower bounds on a set of sequences is a recurrent topic in the literature [START_REF] Welch | Lower bounds on the maximum cross-correlation of signals (Corresp.)[END_REF], [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF], [START_REF] Xiang | Optimal codebooks from binary codes meeting the levenshtein bound[END_REF]. Two different problematics can be found: some articles consider the problem of computing lower bounds on codebooks, which consists in fact of computing the lower bound of any inner product between two sequences in the codebook. This optimal codebook is not the concern of this paper. Here is considered on the contrary the problem of computing lower bounds on correlation sequences, in other words lower bounds on the inner products between any two sequences among the set with any possible delay shift. This problem is thus completely Manuscript received October 16, 2017; first revision: January 28, 2018; second revision: May 19, 2018; date of current version: February 18, 2019.

F. Arlery was with SAMOVAR, Telecom SudParis, CNRS, Université Paris-Saclay, Évry, France, and with Thales Air Systems, Limours, France.

U. Tan is with Sondra, CentraleSupélec, Université Paris-Saclay, Gifsur-Yvette, France, and was with Thales Air Systems, Limours, France. Corresponding e-mail: u.tan@laposte.net.

O. Rabaste is with DEMR, ONERA, Université Paris-Saclay, 91 123 Palaiseau, France. Corresponding e-mail: olivier.rabaste@onera.fr. different from the codebook problem, and in that case no family set is known to meet the existing bounds, which are likely to be not tight enough yet.

Besides, the first lower bound on aperiodic correlation was proposed by Welch in 1974 [START_REF] Welch | Lower bounds on the maximum cross-correlation of signals (Corresp.)[END_REF] for sets of M sequences of length N with identical energy. Its proof is based on the computation of the maximum value taken by the inner products between any two pairs of sequences among a given set. A new bound was proposed only almost 25 years later by Levenshtein [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF], [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF] for the specific case of binary sequences. This bound, based on the introduction of a weight vector, was proved to be tighter than the Welch bound for any M ≥ 4 and N ≥ 2. It was shown soon after that the Levenshtein bound also holds for sequences over the roots of unity [START_REF] Boztas | New lower bounds on aperiodic cross-correlation of codes over the nth roots of unity[END_REF]. Note that both proofs require first to enumerate the number of all possible sequences in the considered set (the set of binary sequences or the set of sequences over the roots of unity) and second to quantify the minimum distance between two different sequences, which is not possible when considering the set of unimodular sequences, as it contains an infinite number of sequences and hence presents a minimum distance equal to zero. Finally, Liu et al. recently proposed a new weight vector that provides a tighter Levenshtein bound for M = 3, N ≥ 3 and any M ≥ 4, N ≥ 2 [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF]. However, as stated both in [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF] and [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF], the Welch bound remains up to now the tightest bound in the case M = 2, since a better bound cannot be provided by the Levenshtein method in that particular case. Thus two problems remain open: first, the validity of the Levenshtein bound to more general sequence sets than sequences over the roots of unity, and second, the possibility to find a tighter bound than the Welch bound in the case M = 2.

When studying the proofs of the Welch and the Levenshtein bounds, it can be noticed that the very specific structure of the sets used for the aperiodic correlation is not fully exploited. Based on this observation, this paper provides new results that enable to provide answers to the two open questions above. First, we demonstrate that the Levenshtein bound holds for all unimodular sequences. This result is quite expected, as a natural extension of Boztas ¸' work [START_REF] Boztas | New lower bounds on aperiodic cross-correlation of codes over the nth roots of unity[END_REF]. However, in his proof appears the cardinality of the set of sequences over the roots of unity for a given N . In the case of unimodular sequences, this cardinality tends to infinity, so that the extension of Boztas ¸' proof may not be that straightforward. Thus in this paper is presented a formal proof that does not require this cardinality. Interestingly this proof mixes Welch and Levenshtein methods, removes the usage of the Cauchy-Schwarz inequality, and exploits to some extent the structure provided by the aperiodic correlation. In particular, this proof does not require the enumeration of the set of unimodular sequences and the minimum distance between any two sequences. Second, we show that this specific structure enables to tighten the upper bound over the energy of all inner products used in Welch's proof and thus to get a tighter bound in the case M = 2. We also show that it provides in the cases M = 3 and M = 4 a tighter bound than the tightest Levenshtein bound provided in [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF].

This article is organized as follows. Section II provides a review on the well-known Welch and Levenshtein bounds on the aperiodic correlation. A generalization of the latter for unimodular sequences is presented in Section III. Section IV tightens this Levenshtein bound, introducing a parameter on the number of delays considered. This improvement is illustrated in Section V in several cases according to the number of sequences M . Finally, some proofs are detailed in the appendices.

Notation: In the following, bold letters designate matrices and vectors. (.) * , (.) T and (.) H denote the conjugate, the transpose and the transpose conjugate operator, respectively. 0 m,n denotes the null matrix (a matrix where all the entries are equal to zero) of size m×n. I n is the identity matrix of size n. • F stands for the Frobenius norm. For an m × n matrix A, it is defined by

A F = m i=1 n j=1 |a i,j | 2 .
Finally, circulant matrices are defined through a map denoted circ, and are specified by a vector x = [x 1 , . . . , x n ] of length n:

                                 C n → C n×n x → circ(x) =               x 1 x 2 . . . x n-1 x n x n x 1 x 2 x n-1 . . . x n x 1 . . . . . . x 3 . . . . . . x 2 x 2 x 3 . . . x n x 1              
.

II. REVIEW ON EXISTING BOUNDS

This paper focuses on the calculation of lower bounds on the maximum sidelobe level of auto-and cross-correlation sidelobes for unimodular sequences. Let {x m } m∈ 1,M be a set of M sequences of length N , such that any n-th entry of any m-th sequence satisfies |x m n | 2 = 1/N . Thus the energy of each sequence (x m ) m∈ 1,M , denoted by E x , is constant and equal to 1.

The aperiodic cross-correlation between two sequences x m1 and x m2 can be defined as:

θ x m 1 ,x m 2 (k) = N n=1 x m1 n (x m2 n+k ) * , for |k| < N, (1)
where we set x m l = 0 for any l ≤ 0 or l > N . The aperiodic autocorrelation is simply obtained for m 1 = m 2 and will be denoted by θ x m 1 (k).

Several lower bounds have been developed on the maximum sidelobe level of the auto-and cross-correlations. This maximum level will be denoted in this paper by θ max and is provided by:

θ 2 max = max    max |k|<N m1 =m2 |θ x m 1 ,x m 2 (k)| 2 , max k =0 m1 |θ x m 1 (k)| 2    . (2)
The Peak-to-Sidelobe Level, denoted by PSL, and used hereafter for comparison purpose, is defined by:

PSL = θ 2 max E 2 x , (3)
and is simply equal here to PSL = θ 2 max since E 2 x = 1. The most well-known bounds were provided by Welch [START_REF] Welch | Lower bounds on the maximum cross-correlation of signals (Corresp.)[END_REF] and Levenshtein [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF]. The Welch bound, valid for any family of unit energy sequences, is provided by:

PSL ≥ M -1 M (2N -1) -1 . (4)
More recently, a tighter bound has been established by Levenshtein [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF]. It introduces a weight vector w of length 2N -1 -applied on each correlation sequence -that should satisfy the following weighting condition:

2N -1 i=1 w i = 1, with w i ≥ 0 if i ∈ 1, 2N -1 , w i = 0 otherwise. (5)
Initially determined for binary sequences [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF], the Levenshtein bound was shown in [START_REF] Boztas | New lower bounds on aperiodic cross-correlation of codes over the nth roots of unity[END_REF] to be valid for sequences over the roots of unity. This bound is expressed by:

PSL ≥ 1 N 2       N - Q 2N -1 w, N (N -1) M 1 - 1 M 2N -1 i=1 w 2 i       , (6)
where w is any weight vector that satisfies the weighting condition (5), and:

       Q 2N -1 (w, a) = a 2N -1 i=1 w 2 i + 2N -1 s,t=1 l s,t,N w s w t , l s,t,N = min(|s -t|, 2N -1 -|s -t|). (7)
If w i = 1/K for i ≤ K, and w i = 0 otherwise, it has been shown that, for all K ∈ 1, N :

PSL ≥ 1 N 2 3N M K -3N 2 -M K 2 + M 3(KM -1) . ( 8
)
An optimal choice of the parameter K in the right-hand side of ( 8) further provides:

PSL ≥ 1 N 2 N - 2N √ 3M when M ≥ 3. (9)
Besides, the previous theorem induces a minimization problem on the quadratic form Q 2N -1 (w, a) under the weighting condition. Levenshtein tackled it in [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF], and obtained a tighter bound:

PSL ≥ 1 N 2 N - πN √ 8M when 5 ≤ M ≤ N 2 . ( 10
)
In [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF], [START_REF] Liu | Quadratic weight vector for tighter aperiodic levenshtein bound[END_REF], [START_REF] Liu | Asymptotically Locally Optimal Weight Vector Design for a Tighter Correlation Lower Bound of Quasi-Complementary Sequence Sets[END_REF], specific weight vectors w are used in order to obtain tighter Levenshtein bounds.

III. GENERALIZATION OF THE LEVENSHTEIN BOUND

In this section, we establish that the Levenshtein bound holds for any set of unimodular sequences. This generalization of Levenshtein's result is performed in two steps: first a calculation of upper and lower bounds on the Frobenius norm of an auto-and cross-correlation matrix, and second the deduction of the lower bound on the PSL.

Let

{x m } m∈ 1,M be a set of M unimodular sequences of length N with |x m n | 2 = 1/N for each n ∈ 1, N . Consider the matrix X of size [M (2N -1)] × [2N -1]: X =      X 1 X 2
. . .

X M      (11)
with X m , m ∈ 1, M , a square matrix of order 2N -1 defined by:

X m =                           x m 1 x m 2 • • • x m N -1 x m N 0 0 • • • 0 0 x m 1 x m 2 • • • x m N -1 x m N 0 0 . . . 0 0 . . . . . . 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 0 • • • • • • 0 x m 1 x m 2 • • • x m N -1 x m N x m N 0 0 0 0 x m 1 x m 2 x m N -1 x m N -1 x m N 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 x m 1 x m 2 x m 2 • • • x m N -1 x m N 0 • • • • • • 0 x m 1                           .
Remark that X m is circulant and specified by the vector

[x m , 0 N -1,1 ] T . Denote by X m i , i ∈ 1, 2N -1 the i-th row of X m ,
and by X m i,q its q-th element. It appears that every auto-and crosscorrelation value between two sequences of {x m } is reduced to a scalar product of some vectors X m i . These values are contained in the matrix R = XX H of order M (2N -1).

If necessary, a weighted version of the row vectors may be considered, by defining the following matrix:

Xm i := X m i √ w i i ∈ 1, 2N -1 and m ∈ 1, M (12)
where the weights w i satisfies the weighting condition [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF]. The associated matrices R and

X ∈ C [M (2N -1)]×[2N -1] are therefore expressed by: R = X XH with X =      X1 X2 . . . XM      . ( 13
)
In the particular case where the weights w i are non zero only for the first K values, the matrix R then contains only all auto-and cross-correlation values of the set up to the K-th lag. This matrix R satisfies the following lemma:

Lemma 1. (Upper Bound) Under the above-mentioned hypothesis, the Frobenius norm of the matrix R can be upperbounded by:

R 2 F ≤ M 2 θ 2 max + M 1 -θ 2 max 2N -1 i=1 w 2 i (14)
Proof. This result is similar to the lemma 1 of [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF], and is also obtained by a similar proof.

A lower bound on the squared Frobenius norm of R can also be computed.

Lemma 2. (Lower bound) Under the above-mentioned hypothesis, the Frobenius norm of the matrix R can be lowerbounded by:

R 2 F ≥ M 2 N 2 N - 2N -1 s,t=1 l s,t,N w s w t (15) with l s,t,N = min (|t -s|, 2N -1 -|t -s|)
Proof. See Appendix A. This proof mixes methods used by Welch and Levenshtein but, instead of using the Cauchy-Schwarz inequality, it exploits to some extent the particular structure provided by the aperiodic correlation and the constant modulus constraint. Besides, it removes the requirement of sequences over the roots of unity.

From these lemmas can then easily be deduced a lower bound on the PSL, akin to Levenshtein's proof : Theorem 1. For any set of M unimodular sequences of length N , and with any weight vector w that satisfies the weighting condition (5), a lower bound on the Peak-to-Sidelobe Level is given by:

θ 2 max ≥ 1 N 2       N - Q 2N -1 w, N (N -1) M 1 - 1 M 2N -1 i=1 w 2 i       with Q 2N -1 (w, a) = a 2N -1 i=1 w 2 i + 2N -1 s,t=1 l s,t,N w s w t l s,t,N = min(|s -t|, 2N -1 -|s -t|). (16)
Proof. Combining Lemma 1 and Lemma 2 yields the desired result (16).

This expression is identical to the Levenshtein bound, but it is proved here that it is still valid for any set of unimodular polyphase sequences -the Levenshtein bound was originally meant for binary sequences and those over the roots of unity. This suggests that any bound obtained from Levenshtein expression using a specific weight vector also holds for unimodular sequences. In particular, optimal weight vectors considered by Levenshtein [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF] and Liu [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF] do.

IV. IMPROVEMENT OVER THE EXISTING BOUNDS

Theorem 1 states that the Levenshtein bound is valid for any set of unimodular sequences. However, this lower bound does not take into account additional information that can be extracted from the specific structure of aperiodic auto-and cross-correlations for a unimodular sequence, e.g., the last delay satisfies:

|θ x l ,x m (k)| 2 = 1/N 2 , for |k| = N -1, ∀(l, m), (17)
and, using the Cauchy-Schwarz inequality, the d-th last delay satisfies (for d ∈ 1, N and d = N if l = m):

|θ x l ,x m (k)| 2 ≤ (d/N ) 2 for |k| = N -d, ∀(l, m). ( 18
)
These properties have already been exploited in [START_REF] Boche | Estimation of deviations between the aperiodic and periodic correlation functions of polyphase sequences in vicinity of the zero shift[END_REF], but in another context (an estimation of a gap between an aperiodic lower bound and a periodic one). Here, they enable to provide a new upper bound, as stated in the following lemma:

Lemma 3. (Upper Bound considering the D last delays) R 2 F ≤ M 2 θ 2 max + M 1 -θ 2 max 2N -1 i=1 w 2 i (19) - D d=1     M 2 θ 2 max - d 2 N 2 2N -1 i,j=1 l i,j,N =N -d w i w j     .
Proof. See appendix C.

Clearly for D = 0, this upper bound is equal to the Levenshtein upper bound provided in Lemma 1. But it can be proved to be tighter if it satisfies the following property:

∃ (w i , w j ) s.t. 2N -1 i,j=1 l i,j,N =N -d w i w j = 0 with θ 2 max ≥ d 2 N 2 . ( 20
)
Minimizing the right-hand-side of (19) with respect to Ddenote the optimum by D opt -insures to provide an upper bound at least equal or tighter than the Levenshtein bound. This in turn enables us to determine a more general bound on the aperiodic correlation that takes into account the additional information on the D last delays of the auto-and crosscorrelation. This bound is provided in the following theorem, with the help of matrices A d and L such that:

               2N -1 i,j=1 l i,j,N =N -d w i w j = w T A d w, 2N -1 s,t=1
l s,t,N w s w t = w T Lw.

L =       0 1 2 2 1 1 0 1 2 2 2 1 0 1 2 2 2 1 0 1 1 2 2 1 0       = circ [0, 1, 2, 2, 1] T . ( 22
)
As A d matrices are related :

(A d ) i,j = 1 if L i,j = N -d, 0 otherwise, (23)
it comes that :

A 1 = circ([0, 0, 1, 1, 0] T ), A 2 = circ([0, 1, 0, 0, 1] T ). (24)
Theorem 2. For any set of M unimodular sequences of length N , and any weight vector w that satisfies the weighting condition ( 5), a lower bound on the Peak-to-Sidelobe Level is given by:

θ 2 max ≥ max D 1 N 2      N - Q w, N (N -1) M , D d=1 (d 2 -N )A d 1 -w T 1 M I + D d=1 A d w      with Q (w, a, B) = w T (aI + B + L) w.
Proof. This expression is directly obtained by combining the upper bound (19) and the lower bound provided by Lemma 2.

Since this new lower bound on aperiodic correlation has been obtained with a single change -on the upper bound of R 2 F , while keeping the lower bound -it implies that if there exists a value D for which the upper bound (19) is tighter than the one provided by Lemma 1 -for a given weight vector w -that satisfies (20), then the resulting lower bound on aperiodic correlation provided by Theorem 2 is also tighter than the Levenshtein bound for the same weight vector.

Corollary 1. Let the Levenshtein bound be denoted by B Lev for given M and N , and a given weight vector w. If there exists d such that w satisfies (20) and B Lev ≥ d 2 /N 2 , then the bound provided by Theorem 2 is tighter than the Levenshtein bound for the same w.

Corollary 1 presents a sufficient condition on the value d in order to get a tighter bound than Levenshtein's. If such a value exists, and if the aforementioned conditions are verified, it implies the following :

B Lev ≥ d 2 N 2 =⇒ d ∈ 0, N B Lev , (25)
where • denotes the floor function. In other words, each value that lies in this interval assures a tighter bound. One of these values, denoted D max , provides the tightest: a rough approximation of it is the maximum value d for which

B Lev ≥ d 2 /N 2 , i.e. D max ≈ N √ B Lev .
However, note that the previous cited interval does not include all the values of interest (see Figure 1 for instance).

As explained in [START_REF] Liu | Meeting the Levenshtein Bound with Equality by Weighted-Correlation Complementary Set[END_REF], an open question remains on the search for set of sequences that achieve the Levenshtein bound. At this point, a first partially negative answer can be given, thanks to Corollary 1. If the latter can indeed be applied, the Levenshtein bound is proved not to be the tightest, meaning that it cannot logically be reached by any set. We will see thereafter that it is the case for instance for M = 2, 3 or 4. The bound provided by Theorem 2 depends on several parameters, such as the number of sequences M and their length N , but also on the choice of the weight vector w and the number of considered delays D. Several results have been given in the literature according to the number of sequences M [5], [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF], [START_REF] Liu | Quadratic weight vector for tighter aperiodic levenshtein bound[END_REF]. This section studies the behaviour of this new bound, according to this criterion. In particular, we will show here that the proposed bound is tighter than the Welch bound in the case M = 2 -an achievement that is not possible with the Levenshtein bound -and tighter than the (up-to-now) tightest Levenshtein bound in the case M = 3 and M = 4.

A. M = 2 case

It has been proved that the tightest Levenshtein bound is obtained with constant weight vectors w i = 1/(2N -1) for i = 1, . . . , 2N -1 [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF]. In this case, the Levenshtein bound is equivalent to the Welch bound, and:

B Welch = 1 4N -3 . (26)
However, this weight vector clearly satisfies Condition (20). It means that there exists d ≥ 1 (for instance, d = 1 works) such that B Welch ≥ d 2 /N 2 for N ≥ 3. Applying Corollary 1 thus proves that the proposed bound is tighter than the Welch bound for M = 2, an improvement that cannot be achieved by the Levenshtein bound. An explicit expression of this bound is:

θ 2 max ≥ 1 3N 2 3M N 2 -3N 2 -M D(D + 1)(2D + 1) M (2N -2D -1) -1 , (27)
and the corresponding proof is given in Appendix D. Fig. 1 shows the behaviour of the proposed bound with M = 2 and N = 1000 according to D. A better bound, compared to the Welch bound, is observed considering 1 to 25 delays, while the optimal bound is achieved with D max = 15. As above-mentioned, this value can be approximately computed:

15 2 N 2 ≈ 2, 25.10 -4 < B Welch ≈ 2, 5.10 -4 < 16 2 N 2 ≈ 2, 56.10 -4 .

B. M = 3 and M = 4 cases

As shown by Liu et al. in [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF], the "Positive-Cycle-ofa-Sine-Wave" weight vector leads to the up-to-now tightest Levenshtein bound for M ≥ 3, N ≥ 3 and M ≥ 4, N ≥ 2 (which is in particular also tighter than the Welch bound). These weights are defined by (with K ∈ 2, 2N -1 ):

w i =    tan π 2K sin π(i -1) K 0 if i ∈ 1, K , otherwise.
(28) Using these weights, the associated bound, defined in [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF], reaches its maximum for a certain value of K, denoted K opt . Actually, it is possible to show that our bound is even tighter, using again Corollary 1 with the "Positive-Cycle-of-a-Sine-Wave" weights. In turn, to prove that Corollary 1 is satisfied in that case, it is sufficient to check that K opt is greater than N , which directly implies Condition (20).

As defined in [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF], the Levenshtein bound using Liu's weight is given by:

B(K) = 1 N 2 N - (N -1)N -M 2 K tan 2 ( π 2K ) + M K 2 2M -K tan 2 ( π 2K ) (29) for K ∈ 2, N (its expression is different for K > N
and is given in [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF]). It can be shown that this bound is an increasing function of K on its definition interval, for M = 3 and M = 4. Therefore, K opt is necessarily greater or equal to N so that Condition (20) is satisfied and Corollary 1 can be applied. However, further analysis should be performed to draw a conclusion for M ≥ 5, as the optimum value K opt may be smaller than N . Fig. 2 compares the Levenshtein bound, the proposed bound -both with Liu's weight [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF] -and the Welch bound, as functions of K, in the case M = 3. The number of delays to consider in the computation of our proposed bound was estimated with the maximum value of D for which B Liu ≥ D 2 /N 2 . In this figure is found again that optimal value K opt is indeed greater than the length of the sequences. Table II gives some values of these bounds, according to several sequence lengths N . The case M = 4 is quite similar. According to the application, it may be needed to consider every delay, i.e., K = 2N -1. In that case, Liu et al. have also developed another weight vector [START_REF] Liu | Asymptotically Locally Optimal Weight Vector Design for a Tighter Correlation Lower Bound of Quasi-Complementary Sequence Sets[END_REF] :

w i = 1 2N -1     1 + cos 2π(i + q) 2N -1 cos π 2N -1     , i ∈ 1, 2N -1 , (30)
for any integer q. Fig. 2 also compares the Levenshtein bound and the proposed one with these weights. The "Positive-Cycle-of-a-Sine-Wave" still provides a better global bound with a wise selection of the parameter K but, if all delays are considered, tide is turned. That is a not-so-surprising result, as that weight has been precisely defined for that case. That said, the proposed bound remains tighter than Levenshtein's, whatever weights.

VI. CONCLUSION

Two contributions have been given in this paper.

• A generalization of the Levenshtein bound. While Levenshtein [START_REF] Levenshtein | New lower bounds on aperiodic crosscorrelation of binary codes[END_REF] and Boztas ¸ [START_REF] Liu | Quadratic weight vector for tighter aperiodic levenshtein bound[END_REF] have proved its validity to a set of binary sequences and over the roots of unity respectively, this article showed that it also holds for a set of unimodular sequences. • An improvement of the Levenshtein bound. This improvement has been obtained by taking into account additional informations that can be extracted from the specific structure of the aperiodic auto-and cross-correlation sequences, and more precisely by refining the upper bound using the D last delays. It allows to tighten the existing Levenshtein bound for M = 2, M = 3 and M = 4. • Some work remains on the case M ≥ 5. Actually, the Levenshtein bound has been tightened, but in a negligible and an unnoticeable way. However, any (yet to be found) weight that will improve the Levenshtein bound in that case will also improve the present one. • In any case, it is worth insisting on the fact that any weight vector that satisfies Corollary 1 gives a Levenshtein bound that can be tightened by Theorem 2. In practical cases, this bound can easily be extended considering some constraints on the spectrum, the mainlobe width, etc. Levenshtein, Liu's weight [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF] Maximum Levenshtein, Liu's weight [START_REF] Liu | Asymptotically Locally Optimal Weight Vector Design for a Tighter Correlation Lower Bound of Quasi-Complementary Sequence Sets[END_REF] Maximum Proposed, Liu's weight [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF] Maximum Proposed, Liu's weight [START_REF] Liu | Asymptotically Locally Optimal Weight Vector Design for a Tighter Correlation Lower Bound of Quasi-Complementary Sequence Sets[END_REF] Maximum Welch Fig. 2. Comparison of the Levenshtein bound and the proposed bound, both using Liu's weights [START_REF] Liu | A new weight vector for a tighter Levenshtein bound on aperiodic correlation[END_REF], [START_REF] Liu | Asymptotically Locally Optimal Weight Vector Design for a Tighter Correlation Lower Bound of Quasi-Complementary Sequence Sets[END_REF], M = 3 APPENDIX A PROOF OF THE LOWER BOUND OF R 2 F R can be developed and lower-bounded as:

R 2 F = X XH 2 F = XH X 2 F = 2N -1 k,k =1 M m=1 2N -1 i=1 X m i,k X m i,k * w i 2 ≥ 2N -1 k=1 M m=1 2N -1 i=1 |X m i,k | 2 w i 2 (31)
where the last inequality is obtained by removing all terms k = k in the first summation. By construction, the structure of the different X m are similar. Thus, using the constant modulus property, it comes that

|X m i,k | 2 = |X l i,k | 2 for any l, m, i, k (|X m i,k | 2 can
only be equal to 0 or 1/N ). Inserting this into previous inequality, we obtain:

R 2 F ≥ M 2 2N -1 k=1 2N -1 i=1 |X m i,k | 2 w i 2 . ( 32
)
At that step, both Welch's and Levenshtein's proofs use the Cauchy-Schwarz inequality. We do not resort to this inequality here but rather exploit the specific structure of the matrix X m in the case of aperiodic correlations. Indeed, it appears, for each column k, that there are exactly N entries X m i,k that are non zero. Exploiting this structure and the fact that the square modulus of the non zero entries is equal to 1/N , it directly comes the following.

2N -1 i=1 |X m i,k | 2 w i =              k i=1 w i /N + 2N -1 i=N +k w i /N if k ≤ N -1 k i=k-N +1 w i /N if k ≥ N (33)
Including these expressions in (32) gives:

R 2 F ≥ M 2 N 2   N -1 k=1 k i=1 w i + 2N -1 i=N +k w i 2 + 2N -1 k=N k i=k-N +1 w i 2   . (34)
It is possible to show that the right hand side is equal to (cf. Appendix B):

N -1 k=1 k i=1 w i + 2N -1 i=N +k w i 2 + 2N -1 k=N k i=k-N +1 w i 2 = 2N -1 s,t=1 (N -l s,t,N )w s w t (35)
with l s,t,N = min(|t -s|, 2N -1 -|t -s|).

Accordingly, the lower bound of R 2 F is given by:

R 2 F ≥ M 2 N 2 N - 2N -1 s,t=1
l s,t,N w s w t .

APPENDIX B PROOF OF EQUALITY (35) This appendix details the proof of Equality (35). Its left hand side can be developed as:

N -1 k=1 k i=1 w i + 2N -1 i=N +k w i 2 + 2N -1 k=N k i=k-N +1 w i 2 = 2 N -1 k=1 k s=1 2N -1 t=N +k w s w t + N -1 k=1 2N -1 i=N +k w i 2 + 2N -1 k=1   k i=max(1,k-N +1) w i   2 (37)
where this last expression is obtained by observing that:

k i=1 w i = k i=κ w i for k ∈ 1, N -1 , (38)
with κ = max(1, k -N + 1). Let us set w = {w i } 2N -1 i=1
and M s2,t2 s1,t1 the (2N -1)×(2N -1) matrix such that the submatrix of row index s 1 ≤ i ≤ s 2 and of column index t 1 ≤ j ≤ t 2 is a matrix of ones while the other entries are null:

M s2,t2 s1,t1 =                        0 • • • • • • 0 0 • • • 0 0 • • • 0 . . . . . . . . . . . . . . . . . . 0 • • • • • • 0 0 • • • 0 0 • • • 0 0 • • • • • • 0 1 • • • 1 0 • • • 0 . . . .
0 • • • • • • 0 1 • • • 1 0 • • • 0 0 • • • • • • 0 0 • • • 0 0 • • • 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 • • • • • • 0 0 • • • 0 0 • • • 0                        ← s 1 ← s 2 ↑ ↑ t 1 t 2 (39
) With such a matrix, we have:

s2 s=s1 t2 t=t1 w s w t = w T M s2,t2 s1,t1 w, (40)
so that each term of (37) may be written with some matrices M t1,t2 s1,s2 :

2N -1 k=1 k i=κ w i 2 = w T 2N -1 k=1 M k,k κ,κ w, N -1 k=1 2N -1 i=N +k w i 2 = w T N -1 k=1 M 2N -1,2N -1 N +k,N +k w, 2 N -1 k=1 k s=1 2N -1 t=N +k w s w t = w T N -1 k=1 M k,2N -1 1,N +k + M 2N -1,k N +k,1 . w. (41)
It can be observed first that:

2N -1 k=1 M k,k κ,κ =   M 1 M T 2 M 2 M 3   , (42)
where M 1 is an N ×N Toeplitz matrix with generating vector

[N, N -1, • • • , • • • , 1], M 2
is a (N -1) × N matrix given by:

M 2 =           0 1 2 • • • N -1 . . . . . . . . . . . . . . . . . . . . . 2 0 • • • • • • 0 1           , (43)
and M 3 is a (N -1) × (N -1) matrix given by:

M 3 =                   N -1 N -2 • • • 2 1 N -2 N -2 . . . . . . . . . . . . . . . . . . 2 • • • • • • 2 . . . 1 • • • • • • • • • 1                   , (44)
second that:

N -1 k=1 M 2N -1,2N -1 N +k,N +k =   0 N,N 0 N,N -1 0 N -1,N M 4   , (45)
where M 4 is a (N -1) × (N -1) matrix given by:

M 4 =                   1 • • • • • • • • • 1 . . . 2 • • • • • • 2 . . . . . . . . . . . . . . . . . . N -2 N -2 1 2 • • • N -2 N -1                   , (46)
and third that:

N -1 k=1 M k,2N -1 1,N +k + M 2N -1,k N +k,1 =   0N-1,N-1 M2 M T 2 0N,N   . ( 47
)
The summation of these different matrices then easily provides a simple (2N -1)×(2N -1) Toeplitz matrix with the generating vector

[N, N -1, • • • , • • • , 2, 1, 1, 2, • • • , N -1],
and whose entry (s, t) is thus equal to N -l s,t,N with:

l s,t,N = min(|t -s|, 2N -1 -|t -s|). (48)
This then provides the wanted expression:

N -1 k=1 k i=1 w i + 2N -1 i=N +k w i 2 + 2N -1 k=N k i=k-N +1 w i 2 = 2N -1 s,t=1
(N -l s,t,N )w s w t .

( |θ x l ,x m (l i,j,N )| 2 w i w j .

(50)

R is a matrix of size M (2N -1) × M (2N -1). The energy constraint provides its diagonal coefficients:

|θ x m ,x m (0)| 2 = 1, ∀m ∈ 1, 2N -1 , (51)
while the aperiodic correlation satisfies:

|θ x l ,x m (i -j)| 2 ≤ d 2
N 2 when |i -j| = N -d ∀ (l, m).

(52) Using these properties, an upper bound of R 2 F may be obtained. Each term of R may be upper bounded by θ 2 max , except the ones that refer to the autocorrelations mainlobes (51) and the D-last delays (52). Hence,

R 2 F = M l,m=1 2N
w i w j + M 1 -θ 2 max 2N -1 i=1 w 2 i -M 2 θ 2 max - 1 N 2 2N -1
i,j=1 l i,j,N =N -1

w i w j -. . . -M 2 θ 2 max - D 2 N 2 2N -1
i,j=1 l i,j,N =N -1 w i w j .

(53) This proof can be concluded using the weighting condition (5): 27) for our proposed bound stated in Theorem 2, in the particular case of a constant weight vector w i := 1/(2N -1) for i ∈ 1, 2N -1 . Remind that for a generic weight vector w, the obtained PSL bound is:

θ 2 max ≥ 1 N 2      N - Q w, N (N -1) M , D d=1 (d 2 -N )A d 1 -w T 1 M I + D d=1 A d w     
(55) with Q (w, a, B) = w T (aI + B + L) w. We will detail the computation of the different terms involved in that expression.

Let us first consider the term w T Lw given by:

w T Lw = 2N -1 s,t=1 l s,t,N w s w t , (56)
with l s,t,N = min(|t -s|, 2N -1 -|t -s|). As already mentioned, the matrix L is circulant :

L = circ [0, 1, . . . , N -1, N -1, . . . , 1] T . (57)
With constant weights, it can be seen that:

w T Lw = 1 (2N -1) 2 2N -1 s,t=1
L s,t .

(58)

The particular structure of the matrix L gives us the following development: (60)

w T Lw = 1 (2N -
From this calculation, it also comes straightforwardly that: Putting all these results together gives rise to the following bound:

θ 2 max ≥ 1 3N 2 3M N 2 -3N 2 -M D(D + 1)(2D + 1) M (2N -2D -1) -1 . (63)

  Clarification example : Set N = 3. The matrix L is of size 5 × 5 (2N -1 × 2N -1 in fact) and is defined as follows :

Fig. 1 .

 1 Fig. 1. Proposed bound versus last delays D

3

 3 Number of considered correlations KBound level (dB)

  us develop the Frobenius norm of R:

≤ M 2 θ 2 max

 2 |θ x l ,x m (l i,j,N )| 2 w i w j

R 2 F ≤ M 2 θ 2 max + M 1 -θ 2 max

 2212 l i,j,N =N -d w i w j . (54) APPENDIX D APPLICATIONS WITH A CONSTANT WEIGHT VECTOR In this appendix are developed the calculations enabling to obtain equation (

  now w T A d w:w T A d w = i,j=1 l i,j,N =N -d w i w j

ACKNOWLEDGEMENT

This work is partly supported by a DGA-MRIS scholarship. The authors would like to thank the reviewers and the IEEE associated editor for their comments and advice, and also F. Lehmann and J.-P. Ovarlez for their help.


Eitan Altman
email: eitan.altman@inria.fr

Said Boularouk

Josselin Didier
email: didier.josselin@univ-avignon.fr

Constrained Markov Decision Processes with Total Expected Cost Criteria

We study in this paper a multiobjective dynamic programmming where all the criteria are in the form of total expected sum of costs till absorption in some set of states M. We assume that instantaneous costs are strictly positive and make no assumption on the ergodic structure of the Markov Decision Process. Our main result is to extend the linear program solution approach that was previously derived for transient CMDPs (Constrained Markov Decision Processes) to general ergodic structure. Several (additive) cost metrics are defined and (possibly randomized) routing policies are sought which minimize one of the costs subject to constraints over the other objectives.

INTRODUCTION

When one has to select a path between a source S and a destination R, one often has several criteria. In road traffic problems it may be the minimization of the delay as well as the tolls. In communication networks it may be the minimization of delays, of loss probabilities of packets, of blocking probabilities of calls or of starvation probabilities in streeming video traffic. This motivates us to study the more general framework of CMDPs (Constrained Markov Decision Processes) which can be solved by transforming it to a linear program. The existing theory for solving such problems requires strong assumptions on the ergodic structure of the problem. In particular, for the shortest path multiobjective problem these conditions translate to a restrictive condition on the topology of the graph which fails to hold if there are cycles in the network. Our contribution is to extend existing solution methods to our multiobjective CMDP.

MODEL

Constrained Markov decision process (CMDP) A CMDP is described by the following objects. There is a set X of states which we asssume to be finite, a finite set A(x) of actions available at state x, a set of transition probabilities {Px,a,y}, where x, y ∈ X, a ∈ A(x). Px,a,y denotes the probability to move from state x to state y if action a is chosen at state x.

We consider K+1 cost criteria where one cost criterion, C, will be minimized subject to constraints on the other costs VALUETOOLS 2019 Palma de Mallorca, Spain Copyright is held by author/owner(s). D1, ..., DK of the form D k (u) ≤ W k where W k are given constants.

Instantaneous costs In order to define the costs we first introduce the instantaneous costs c and d k , k = 1, ..., K where c and d k are each strictly positive functions of the state-and action.

Histories and Policies. Define hn = (x0, a0, x1, a1, ..., xn-1, an-1, xn) to be a history of length n + 1 where a k ∈ A(x k ). A policy u is a sequence (u0, u1, ...) where um(•|hm) is a probability measure over the action set A(xm) conditioned on the observed history hm. Define the class of stationary policies: w is a stationary policy if the dependence of w k on the history h k is only through the current state x k . Under a stationary policy w, the state process is a Markov chain with a transition probability matrix P (w) satisfying

Pxy(w) = a w(a|x)Pxay
Each distribution β over the initial states x0 and policy u define a probability measure P u β over the set of histories H. We denote by E u β the corresponding expectation operator. We shall use the notation Xn, An, Hn to denote the stochastic state process, the stochastic action process and the history stochastic process.

Cost criteria We consier in this paper the total expected cost till a set M of states is reached for the first time. More precisely, we assume that the set X of all states is the disjoint union of the two sets X and M. Let TM the time till some state within M is reached for the first time. The total expected costs till absorption in M are defined as

C(β, u) = E u β T M t=1 [c(Xt, At)] D k (β, u) = E u β T M t=1 [d k (Xt, At)]
We shall assume without loss of generality that the set M is absorbing, i.e. Pxay = 0 for all x ∈ M, a ∈ A(x) and y ∈ M. We further assume that c(x, a) = d k (x, a) = 0 for all x ∈ M, a ∈ A(x), k = 1, ..., K. We then have

C(β, u) = E u β ∞ t=1 [c(Xt, At)] , D k (β, u) = E u β ∞ t=1 [d k (Xt, At)]
For a stochastic matrix P and the set of states M, we de-fine by MP the Taboo matrix which is obtained by replacing in P the entries of each column x ∈ M with zeros.

OCCUPATION MEASURE

For any initial distribution β, any policy u, state x and set of actions A ∈ A(x) define

p u β (t, x, A) := P u β (Xt = x, At ∈ A, TM > t) f (β, u, x, A) = ∞ t=1 p u β (t; x, A)
and s(β, u, x) = f (β, u; x, A(x)). Define the following polyhedron Q(β) to be the set of non-negative measures over the set of state action pairs, that satisfy for all x ∈ X,

a∈A(x) ρ(x, a) = y∈X a∈A(x)
ρ(y, a)(Py,a,x1{x ∈ X }) + β(x).

(1)

MAIN RESULTS

Below we identify a linear program that allows to compute the optimal value and an optimal stationary policy for CMDP. A similar result was already available in [START_REF] Altman | Constrained Markov Decision Processes[END_REF] but required the strong assumption that s(β, u) is finite for any u. This excludes the shortest path problem in which policies that include cycles may have infinite cost. In order to handle such situations we note that one may assume throughout that c and d are uniformly bounded below by some positive constant c. The following Lemma shows that although we do not assume that all policies have finite occupation measures, those having infinite occupation measures are not optimal.

It further shows that one may restrict the search of solutions to CMDP to stationary policies. Proof.

(i) We have

C(β, u) = x,a c(x, a)f (β, u; x, a) ≥ c x s(β, u; x) = cE u β [TM]
where c := minx,ac(x, a). Thus if C(β, u) is finite then s(β, u) and f (β, u) are indeed finite measures. That f (β, u) satisfies (1) follows by noting that

p u β (t; x) = y,a p u β (t -1; y, a)Py,a,x1{x ∈ X }
and taking the sum over t.

(ii) See Lemma 7.1 (i) in p. 76 in [START_REF] Altman | Constrained Markov Decision Processes[END_REF]. Although the statement in that reference is for for transient MDPs, the proof does carry on to our framework.

Theorem 2. Choose any initial distribution β and policy u. Then either C(β, u) = ∞ or there exists a stationary policy w such that C(β, w) ≤ C(β, u),

Proof.
This is an extension of thm 8.1 in p.100 of [START_REF] Altman | Constrained Markov Decision Processes[END_REF]. Choose some policy u. Assume C(β, u) is finite. Consider a stationary policy w satisfying f (β, u; x, a) = s(β, u; x)w(a|x). Note that f and s are finite measures otherwize C(β, u) would be infinite. It then follows that s(β, u; x) = β(x) + y∈X s(β, u; y)MPyx(w). see the derivation of eq 8.6 page 102 in [START_REF] Altman | Constrained Markov Decision Processes[END_REF]. Note that in [START_REF] Altman | Constrained Markov Decision Processes[END_REF], s(β, u; x) is finite for all β, u and x but eq. 8.6 in [START_REF] Altman | Constrained Markov Decision Processes[END_REF] holds also in our framework. Hence by Lemma 1, for all x, s(β, w; x) ≤ s(β, u; x). Thus f (β, w; x, a) ≤ f (β, u; x, a) for all state action pairs x, a. As the costs c and d are strictly positive, we conclude that

C(β, u) =
D k (ρ) :=< ρ, d k >≤ W k , k = 1, ..., K, ρ ∈ Q(β)
where Q(β) is defined in (1).

Theorem 3. (i) To each policy u ∈ U in CMDP there corresponds a point ρ(u) := f (β, u) in Q(β) whose corresponding costs are the same:

C(β, u) = C(ρ), D(β, u) = D(ρ). (3)
(ii) Conversely, for each ρ ∈ Q(β), there corresponds a stationary policy w(ρ) whose performance is at least as good as the one of ρ. More precisely, select a stationary policy w(ρ) so that w ρ * (a|y) = ρ(y, a)

a ∈A(y) ρ(y, a )

for all y for which the denominator is finite and strictly positive. Then C(β, w(ρ)) ≤ C(ρ), D(β, w(ρ)) ≤ D(ρ).

(iii) The optimal value C(β) of CMDP is equal to the optimal value C * of LP(β). Let ρ * be an optimal solution of LP(β). Then the stationary policy w ρ * given in eq. ( 4) is optimal for CMDP.

Proof.

(i) From Lemma 1 (i) it follows that either C(β, u) is infinite, or f (β, u) satisfies (1) and hence is in Q(β). in both cases (3) holds. (ii) follpws from Lemma 1 (ii). (iii) We may assume that there exists a policy u such that D k (u) ≤ W k and C(u) is finite, otherwise the statement is trivial. The statement follows then from (i) and (ii) of the Theorem.

Lemma 1 .

 1 (i) Fix some initial distribution β and a policy u. Then either C(β, u) is infinite or f (β, u) satisfies (1) and both f (β, u) and s(β, u) are finite measures. (ii) Fix some initial distribution β and a stationary policy w. Then s(β, w; x) is the minimal solution tor = β + rMP (w), r ≥ 0(2)(in matrix notation, where r and β are row vectors).

  y∈X a∈A(y) f (β, u; y, a)c(y, a) ≥ y∈X a∈A(y) f (β, w; y, a)c(y, a) = C(β, w) and similarly, D k (β, u) ≥ D k (w), k = 1, ..., K Consider the following LP: LP (β): Find the infimum C * of C(ρ) :=< ρ, c > over ρ subject to