Anastasia Bezerianos
email: anastasia.bezerianos@lri.fr.

Petra Isenberg 1 Fig

Perception of Visual Variables on Tiled Wall-Sized Displays for Information Visualization Applications

Keywords: Information Visualization, Perception, Wall Displays !

Two viewers analyzing data visualizations from different viewpoints in front of a large high-resolution wall display (a). A participant conducting a trial during our first experiment (b).

Abstract-We present the results of two user studies on the perception of visual variables on tiled high-resolution wall-sized displays. We contribute an understanding of, and indicators predicting how, large variations in viewing distances and viewing angles affect the accurate perception of angles, areas, and lengths. Our work, thus, helps visualization researchers with design considerations on how to create effective visualizations for these spaces. The first study showed that perception accuracy was impacted most when viewers were close to the wall but differently for each variable (Angle, Area, Length). Our second study examined the effect of perception when participants could move freely compared to when they had a static viewpoint. We found that a far but static viewpoint was as accurate but less time consuming than one that included free motion. Based on our findings, we recommend encouraging viewers to stand further back from the display when conducting perception estimation tasks. If tasks need to be conducted close to the wall display, important information should be placed directly in front of the viewer or above, and viewers should be provided with an estimation of the distortion effects predicted by our work-or encouraged to physically navigate the wall in specific ways to reduce judgement error.

INTRODUCTION

Mega-and Giga-pixel wall-sized displays (henceforth referred to as wall-sized displays) offer the opportunity to engulf viewers in very large high-resolution information spaces. They form intriguing new environments for data analysis and information visualization due to several inherent benefits: physical rather than virtual navigation affords a natural pan-and-zoom in the information space, an enlarged physical space in front of the display enables collaborative viewing and data analysis, and millions of pixels support viewing tremendous amounts of data in one shared environment [START_REF] Ball | Move to Improve: Promoting Physical Navigation to Increase User Performance with Large Displays[END_REF][START_REF] Endert | Visual Encodings that Support Physical Navigation on Large Displays[END_REF]. To fully leverage wall-sized displays for data analysis, however, we need to design wall-sized visualizations and workspaces based on a sound understanding of how human's perceptual and cognitive capabilities are affected by this new work environment. At the most basic level, visualization workspaces for wall displays have to incorporate what we already know about the design of information visualizations for desktop-sized displays. Beyond this knowledge, wall-specific design recommendations have to be developed. One important criterion for the development of information visualization techniques for wall-sized displays is their immense physical size. It is not uncommon to see wall displays of over 5m (16') × 2m (6.5') in width and height [START_REF] Beaudouin-Lafon | Lessons Learned from the WILD Room, a Multisurface Interactive Environment[END_REF][START_REF] Endert | Visual Encodings that Support Physical Navigation on Large Displays[END_REF]. Even complete rooms covered on all sides by high-resolution displays are being constructed for visualization research and applications [START_REF]Stony Brook University Receives NSF Grant to Design Revolutionary Reality Deck[END_REF].

With physically large display-walls, physical navigation becomes an important means of accessing an information visualization [START_REF] Ball | Move to Improve: Promoting Physical Navigation to Increase User Performance with Large Displays[END_REF][START_REF] Endert | Visual Encodings that Support Physical Navigation on Large Displays[END_REF][START_REF] Yost | The Perceptual Scalability of Visualization[END_REF]. Viewers choose close or far viewpoints to zoom in and out, and pan physically by moving left and right to see different parts of the display. This type of movement may involve a physical relocation as well as a change of head orientation, as depicted in Fig. 1. Thus, viewers fluidly and frequently switch viewing distances and angles which may lead to systematic discrepancies between the actual appearance of displayed information in physical space (as can be measured by rulers) and its psychophysical appearance in a person's visual space.

Understanding discrepancies and where and when they occur is important for information visualization design, as fundamental data analysis tasks involve the correct assessment and comparison of elementary visual variables such as areas, angles, positions, slopes, or lengths [START_REF] Cleveland | The Elements of Graphing Data[END_REF]. To read a bubble chart, for example, one has to compare the sizes of circles to one another and to a legend, as well as relate positions in a 2D coordinate space. Fig. 2 gives an example of how the appearance of three visual variables is affected when seen from different viewpoints and viewing angles. The question arises whether comparisons such as these are affected by the oblique viewing angles which occur when viewing data from different positions in front of a wall-sized display.

To-date many high-resolution wall-sized displays, including ours, are assembled from multiple LCD monitors [START_REF] Beaudouin-Lafon | Lessons Learned from the WILD Room, a Multisurface Interactive Environment[END_REF][START_REF] Endert | Visual Encodings that Support Physical Navigation on Large Displays[END_REF][START_REF]Stony Brook University Receives NSF Grant to Design Revolutionary Reality Deck[END_REF]. These setups include clear visible bezels which form part of our study context. The research we report on in this paper, thus, takes a first step towards assessing the implications of changes in viewpoint on the assessment of data representations on tiled wall-sized displays with visible bezels.

Our research is motivated by three main questions:

• Are all areas of a wall equally effective for close scrutiny and comparison of data items? • What is the effect of viewing distance and angle on the perception of visual variables in large viewing spaces? • What are the benefits of walking in comparison tasks?

We began addressing these questions by studying how perception of elementary visual variables (Angle, Area, Length) was affected by varying viewing distances and angles. We contribute two studies: the first assessed static viewing conditions and identified different parameters that can help predict the perceived magnitude of the tested visual variables. The second contributes an understanding of the influence of allowing participants to move in front of the display. Our final contribution is a set of design implications about placement of data items on wall displays and the characteristics of effective physical navigation.

RELATED WORK

We can draw from a variety of past research for the design of our experiments. A large chunk of the literature comes from the field of psychophysics. We report on the related background in this field separately in the following section as we lead into the study design. In this section, we concentrate on the related literature on large displays and perception of graphical elements in HCI and information visualization.

Viewpoints and Interaction with Large Displays

The problems of viewing and interacting with information on physically large displays has been investigated in HCI, focusing on several different questions: how to acquire targets across large distances [START_REF] Shoemaker | Shadow Reaching: A New Perspective on Interaction for Large Displays[END_REF], how to view far areas up-close [START_REF] Bezerianos | Using Alternative Views for Layout, Comparison and Context Switching Tasks in Wall Displays[END_REF], how to maintain awareness [START_REF] Bezerianos | Mnemonic Rendering: An Image-based Approach for Exposing Hidden Changes in Dynamic Displays[END_REF][START_REF] Khan | Spotlight: Directing Users' Attention on Large Displays[END_REF], how large displays influence performance in spatial orientation tasks [START_REF] Tan | With Similar Visual Angles, Larger Displays Improve Spatial Performance[END_REF], or how a larger field of view influences user performance [START_REF] Czerwinski | Women Take a Wider View[END_REF]. In contrast to these questions we want to learn how varying viewing distances and angles affect the accurate perception of a virtual object's properties such as its area, length, or angles. We know of no largedisplay literature that asks this question but the problem has already been recognized [START_REF] Andrews | Information Visualization on Large, High-resolution Displays: Issues, Challenges, and Opportunities[END_REF]. Several researchers have instead considered the influence of varying viewpoints on other large-display tasks:

Jota et al. [START_REF] Jota | A Comparison of Ray Pointing Techniques for Very Large Displays[END_REF] studied the impact of viewing angles on pointing performance on a 3m × 1m wall. Several studies in the tabletop literature assessed the relationship of view position and 2D object rotation on coordination, comprehension, and collaboration [START_REF] Kruger | Roles of Orientation in Tabletop Collaboration: Comprehension, Coordination and Communication[END_REF][START_REF] Kruger | Fluid Integration of Rotation and Translation[END_REF]. Viewpoints have also been studied for viewing 3D objects on tabletops [START_REF] Hancock | The Effects of Changing Projection Geometry on the Interpretation of 3D Orientation on Tabletops[END_REF]. In multi-display environments, Nacenta et al. [START_REF] Nacenta | E-conic: A Perspective-Aware Interface for Multi-Display Environments[END_REF] showed that dynamically correcting perspective based on a viewer's viewpoint improved performance for tasks such as targeting, steering, aligning, patternmatching, and reading. These studies relate to ours in that they corroborate the importance of view positions and angles to task performance.

Information Visualization and Large Displays

Several researchers have considered the influence of a viewer's position in front of a large display on information visualization tasks. For tabletops, Wigdor et al. [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] studied how varying screen orientation from a horizontal to up-right position influenced the accurate perception of elementary graphical elements. They found perception to be least accurate in the horizontal position. This study resembles ours in that elementary elements were tested using study techniques from psychophysics [START_REF] Goldstein | Sensation and Perception[END_REF]. We relate some of their findings more closely to ours in our Discussion Section. Alallah et al. [START_REF] Alallah | Oa-Gaphs: Orientation Agnostic Graphs for Improving the Legibility of Charts on Horizontal Displays[END_REF] tested how the perception of simple charts was impacted by varying viewing angles around a horizontal screen. They found that reading charts right-side up was fastest and least error-prone, and proposed a new chart design to alleviate orientation problems.

For wall-sized displays several studies explore how changes in a viewer's position affect how visualizations are read. Endert et al. [START_REF] Endert | Visual Encodings that Support Physical Navigation on Large Displays[END_REF] discuss how a viewer's distance from a large display influences the visual aggregation of displayed information. They found encodings based on a color ramp to visually aggregate particularly well across viewing distances for a visual search task. Yost and North [START_REF] Yost | The Perceptual Scalability of Visualization[END_REF] tested several data visualizations for their ability to effectively display large amounts of data on large displays. They found their visualizations to scale well for the tasks of finding detailed and overview information and note that spatial encoding of information was particularly important on large displays. In a follow-up experiment Yost et al. [START_REF] Yost | Beyond Visual Acuity: The Perceptual Scalability of Information Visualizations for Large Displays[END_REF] studied how scaling visualizations beyond visual acuity affected user performance. For almost all tested tasks they found performance improvements and argue for design guidelines that take visual aggregation and physical navigation into account. Ball and North [START_REF] Ball | The Effects of Peripheral Vision and Physical Navigation on Large Scale Visualization[END_REF] compared the benefits of added peripheral vision vs. physical navigation for large displays, and found that physical navigation influenced task performance while added peripheral vision did not. The authors further stress the importance of physical navigation for visualization tasks. The stream of research on physical navigation relates to ours as a strong motivation for studying the influence of changing viewpoints and angles on accurate perception of data representations.

BACKGROUND IN PSYCHOPHYSICS

Psychophysics is a sub-discipline of psychology that is concerned with measuring the relationships between perceived and actual properties of a visual object [START_REF] Goldstein | Sensation and Perception[END_REF][START_REF] Wagner | The Geometries of Visual Space[END_REF]. Much research in psychophysics is concerned with the study of spatial perception and the comparison of physical and visual space. Unfortunately no one model exists which clearly describes visual space and would allow us to predict how elementary graphical elements will be perceived in a variety of viewing conditions [START_REF] Wagner | The Geometries of Visual Space[END_REF]. While it has been proposed to model visual space using hyperbolic, euclidean, or other geometries, no single geometry has been shown to work under all viewing conditions. Instead, researchers have attempted to mathematically describe the differences between physical and perceived magnitude of objects as collected from user studies. One popular function describing this difference is Stevens' [START_REF] Stevens | Psychophysics[END_REF] power law: J = λ D α , with J = judged magnitude, D = actual magnitude, α = exponent, λ = scaling constant. It has been tested under varying conditions, and several values for α have been proposed for judging elementary graphical elements (visual variables) such as length, area, or position. Wagner [START_REF] Wagner | The Geometries of Visual Space[END_REF] gives a recent meta-analysis of 104 articles reporting 530 values for α collected under different conditions. No combination of conditions matched those of viewing elements on wallsized displays. The reported exponents can, thus, help us hypothesize but not predict how reading elementary graphical variables may be affected in our work environment. As no previous study matches our viewing conditions, we conducted our own experiments under conditions close to how one would work in front of a wall-sized display. Our conditions involved: binocular vision, eye movement, changing head positions and viewing distances, and a back-lit viewing surface.

Psychophysics has developed several methods to help assess a viewer's visual perception of an object and to, thus, compare its magnitude (e. g., size) in the physical space to its subjectively experienced magnitude in a person's perceived visual space. Methods include numeric estimation, magnitude production, and sensitivity measures [START_REF] Wagner | The Geometries of Visual Space[END_REF]. There is a debate as to which method is the best to measure the perceived magnitude of a given object. The methods of numeric estimation have been used in many experiments in the past (e. g., [START_REF] Cleveland | Graphical Perception and Graphical Methods for Analyzing Scientific Data[END_REF][START_REF] Goldstein | Sensation and Perception[END_REF][START_REF] Isenberg | A Study on Dual-Scale Data Charts[END_REF][START_REF] Wagner | The Geometries of Visual Space[END_REF][START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF]). In our experiment we chose to use a magnitude production methodology. Here observers are asked to match two types of perceptions. Participants are shown a "standard" modulus object and are asked to change the intensity of a second object (the stimulus) until it is perceived to be equivalent to the modulus. We chose a magnitude production methodology for our experiment as the comparison judgements it requires are extremely frequent in information visualization [START_REF] Gleicher | Visual Comparison for Information Visualization[END_REF]. We give additional justification in Section 4.

It is known that no exponent for Steven's law holds under all viewing conditions [START_REF] Wiest | Steven's Exponent for Psychophysical Scaling of Perceived, Remembered, and Inferred Distance[END_REF]. Given the large number of varying factors, none that matched our study setup in its entirety, we have to use average exponents for forming study hypotheses. Wagner [START_REF] Wagner | The Geometries of Visual Space[END_REF] reports the following average exponents for studies on perception tasks: 1.02 for position and length, 0.84 for area, and 0.76 for angle. These state that generally people's judgement for position and length is consistent with actual positions and lengths, while angles and areas are underestimated compared to their real sizes. It has further been investigated how the visual angle-the angle a viewed object creates on the retina-and viewing distance influences the perception of visual variables [START_REF] Foley | Depth, Size and Distance in Stereoscopic Vision[END_REF][START_REF] Levin | Visual Angle as a Determinant of Perceived Interobject Distance[END_REF]. In order to derive hypotheses from articles suggesting an influence, we calculated viewer-object distances and visual angles for distinct regions on our wall size display as can be seen in Fig. 3.

STUDY MOTIVATION

Given previous work we expect that locations with smallest visual angles (resulting from object size, position, and viewing distance) will result in larger visual distortion of the perceived visual variables. To understand the effect of different display locations and viewing distances in detail we conducted two magnitude production experiments.

In Experiment 1, our goal was to determine how different object positions and sizes affect perception, by asking participants to interactively decrease the magnitude of an object's visual variable to match the magnitude of another object's visual variable at another area in the display. This is motivated by the following scenario: People position themselves in front of information of interest to facilitate their tasks [START_REF] Ball | Move to Improve: Promoting Physical Navigation to Increase User Performance with Large Displays[END_REF][START_REF] Endert | Visual Encodings that Support Physical Navigation on Large Displays[END_REF]. When assessing information of interest, the data elements often have to be placed within their larger context, to determine how they compare to others (e. g., compared to a legend). Although viewers could walk to get a closer look at data and walk back, this type of interaction comes at a cost of efficiency, especially when data needs to be quickly compared. Furthermore, collaborative settings may require viewers to quickly achieve common ground by comparing what someone else is viewing. For these data analysis scenarios, it is unclear how the perception of informations is affected by different static P eye (x , h eye , 0) Q(x , y, d); a = P ob j P eye b = P ob j P eye q = P eye Q α = arctan( x q ) β = arctan( x+s q ) θ = αβ (a) Calculations for visual angle θ . viewer placements around the wall. In Experiment 1 we, thus, compare distortion across three visual variables (Angle, Area, Length) and try to determine if it is predictable. We attempt to characterize this effect and determine when quick comparisons from a stationary viewpoint, by turning one's head, are acceptable, and when the potential distortion errors are such that they require physical navigation or additional interface widgets to bring remote information closer. The goal of Experiment 2 was to investigate free movement as an alternative to static viewer placement. In contrast to Experiment 1, participants were allowed to move freely in front of the wall display. We were interested in the movement choices and strategies participants followed when allowed to walk, as well as time vs. accuracy trade-offs.

HYPOTHESES

From an assessment of the psychophysics and information visualization literature we derived a number of hypotheses for our experiments: H1: Accuracy results for visual variables follow those of previous work with lowest absolute error for Length, followed by Area, and Angle (upright) [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF]. H2: The nature of judgement errors will differ between different visual variables. Based on our visual angle calculations (Fig. 3) distant objects look smaller and the only depth cues available to viewers are bezels. We thus expect areas to be underestimated on average. Angles oriented towards the biggest axis of distortion (Fig. 2) will be overestimated: their line segments look smaller and they will seem more obtuse. As in previous studies [START_REF] Wagner | The Geometries of Visual Space[END_REF] lengths will correspond approximately to their actual sizes. H3: Accuracy decreases with growing distance between viewer and remote object. H3 contrasts H6 in Wigdor et al.'s study [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] that found no such effect, as we test much larger left-right distances. H4: Performance (accuracy and task time) decreases for close viewpoints as differences in visual angles are more extreme following H2 and the visual angle calculations in Fig. 3 that show smaller visual angles for remote objects. H5: The accuracy and nature of judgments of different visual variables is impacted differently for increasing object distances and viewing distances from the wall, but in a predictable way. H6: Accuracy increases when free movement is allowed, at a cost of temporal efficiency.

EXPERIMENT 1: STATIC COMPARISONS

Participants were placed at two fixed positions left-most in front of the wall. We chose left-most positions instead of centered ones as we expect results to be symmetric left and right and because we could test the most extreme distances. At each position participants were requested to engage in magnitude production tasks and interactively adjust the magnitude of an object's visual variable close to their location, to match the magnitude of the same variable on a remote modulus object. As a control condition, the two objects were occasionally drawn on the same screen. The works of Cleveland and McGill [START_REF] Cleveland | The Elements of Graphing Data[END_REF] and Wigdor et al. [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] differ slightly to ours as they used a magnitude estimation methodology. We followed this approach in an original pilot of 16 participants, but found that they tended to round their results to the closest 10%. This produced very noisy data and as a consequence results that were not accurate enough when attempting to predict perspective distortion. Thus, we decided on a magnitude production experiment that bypasses the mental conversion of a size to a number.

Apparatus

We used a 5.5m(18 ) × 1.8m(5.9 ), tiled wall-sized display consisting of 32 LCD screens of 2560×1600 resolution each. Screens are arranged as seen in Fig. 4 resulting in an effective resolution of 20480 x 6400 pixels, and are driven by a 18 workstation cluster. Software was written using the ZVTM toolkit with cluster extension [START_REF] Pietriga | Rapid Development of User Interfaces on Cluster-Driven Wall Displays with jBricks[END_REF]. Lights inside the experiment room were dimmed to reduce glare effects.

Factors

Our study included three main factors: visual variable, viewing distance from the wall, and modulus location and size.

Visual Variable

We used a subset of Cleveland's [START_REF] Cleveland | The Elements of Graphing Data[END_REF] elementary graphical perception tasks, namely assessing Length, Angle and Area as they are among the most highly ranked by Cleveland [START_REF] Cleveland | The Elements of Graphing Data[END_REF] and because we hypothesized them to be impacted by perspective changes. We did not test position, slope, and color for the following reasons. In our pilot study we tested position and found it to be largely unaffected by distortion. Furthermore, testing position is highly impacted by the presence of bezels, as positions can be easily compared within one single screen from a bezel onward. We thus decided not to include it in our final study to reduce time constraints on participants. Slope was not considered as previous work suggests a close relationship to angle judgments [START_REF] Cleveland | Graphical Perception and Graphical Methods for Analyzing Scientific Data[END_REF]. Finally, similar to Wigdor et al. [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF], color was not investigated, as color consistency across the wall is hard to achieve under differing viewing angles, creating a likely confound. This is especially true in our setup, as color perception is heavily influenced by the viewing angles of particular LCD models [START_REF] Harrison | A New Angle on Cheap LCDs: Making Positive Use of Optical Distortion[END_REF][START_REF] Kim | Enabling Concurrent Dual Views on Common LCD Screens[END_REF], and some viewing angles can even invert color perception.

The interactive object and the remote modulus were drawn with a distinct color of ∼ 81% intensity (#7FFFD4, #FFB6C1). The arms of the angles were of different length for modulus and stimulus in order to avoid participants making vertical length judgements on the angle's open side. Participants were informed about this choice. To minimize possible influences due to the presence of bezels [START_REF] Ball | Analysis of User Behavior on High-Resolution Tiled Displays[END_REF][START_REF] Bi | Effects of Interior Bezels of Tiled-Monitor Large Displays on Visual Search, Tunnel Steering, and Target Selection[END_REF], objects were drawn fully within a wall tile on a black background. For Length, objects were oriented horizontally. Angle judgements are known to be affected by angle orientation [START_REF] Wagner | The Geometries of Visual Space[END_REF] so we chose to keep a consistent Angle orientation that follows the axis of biggest distortion (the angle bisector was horizontal). In results reported by Wigdor et al. [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] this "upright" angle orientation lead to larger errors than an orientation rotated by 90º. Fig. 5 shows examples of how the interactive object and modulus were drawn if sharing the same screen.

Viewing Distance

Participants performed tasks at two distances from the wall: Distance-Close = 60cm(∼ 24 ) and DistanceFar= 320cm(∼ 126 ). Distance-Close is within the recommended range for desktop monitor viewing [START_REF] Fisher | The Force of Contraction of the Human Ciliary Muscle During Accommodation[END_REF]. We chose it because it affords viewing objects in great detail at regular monitor distance, as well as direct-touch interaction. Given a conservative number of 60º for the human visual field outward from the nose for each eye, DistanceFar was chosen so that viewers had the entire wall in view when looking straight at it. Fig. 4 gives an overview of the two viewing distances.

Modulus locations and sizes

We used 9 modulus locations, described in chess notation (Fig. 4). From the left we used columns A, E, and H and rows 1, 3, and 4 from the bottom. Given the height of our wall and the average height of our participants, location A3 was always parallel to the viewer's frontal plane and had the shortest viewing distance in both DistanceClose and DistanceFar (Fig. 3). We refer to A3 as the frontal screen.

For each visual variable, participants were presented with 6 modulus sizes (intensities/magnitudes) to produce. These were 10%, 20%, 30%, 40%, 60% and 70% of the initial size of the interactive stimulus for each visual variable. These initial stimulus sizes were always 180 o for Angle, 2560 pixels for Length (a single screen width), and 1280 pixels for the diameter of Area (half the screen width) respectively. We ensured that these initial sizes allowed the modulus to be visible in the smallest increments, while still be able to fit on the same screen as the interactive stimulus for the A3 frontal screen location condition. During each trial, the interactive stimulus had to be interactively reduced in size until it perceptually matched the remote modulus.

Participants and Procedure

Fifteen participants (5 female) took part in the study, recruited from our research institute. They were not paid for their involvement. Participants ranged from 24-33 years in age (mean & median age 29), 7 were students and 8 non-students with technical occupations. All participants reported normal or corrected-to-normal vision. Twelve participants reported experience with wall-sized displays in work tasks or games; the remaining 3 participants reported no previous experience.

Visual variable presentation order was randomized using a latin square. Presentation of modulus locations and sizes was also randomized, and their exact position within their screen location was varied between trials. Participants adjusted the size of the interactive object using the UP and DOWN arrow keys of a wireless keyboard on a stand in front of them. When the desired size was achieved they hit ENTER to terminate the trial. Before each trial started, the screens containing the stimulus and modulus were highlighted to ensure participants did not spend time on visual searches. Timing started once the stimulus and modulus appeared on the screen and stopped when ENTER was hit. After the study, participants filled out a questionnaire eliciting demographic information and subjective data on their performance and preference. Overall Experiment 1 consisted of:

EXPERIMENT 1 RESULTS

Metrics used in our analysis were Time, AbsErr and EstErr. We define AbsErr similarly to magnitude estimation studies [START_REF] Cleveland | Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods[END_REF][START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF]. AbsErr is the absolute percentage of estimation error over the real magnitude of the modulus object. Thus if participants report stimulus magnitude m u for a modulus of true magnitude m t , then AbsErr =| m u -m t m t * 100 |. This metric expresses the overall error in judgement (irrespective of over-or under-estimation tendencies). It is a skewed distribution, and as suggested by Cleveland [START_REF] Cleveland | Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods[END_REF], we conducted our analysis on its log variation log 2 ( 1 8 + AbsErr). Means reported are before normalization. EstErr represents the direction of estimation error, i. e. the tendency to over-or under-estimate the magnitude of the modulus and by how much. It is defined as EstErr = m u -m t m t * 100, with EstErr > 0 when magnitude is overestimated, and EstErr < 0 when underestimated.

Trials were marked as outliers when metrics were beyond two standard deviations from the mean for a given visual variable, viewing distance, size and location. 186 trials (3% of all trials) were identified as outliers and removed from further analysis. Similar to Cleveland and McGill [START_REF] Cleveland | Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods[END_REF] the remaining trials were aggregated per participant and factors for all sizes. All metrics followed the normal distribution. All analyses were performed using an ANOVA, and post-hoc pair-wise mean comparison p-values are adjusted using the Bonferroni criterion.

Results Across Visual Variables

We first analyzed effects across visual variables Area, Angle and Length and compared their performance.

Time (Fig. 6.a)

There was no significant effect of visual variable or location on time. Mean Time was longer for Angle (7.12 sec), followed by Length (6.6 sec) and Area (6.39 sec). There was a significant effect of viewing distance (F 1,14 = 17.3, p < .001). Tasks performed at DistanceClose took significantly longer than those at DistanceFar (all p < .05). AbsErr (Fig. 6.b) and EstErr (Fig. 7)

There was a significant effect of visual variable on AbsErr (F 2,28 = 95.2, p < .0001). Pair-wise comparisons showed that errors in judgement were significantly larger for Angle than all others (p < .001) with no other differences. Mean values for Angle (22%) were larger, followed by Area (13%) and Length (11%). Our ordering of visual variables according to accuracy is different than that reported by Cleveland [START_REF] Cleveland | Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods[END_REF] (where angles have smaller errors than areas), but similar to Wigdor [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] for upright angles. We examined this order separately when both objects were placed in frontal screen A3, to investigate if the effect was only present in remote location, but found this ordering to be present even on the frontal screen.

EstErr gives us the tendencies (direction) of estimation error. There was a significant effect for visual variable (F 2,28 = 25, p < .0001). Es-tErr was different for all visual variables (all p < .05), with the modulus being consistently overestimated, but by different amounts. Mean overestimation was significantly larger for Angle (19%), followed by Area (9%) and Length (4%).

The somewhat stronger differences of EstErr than AbsErr indicate that although the different visual variables were affected somewhat differently in terms of absolute magnitude, it is the tendencies to overand under-estimate that are different, with clear tendencies to overestimate in Angle but less consistent tendencies for Length and Area.

VIEWING DISTANCE: There was a significant effect of viewing distance on AbsErr (F 1,14 = 199.5, p < .0001), with less AbsErr in the DistanceFar condition (p < .001). There was no significant visual variable × viewing distance interaction, indicating accuracy did not vary differently for the different visual variables at different distances.

There was a significant effect of viewing distance on EstErr (F 1,14 = 73.5, p < .0001). Participants overestimated overall, with larger overestimations in DistanceClose than DistanceFar (p < .001). A significant viewing distance × visual variable interaction (F 2,28 = 34.5, p < .0001) indicates that the direction of error was affected differently by viewing distance for each of the visual variables. Pair-wise comparisons showed all visual variables to be different for Distance-Close (all p < .05) following the global trends described before. In Dis-tanceFar there was no difference between Length and Area, indicating Angle was overestimated significantly more even in the DistanceFar.

LOCATION: There was a significant effect of screen location on AbsErr (F 8,112 = 54.8, p < .0001). AbsErr increased with column distance (all reported effects p < .01): A1, A3, A4 had significant less Ab-sErr than all others, with no difference between screens in that column. Similarly AbsErr in the medium column E1, E3, E4 was significantly higher than the screens in A, and lower than remote screens in H. Finally the remote screens H1, H3, H4 had the largest AbsErr. There is, thus, a clear screen grouping across columns in terms of AbsErr.

The effects of direction of estimation are similar, with significant effect of screen location on EstErr (F 8,112 = 26.3, p < .0001). Overall participants overestimated, and overestimation increased with column distance A < E < H (Fig. 7). Overestimation on the column A1, A3, A4 was significantly less than all others, screens in the middle E1, E3, E4 had significantly larger EstErr than the first column, and significantly smaller EstErr than the two upper screens in the last column (all p < .05). We also observed a tendency (p < .1) for row 1 (lower screens) to have a lower average EstErr than the other screens in the same column.

Visual variabless were affected differently by location. There was a significant location × visual variable interaction on AbsErr (F 16,224 = 1.9, p < .01). Pair-wise comparisons (all p < .05) showed no difference between techniques in column A. Nevertheless the overall error of Angle increased compared to the others in the middle E and far column H. In E Angle has significantly larger AbsErr than Length, and in H larger than Area as well. No significant difference between Area and Length was found, nor significant effects depending on screen height.

The direction of error had clearer effects. There was a significant location × visual variable interaction on EstErr (F 16,224 = 30.2, p < .0001). Pair-wise comparisons (all p < .05) showed that Angle was overestimated more compared to other visual variables in most locations, but that this is not the case in screen A1 (lower screen close to the participant). In this location the estimation of Angle was significantly less than in all other screens for all visual variables (the inverse trend from all other locations). Moreover, Length which tends to have a small overestimation, had one of the largest overestimations in screen A1. In the middle column E, we found no difference between visual variable at the lower screen E1, although for the 2 higher screens Angle was significantly overestimated. In the far column H, all techniques were different at H3, H4. But again for the lower screen H1 effects were less pronounced, with only Angle being different from the others. The effects stem mainly from the DistanceClose condition (all p < .05), but similar trends appear in DistanceFar (p < .1).

In summary, the effects of the screen height seen in EstErr were not as strong in AbsErr, indicating that it was the tendencies to over-and under-estimate that changed with screen height, not the absolute error. SIZE: As in previous work [START_REF] Cleveland | Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods[END_REF][START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] we aggregated the results of different modulus sizes for the main analysis above. In a separate analysis, we also tested for effects of size (a separate factor of 6 possible values). We found a significant effect of size on AbsErr (F 5,70 = 12.1, p < .0001). Overall AbsErr decreased with the increase of object size, although only the two larger targets had significantly less AbsErr than other target sizes (p < .05).

A significant size × visual variable interaction (F 10,140 = 39.2, p < .0001) was also present. When looking at the effect of size on the different visual variables we found that for the four smaller sizes Angle had significantly larger AbsErr than all others, with no difference between visual variables for the 2 large sizes. Fig. 8 shows that (especially in DistanceClose) the AbsErr drops for larger sizes, with a difference in the amount of decrease between visual variables until there is little difference on larger object sizes.

Summary

Our analysis showed no significant difference between visual variables for task Time, but a difference for the two error metrics.

The absolute error follows the ordering reported by Wigdor et al. [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF], with Angle being the most error-prone and Length the least. Ab-sErr tends to increase when viewers are close to the screen, and when the distance to the remote object increases, with Angle being most affected. This last finding merits further discussion. An effect of stimulus-modulus distance was also reported by Cleveland [START_REF] Cleveland | Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods[END_REF], but Wigdor et al. [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] suggested that it may have been due to a possible confound in the original study. We discuss these findings in Section 9. We also found that the absolute estimation error decreased with the increase of object size. The rate of decrease was more steep for Angle (and somewhat less for Area), until errors were similar across visual variables for the largest object sizes.

The nature of over-or under-estimation was different per visual variable: Angle was consistently overestimated, except on screen A1, whereas Length and Area were less consistent in their tendencies (especially Length). The generally observed nature of overestimation was less pronounced in lower screens. Nevertheless, as we move upwards on the wall the overestimation becomes more pronounced for Angle followed by Area. Looking at the estimation averages for Angle and to a lesser degree Area (Fig. 7) the amount of overestimation is lowest in the lowest screens of the same column, whereas Length tended to be overestimated by a larger degree at lower screens, thus balancing EstErr across visual variables in these locations. This indicates that lower screens are perceived differently. Looking at horizontal screen location, Angle was affected the most, and Length the least, with estimates going up faster with horizontal distance.

Predicting Visual Variables

In the previous section we compared the visual variables. We now examine each visual variable in an attempt to predict their observed behavior for our study setup. More specifically we examine the effect of the different factors related to perceived magnitude PerMag (that is the participant's answer m u ) given the true magnitude m t . In our previous findings, effects were similar across rows or columns of the wall, thus we express screen location as a combination of column A, E, H (horizontal displacement), and row 1, 3, 4 (vertical displacement).

Results for Visual Variable: Angle

We found a significant effect of viewing distance (F 1,14 = 89.7, p < .0001), column (F 2,28 = 96.8, p < .0001) and row (F 2,28 = 65.5, p < .0001) on PerMag, as well as a significant viewing distance × column (F 2,28 = 81.5, p < .0001) and viewing distance × row (F 2,28 = 19.8, p < .0001) interaction. Pair-wise comparisons (all p < .05) showed that overestimation of Angle was significantly different between the three different columns, increasing with column distance. This effect was present both in DistanceClose and DistanceFar, although less pronounced in DistanceFar (all p < .05). For rows, the lower screens (row 1) always had significantly less overestimation, with no other differences. This effect was only present in DistanceClose, with no difference due to screen row in DistanceFar. There was also an effect of size on PerMag (F 5,70 = 1895.3, p < .0001), with all sizes being perceived differently (all p < .0001).

ANGLE PREDICTION Based on the above, we expect that the perceived Angle increases with the increase of the factors size, column and row, and decreases with the factor viewing distance. Indeed, we found a positive Pearson correlation between the dependent variable PerMag, the true object size (r = 0.943, n = 1620, p < .0001) and screen column (r = 0.161, n = 1620, p < .0001), and a negative correlation with viewing distance (r = -0.12, n = 1620, p < .0001). We found no significant correlation with row, but there was a clear trend (p = .07). No correlations were found between the predictor variables, indicating they are mutually independent. Thus we feel these factors are enough to predict the perceived angles. To verify this hypothesis for our setup, we ran a multiple linear regression analysis using the above factors. We obtained a very good fit for predicting the reported angles (R 2 = .93, Adjusted R 2 = .93). In our regression analysis we expressed viewing distance, column and row in cm, and the predicted and actual angles in angle degrees. Table 1 summarizes the coefficients that predict Angle in our setup.

Results for Visual Variable: Area

A significant effect of viewing distance (F 1,14 = 60.3, p < .0001), column (F 2,28 = 9.2, p < .01) and row (F 2,28 = 5.4, p < .01) on PerMag was present, and a significant viewing distance × column (F 2,28 = 28.4, p < .0001) interaction. Overestimation of Area was significantly different between the three different columns, increasing with column distance. The effect was due to the DistanceClose condition (all p < .05). For screen row, the lower screens (row 1) had significantly less overestimation than the higher ones, with no other differences (all p < .05). There was also an effect of size on PerMag (F 5,70 = 3847.4, p < .0001), with all sizes being perceived differently (all p < .0001).

AREA PREDICTION We expected that perceived Area will increase with increasing factors size, column and row and decrease when increasing viewing distance. Indeed, we found a positive Pearson correlation between the dependent variable PerMag, the actual size (r = 0.969, n = 1620, p < .0001) and column (r = 0.05, n = 1620, p < .05), and a negative correlation with viewing distance (r = -0.096, n = 1620, p < .0001). We found no significant correlation with row and no correlations between the predictor variables. Thus, these factors (excluding row) are enough to predict the perception of areas. To verify this hypothesis, we ran a multiple linear regression analysis using the above factors. We obtained a very good fit (R 2 = .925, Adjusted R 2 = .925), although column had a very small influence. In our analysis we expressed viewing distance and column in cm, and the predicted and actual areas in cm 2 . Table 1 summarizes the coefficients that predict Area in our setup.

Results for Visual Variable: Length

We found a significant effect of viewing distance (F 1,14 = 8.3, p < .05) and of row (F 2,28 = 6.7, p < .01) on PerMag. Results show that participants overestimated to a larger extend in DistanceClose. Moreover, objects in the lower screens (Row 1) were significantly overestimated compared to the other two rows (all p < .05). There was also a significant effect of size on PerMag (F 5,70 = 3953.6, p < .0001) with all sizes being significantly different.

LENGTH PREDICTION Given these results, we expect that the perceived Length increases with increasing size, and decreases with the increase of factors row and viewing distance. Nevertheless, a correlation analysis (over all factors), only shows a significant positive Pearson correlation between the dependent variable PerMag and the actual size (r = 0.971, n = 1620, p < .0001). Thus factor size should be enough to predict perceived lengths. To verify this hypothesis for our setup, we ran a linear regression analysis using size only as a factor. We obtained a very good fit (R 2 = .939, Adjusted R 2 = .939) for predicting the reported lengths. For our analysis we expressed the predicted and actual size in cm. We summarize the coefficients of the linear relationship that predicts lengths in our setup in Table 1.

Discussion on Prediction

We note that in our setup a linear relationship between size and the other factors is enough to provide a very accurate model of the perceived magnitudes. Even though perception of magnitude of visual variables follows a power low relationship with their true magnitude [START_REF] Wagner | The Geometries of Visual Space[END_REF], an initial curve fitting (per visual variables, and viewing distance) showed an almost linear relationship (α very close to 1). We believe this is due to the fairly small amount of sizes tested (6) compared to other perception studies. We expect that with an increase of sizes tested we will be able to observe such a power law behavior and further improve our model.

Although not reported, we tested visual angle and viewer-object distance (Fig. 3) as predictors of perceived magnitude. An inverse correlation was present (smaller visual angles lead to larger overestimation, larger viewer-object distances to smaller overestimation), but their influence is different at the two user distances. For example, Column E and H have similar visual angles at DistanceClose and DistanceFar, and Column H and E similar viewer-object distances (Fig. 3) but magnitude estimations were quite different (Fig. 7). Thus we feel the reported models are better predictors.

Questionnaire

We were further interested in the influence of the bezels. As we could not measure their influence directly, we asked participants for their strategies in solving the tasks and if they involved bezels. Thirteen participants reported to have used bezels, most of them for the Length task, but some noticed that bezels were only useful as landmarks for the larger sizes. It would be interesting to study the influence of bezels further in a dedicated experiment with the use of an eye-tracker.

EXPERIMENT 2: STATIC VS. MOVING

In Experiment 1 our goal was to understand and predict the effect of visual distortion while viewers stand at close and far locations in front of the wall display. We motivated this choice by scenarios in which viewers stand in specific locations conducting detailed tasks, and want to occasionally make quick visual comparisons with objects at distant locations (such as a comparison to a legend placed elsewhere). Nevertheless, we acknowledge that if the main task of the viewer is the comparison itself, they may decide to move in front of the wall to gain a better perspective of the information to compare. We, thus, conducted a follow-up study where participants were able to move freely, tracked using a Vicon motion capturing system (www.vicon.com).

Nine participants of the original study (3 female) took part in the second study a week later. Given that the stronger effects observed in our first study were in the farthest column, we only tested these locations (and the frontal screen A3) -4 locations overall. Participants started each trial close to the screen (as in DistanceClose) and were then able to move freely to perform their task. We analyzed these results with the results for DistanceClose and DistanceFar of our first study for the specific modulus locations.

Overview Strategy

Step-Back Strategy Target Strategy Wall Stimulus Modulus Fig. 9. Three participants' actual motion paths showing the three different types of moving strategies. We also illustrate possible modulus and stimulus locations and participants' viewing angles.

Overall Experiment 2 had:

Moving Strategy

Three moving strategies emerged during our experiment. Four participants adopted an overview strategy, walking to the center of the display at a far distance (∼ 3m), to observe both stimulus and modulus under a comparable visual angle in each direction. Three participants adopted a move to target strategy, walking until they arrived almost in front of the remote modulus. Finally, two participants performed a step-back strategy, moving slightly backwards from their original position (∼ 1m) to look at the remote modulus. Sample strategy profiles can be seen in Fig. 9. Participants tended to be consistent in their strategies throughout the experiment. We observed changes only in the target strategy, where towards the end of the experiment participants tended to stop partway ( ∼ 1m) before completely reaching the target. All participants performed tasks by first making an approximate judgement and then used walking to verify or adjust their initial judgement. All participants moved only once per trial.

AbsErr means were larger with the step-back strategy (20.4%), followed by the target strategy (11.1%), and with overview being the most accurate (9.5%). A Kruscal Wallis non-parametric test showed a significant effect of strategy on AbsErr (Chisquare(2) = 13.1, p < .01). Pair-wise comparisons showed that step-back was significantly more error phone than the others (all p < .001).

We also looked for learning effects between trials for each strategy, to see if participants' accuracy increased over time. Although we found no significant learning effect, when asked, five out of nine participants mentioned that after the end of the walking experiment they felt they could more accurately make estimations (even without walking). This leads us to believe that viewers can learn to self correct for visual distortion, a topic we plan to explore further in the future.

Static vs. Moving (Fig. 10)

ABSERR: There was a significant effect of viewing distance (F 2,16 = 18.2, p < .0001) and visual variable (F 2,16 = 9.2, p < .0001) on AbsErr, as well as a visual variable × viewing distance interaction (F 4,32 = 3.3, p < .05). Pair-wise comparisons (all p < .05) showed that AbsErr was significantly higher in DistanceClose (25%), with no difference between DistanceFar (12.6%) and ViewerMove(12.4%). Again, AbsErr was significantly higher for Angle (23%), followed by Area (14.5%), and Length (12.5%). This difference between visual variables was due to DistanceClose mainly, with no difference between visual variables in DistanceFar and ViewerMove (all p < .05).

TIME: There was a significant effect of viewing distance (F 2,16 = 10.3, p < .0001) on Time. Pair-wise comparisons (all p < .05) showed mean times to be significantly different between all viewing distances for the tested locations. DistanceFar was faster (6 sec), followed by DistanceClose (6.7 sec), and was almost double for ViewerMove (13.1 sec). Thus, the accuracy benefits for ViewerMove come with a time cost, while DistanceFar is both faster and has similar accuracy.

DISCUSSION

Our studies showed several interesting results in regards to our initial hypotheses. In H1 we had hypothesized that results would follow previous work [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] and rank visual variables with increasing absolute error for length, area and angle (upright). Since we chose an angle orientation that is proven to be very error prone [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF], our findings also follow this order, with angle being the most error prone visual variable (in all screens, including the frontal screen A3).

Based on previous work of Wagner who had conjectured that visual space was compressed in the in-depth dimension leading to angle overestimation [START_REF] Wagner | The Geometries of Visual Space[END_REF], we had hypothesized (H2) that angles would be overestimated. This was indeed the case. We had also hypothesized that areas would be underestimated. This was contrary to our findings, with areas being overestimated. A possible explanation comes from related work. Aks and Enns [START_REF] Aks | Visual Search for Size is Influenced by a Background Texture Gradient[END_REF] found that the addition of a grid to a scene of objects placed in 3D lead viewers to make object size corrections, hinting at a possibility that bezels may be used similarly. One of our participants accordingly stated "I compensated for my perspective." It is possible that our participants in an attempt to self-correct for perspective distortion did in fact self-correct too much. This effect was not as pronounced in length estimations and perhaps participants used bezels more successfully to estimate lengths than areas. Given participants' comments it is likely that results on length estimation may differ for a similar study on a seamless wall without bezels. Nevertheless results on angles and areas will most likely hold.

In H3 we hypothesized that the effects of H2 would increase with distance between stimulus and modulus. This was the case when participants were close to the wall, while the effect was less visible when they were far. The effect was present for both Angle and Area, and to a lesser extend for Length, confirming H3. In the work of Cleveland et al. [START_REF] Cleveland | Graphical Perception: Theory, Experimentation, and Application to the Development of Graphical Methods[END_REF] such an effect was observed as well, but not by Wigdor et al. [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF], where it was shown that left-right distances did not lead to increasing error. We showed that the effect exists, and it was most likely not observed in [START_REF] Wigdor | Perception of Elementary Graphical Elements in Tabletop and Multi-surface Environments[END_REF] because they tested much smaller left-right distances and, thus, differences in visual angles, than our Experiment 1.

We partially confirmed H4. Participants were slower when standing close to the wall, but not significantly so. For accuracy, we confirmed an increase in absolute error when standing close to the wall for all visual variables. In the questionnaire, all participants also reported that the tasks were easier to accomplish when standing far away.

In H5 we hypothesized that visual variables would be independently impacted by changes in viewing angle and distance but were less sure about the nature of the impact. Indeed we found very different behavior across visual variables. In general Angle was most impacted with highest inaccuracy. Although Angle judgments had a consistent overestimation tendency, estimations were smaller in the lower screens compared to other screens in the same column. Area had similar effects of increasing overestimation with left-right distance and a tendency for smaller estimations at lower screens, although the effects were mainly pronounced in DistanceClose. The judgements for Length were also affected by screen height, but in the inverse way. Length estimations that were on average closer to the real object values were overestimated in lower screens (an effect most visible in DistanceClose). Previous work in the physiology literature found a difference for visual activities in the upper-and lower visual fields [START_REF] Previc | Functional Specialization in the Lower and Upper Visual Fields in Humans: Its Ecological Origins and Neurophysiological Implications[END_REF], pointing to an interesting venue for further investigation for wall-sized displays.

Finally, in Experiment 2 we tested H6 related to walking, focusing on extreme distance and distortion conditions (last column on the wall). As expected, accuracy for estimations from a static position close to the wall was worse than when participants were allowed to move. However, we found no difference in perception accuracy between moving and standing on a static position far from the wall. Moreover, the task completion time was more than twice as long in the moving condition and participants complained about fatigue.

IMPLICATIONS FOR DESIGN

The results of our experiments apply to explicit comparison tasks that involve a quantitative comparison component [START_REF] Gleicher | Visual Comparison for Information Visualization[END_REF] such as finding similarities, differences and trends, spotting outliers, or acquiring a quick overview. One of the goals of our experiments was to derive design considerations for visualizations for wall-sized displays that require these tasks. Our main questions in regards to workspace design were:

Are all areas of a wall equally effective for close scrutiny and comparison of data items? Our analysis showed that indeed it is not recommended to compare data in certain screen locations as the error introduced reached as far as 157%/128%/110% overestimation for the three visual variables. We also found that lower screens tend to be somewhat unpredictable in their perception trends. We suggest that task-relevant data representations should not be placed at the lower positions on the wall. This is of importance to visualization designers, given that traditionally visual legends are placed at the bottom of visualizations and these legends often require visual comparisons (e. g., in a bubble chart the quantities represented by bubble sizes). Lower screens should be dedicated to widgets or contextual data that does not need to be reliably compared, such as visualization titles or numeric information about the data.

Should we redesign visualizations for walls for better comparison? When viewers were close to the wall, we found that judgement accuracy for Angle, and to a lesser degree Area, started to drop for targets placed as far way as half the wall width (∼ 3m). Length was least affected by screen position and distances. When magnitude comparison tasks are expected to be performed regularly close the wall (e. g., comparing pie or sector charts) we recommend not to design visualizations such that they require comparison across large distances (more than 3m), especially for Angle. Given the fairly predictable behavior of visual variables we were able to identify factors affecting them and to provide approximation models for their perceived sizes that fit our observed data very accurately. These models can be used by visualization designers to predict visual variable distortion and decide on acceptable distortion effects in their visualizations.

In our experiments we did not test every possible visual variable (for time reasons). The use of color intensity was previously recommended as being particularly stable across viewing distances for a visual search task [START_REF] Endert | Visual Encodings that Support Physical Navigation on Large Displays[END_REF]. Its effect for comparison tasks, however, will have to be further investigated. Yet, given the high influence of LCD screens' viewing angles on color perception [START_REF] Harrison | A New Angle on Cheap LCDs: Making Positive Use of Optical Distortion[END_REF][START_REF] Kim | Enabling Concurrent Dual Views on Common LCD Screens[END_REF] results may be difficult to generalize for other large wall setups.

How can we support data comparison at close viewing distances without visualization redesign? We generally found comparisons across long distances when standing close to the wall most error-prone. If physical movement in front of the wall is not possible (e. g., while interacting using direct-touch or multiple viewers are occupying the area in front of the wall) specific widgets could be designed to bring far information up-close [START_REF] Bezerianos | The Vacuum: Facilitating the Manipulation of Distant Objects[END_REF], enabling accurate comparisons with remote locations. Moreover, designers should provide additional aids to help viewers make judgements (e. g. use of tick marks, or value labels inside the visualization), that can act as guides much as the bezels did in our study. Alternatively, designers can use our prediction models to infer perceptual differences, and add additional meta-data on their visualizations about these calculations. At the very least viewers should be warned about distortion effects if designers deem comparison tasks important in their visualizations. For example a simple small text field could be added with a warning that "remote angles may appear twice as large" (similar to car mirror warnings for remote objects). Due to visual acuity these text fields could be made small to be only visible when needed, i. e. when viewers are close to the wall.

Should we encourage walking for comparison tasks? Using interactive widgets in comparison tasks comes with an interaction cost. An alternative is physical navigation, which is flexible and natural to viewers, but in turn comes with a time cost, as our findings indicate. More surprising was that the mean accuracy was not better when participants could walk compared to a static viewpoint far from the wall. Participants' walking strategies may offer an explanation: as walking is tiring, some participants walked minimally and were thus still affected by visual distortion, resulting in higher error rates. Thus, recommendations for walking need to be more specific. Viewers need to either move far from the wall (∼ 3m back), place themselves in the middle of the two objects to compare, or approach both objects to compare. Our models can be used to give viewers an approximate understanding of the distortion magnitude across the wall to help them decide when to make quick judgements turning their head, when to use interaction mediators to bring remote content closer to their focus of attention, or physically navigate. However, our discussion of walking guidelines is specific to quantitative comparison tasks. Physical navigation has been shown to be beneficial to other tasks such as zoomingin and -out to visually aggregate information [START_REF] Yost | Beyond Visual Acuity: The Perceptual Scalability of Information Visualizations for Large Displays[END_REF]). The tradeoffs with these benefits need to be further investigated.

CONCLUSIONS

We conducted two studies to understand distortion effects for information visualizations placed on large high-resolution wall-sized displays. In the first, we tested two static locations in front of the display and found that viewing distance from the wall, as well as horizontal and vertical placement, affected errors. Participants performed tasks better when the information was in full view, despite the fact that they stood further away from the display and the objects to compare were visually smaller. We tested three visual variables and found that length was relatively unaffected by changes in viewing distance and placement on the wall-but area and angle judgments were significantly affected. Moreover, performance on the lower locations of the display was found not to be consistent with other locations. Finally we proposed prediction indicators of how large variations in viewing distances and object placement affect the accurate perception of these visual variables.

In the second study, we examined the trade-offs involved when allowing viewers to walk. We found that-although moving was as accurate as static comparisons from afar-it took twice as long and viewers occasionally chose non-optimal moving strategies. Based on these findings we derived design considerations which recommend to encourage viewers to stand further back from the display when conducting quantitative comparison tasks. As such, we support previous recommendations for different data analysis tasks for wall-sized displays [START_REF] Andrews | Information Visualization on Large, High-resolution Displays: Issues, Challenges, and Opportunities[END_REF] that promoted physical navigation.

If tasks need to be conducted close to the wall display, however, viewers should either be encouraged to physically navigate the wall in specific ways to reduce judgement error, or important information should be placed directly in front of the viewer or above, and viewers should be provided with an estimation of the distortion effects predicted by our work.

  (a) The viewpoints of two observers. (b) Wall as seen by the left observer.(c) Wall as seen by the right observer.

Fig. 2 .

 2 Fig.2. Two observers looking at the same angles, lengths, and circles displayed across a large wall display.

  θ , v for d = 60cm and h eye = 160cm on our wall. θ , v for d = 320cm and h eye = 160cm on our wall. 1-8 8-16 16-23 23-30 30-38 38-45 45-53 53-60 (d) Heatmap legend for visual angle in Fig. 3(b) and 3(c).

Fig. 3 .

 3 Fig.3. Calculations of visual angles θ and viewer-object distance v (in cm) on our wall display. We tested screens with red borders in our study.

Fig. 4 .

 4 Fig. 4. The physical experiment setup showing the dimensions of our wall and modulus locations using chess notation (stimulus always in A3).

Fig. 5 .

 5 Fig. 5. Example screens showing the large interactive stimulus (green) the viewers adjusted to match the remote modulus (red) for Length, Area and Angle. The stimulus was always close to the participant's location.

Fig. 6 .

 6 Fig. 6. Time and Absolute error across all visual variables for Close and Far viewing distances.

  Length in DistanceFar. 88-96 96-104 104-112 112-120 120-128 128-136 136-144 144-152 152-160 (g) Legend for the heatmaps.

Fig. 7 .

 7 Fig. 7. Results for magnitude estimations (100+EstErr ) for each visual variable and viewing distance in Experiment 1. Values per screen indicate the percentage difference in average judgments for this modulus location. Values > 100% are overestimations and values < 100% underestimations. The frontal screen is highlighted with a red border.

Fig. 8 .

 8 Fig. 8. Absolute error across all visual variables for the 6 modulus (target) sizes tested, for Close and Far viewing distances.

Fig. 10 .

 10 Fig. 10. Absolute Errors and Times for visual variables in Experiment 2.

Table 1 .

 1 Regression analysis coefficients C. For our setup the perceived size can be predicted using the following equation PerMag = Constant + C mt * m t +C Distance * Distance +C screenX * ScreenX +C screenY * ScreenY .

		Perceived Size Magnitude Coefficients
		Angle (degrees)	Area (cm 2 )	Length (cm)
	Constant	4.286* (0.931)	0.022* (0.003) -3.124* (0.167)
	True Magnitude m t	0.977* (0.007)	1.027* (0.007)	0.944* (0.006)
	Viewing Distance (cm)	-0.35* (0.002)	-0.11* (0.001)
	Screen X (cm)	0.32* (0.001) 3.768•10 -5 * (0.000)
	Screen Y (cm)	0.3* (0.004)
	R-square	0.932	0.925	0.939
	Adjuster R-square	0.932	0.925	0.939
	Number of observations	1620	1620	1620
	Standard errors are reported in parentheses.
	* indicates significance at the 99% level.

ACKNOWLEDGEMENTS

We'd like to thank Jean-Daniel Fekete for his comments on an earlier draft of the paper, our reviewers and our study participants.


Victorin Martin

Jean-Marc Lasgouttes

Cyril Furtlehner

Local stability of Belief Propagation algorithm with multiple fixed points

A number of problems in statistical physics and computer science can be expressed as the computation of marginal probabilities over a Markov random field. Belief propagation, an iterative message-passing algorithm, computes exactly such marginals when the underlying graph is a tree. But it has gained its popularity as an efficient way to approximate them in the more general case, even if it can exhibits multiple fixed points and is not guaranteed to converge. In this paper, we express a new sufficient condition for local stability of a belief propagation fixed point in terms of the graph structure and the beliefs values at the fixed point. This gives credence to the usual understanding that Belief Propagation performs better on sparse graphs.

Introduction

We consider in this work a Markov random field (MRF) on a finite graph with local interactions, on which we want to compute marginal probabilities. The structure of the underlying model is described by a set of discrete variables x = {x i , i ∈ V} ∈ {1, . . . , q} V , where the set V of variables is linked together by so-called "factors" which are subsets a ⊂ V of variables. If F is this set of factors, we consider the set of probability measures of the form

p(x) = i∈V φ i (x i ) a∈F ψ a (x a ), (1)
where x a = {x i , i ∈ a}. In what follows, a factor will be indifferently considered as a node in a graph or as a set of variables. In this respect, i ∈ a ca be read as "the variable node i is connected to the factor node a." F together with V define the factor graph G [START_REF] Kschischang | Factor graphs and the sum-product algorithm[END_REF], which is an undirected bipartite graph. We will also assume that p is strictly positive, which is to say that the MRF exhibits no deterministic behavior. The set E of edges contains all the pairs (a, i) ∈ F × V such that i ∈ a. We denote d a (resp. d i ) the degree of the factor node a (resp. of the variable node i).

Exact procedures for computing marginal probabilities of p generally face an exponential complexity and one has to resort to approximate procedures. In computer science, the belief propagation (BP) algorithm [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Network of Plausible Inference[END_REF] is a message passing procedure that allows to compute efficiently exact marginal probabilities when the underlying graph is a tree. When the graph has cycles, it is still possible to apply the procedure, which converges with a rather good accuracy on sufficiently sparse graphs. However, there may be several fixed points, corresponding to stationary points of the Bethe free energy [START_REF] Yedidia | Constructing free-energy approximations and generalized belief propagation algorithms[END_REF]. Stable fixed points of BP are local minima of the Bethe free energy [START_REF] Heskes | Stable fixed points of loopy belief propagation are minima of the Bethe free energy[END_REF][START_REF] Watanabe | Graph zeta function in the Bethe free energy and loopy belief propagation[END_REF].

The question of convergence of BP has been addressed in a series of works [START_REF] Tatikonda | Loopy belief propagation and Gibbs measures[END_REF][START_REF] Ihler | Loopy belief propagation: Convergence and effects of message errors[END_REF][START_REF] Mooij | Sufficient conditions for convergence of the sum-product algorithm[END_REF], which establish sufficient conditions on the MRF under which BP converges to a unique fixed point. However, cases with multiple fixed points can be used to encode different patterns [START_REF] Furtlehner | Learning multiple belief propagation fixed points for real time inference[END_REF] and have not been studied yet. Wainwright [START_REF] Wainwright | Estimating the "wrong" graphical model: benefits in the computation-limited setting[END_REF] suggests that, facing the joint problem of parameter estimation and prediction in a MRF, estimation under the Bethe approximation and prediction using BP is an efficient setting. This consist in choosing (1) such that one fixed point is known. We propose here to change the viewpoint and, instead of looking for conditions ensuring a single fixed point, examine the local properties of each of them. Theorem 4.1 gives a sufficient condition for local stability of fixed points which quantifies the known fact that BP performs better in sparser graphs.

The paper is organized as follows: the BP algorithm and its various normalization strategies are defined in Section 2. Section 3 exhibits cases where convergence of messages is equivalent to convergence of beliefs, allowing us to consider only message convergence. Finally in Section 4, we provide some sufficient conditions for local stability of BP fixed points. Section 5 concludes the paper.

The belief propagation algorithm

The belief propagation algorithm [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Network of Plausible Inference[END_REF] is a message passing procedure, whose output is a set of estimated marginal probabilities, the beliefs b a (x a ) (including single nodes beliefs b i (x i )). The idea is to factor the marginal probability at a given site as a product of contributions coming from neighboring factor nodes, which are the messages. With definition (1) of the joint probability measure, the updates rules read:

m a→i (x i ) ← x a\i ψ a (x a ) j∈a\i n j→a (x j ), ( 2
)
n i→a (x i ) def = φ i (x i ) a ′ ∋i,a ′ =a m a ′ →i (x i ), (3)
where the notation x a\i should be understood as summing from 1 to q all the variables x j , j ∈ a ⊂ V, j = i. At any point of the algorithm, one can compute the current beliefs as

b i (x i ) def = 1 Z i (m) φ i (x i ) a∋i m a→i (x i ), ( 4
) b a (x a ) def = 1 Z a (m) ψ a (x a ) i∈a n i→a (x i ), (5)
where Z i (m) and Z a (m) are the normalization constants that ensure that

x i b i (x i ) = 1, x a b a (x a ) = 1. ( 6
)
These constants reduce to 1 when G is a tree. When the algorithm has converged, the following compatibility condition holds :

x a\i b a (x a ) = b i (x i ). (7)
In practice, the messages are often normalized so that

q x i =1 m a→i (x i ) = 1. (8)
However, the possibilities of normalization are not limited to this setting. Consider the mapping

Θ ai,x i (m) def = x a\i ψ a (x a ) j∈a\i φ j (x j ) a ′ ∋j,a ′ =a m a ′ →j (x j ) . ( 9
)
A normalized version of BP is defined by the update rule

ma→i (x i ) ← Θ ai,x i ( m) Z ai ( m) . ( 10
)
where Z ai ( m) is a constant that depends on the messages and which, in the case of (8), reads

Z mess ai ( m) def = q x=1 Θ ai,x ( m). (11)
Following [START_REF] Wainwright | Stochastic processes on graphs with cycles: geometric and variational approaches[END_REF], it is worth noting that (2,3) can be rewritten as

m a→i (x i ) ← Z a (m)b i|a (x i ) Z i (m)b i (x i ) m a→i (x i ), (12)
where we use the convenient shorthand notation b i|a

(x i ) def = x a\i b a (x a )
. This suggests a different type of normalization, used in particular by [START_REF] Heskes | Stable fixed points of loopy belief propagation are minima of the Bethe free energy[END_REF], namely

Z bel ai ( m) def = Z a ( m) Z i ( m) , ( 13
)
which leads to the simple update rule ma→i

(x i ) ← b i|a (x i ) b i (x i ) ma→i (x i ). ( 14
)

Belief and message dynamic

At each step of the algorithm, using (4) and ( 5), we can compute the current beliefs b (n) i and b (n) a associated with the message m (n) . The sequence m (n) will be said to be "b-convergent" when the sequences b (n) i and b (n) a converge. This is the convergence that is interesting in practice. The term "m-convergence" will be used to refer to convergence of the sequence m (n) itself. Since the algorithm is expressed in terms messages, m-convergence obviously implies b-convergence, but the opposite is not generally true. The aim of this section is to provide a broad class of normalization policies such that b-and m-convergence, are equivalent in order to focus on m-convergence in the next section.

As pointed out in [START_REF] Mooij | Sufficient conditions for convergence of the sum-product algorithm[END_REF], different sets of messages correspond to the same set of beliefs. The following lemma makes this explicit. Lemma 3.1. Two set of messages m and m ′ lead to the same beliefs if, and only if, there is a set of strictly positive constants c ai such that

m ′ a→i (x i ) = c ai m a→i (x i ).
Proof. The direct part of the lemma is trivial. Concerning the other part, we have from ( 4) and ( 5)

b a (x a )Z a (m) ψ a (x a ) = j∈a b∋j,b =a m b→j (x j ), b i (x i )Z i (m) φ i (x i ) = a∋i m a→i (x i ).
Assume the two vectors of messages m and m ′ lead to the same set of beliefs b and write m a→i

(x i ) = c ai (x i ) m ′ a→i (x i ).
Then, from the relation on b i (x i ), the vector c satisfies

a∋i c ai (x i ) = a∋i m a→i (x i ) m ′ a→i (x i ) = Z i (m) Z i (m ′ ) def = v i . ( 15
)
Moreover, we want to preserve the beliefs b a . Using (15), we have

j∈a c aj (x j ) = j∈a m a→j (x j ) m ′ a→j (x j ) = Z a (m ′ ) Z a (m) i∈a v i def = v a , (16)
since v i (resp. v a ) does not depend on the choice of x i (resp. x a ), ( 16) implies the independence of c ai (x i ) with respect to x i . Indeed, if we compare two vectors x a and x ′ a such that, for all i ∈ a\ j,

x ′ i = x i , but x ′ j = x j , then c aj (x j ) = c aj (x ′ j ), which concludes the proof.
Following an idea developed in [START_REF] Mooij | Sufficient conditions for convergence of the sum-product algorithm[END_REF], it is natural to look at the behavior of BP in a quotient space corresponding to the invariance of beliefs. First, we will introduce a natural parametrization for which the quotient space is just a vector space. Then we will show that, in terms of b-convergence, the effect of normalization is null. Let us consider the following change of variables:

µ a→i (x i ) def = log m a→i (x i ),
so that the plain update mapping (9) becomes

µ a→i (x i ) ← Λ ai,x i (µ) def = log     x a \i ψ a (x a ) exp j∈a\i b∋j b =a µ b→j (x j )     .
We have µ ∈ N def = R |E|×q and we define the vector space W which is the linear span of the following vectors

{e ai ∈ N } (ai)∈E (e ai ) cj,x j def = 1 1 {a=c,i=j} .
The invariance set of the beliefs corresponding to µ is simply the affine space µ + W (Lemma 3.1). So µ (n) is b-convergent iff µ (n) converges in the quotient space N \ W, which is simply a vector space [START_REF] Halmos | Finite-Dimensional Vector Space[END_REF]. We use the notation [x] for the canonical projection of x on N \ W.

The normalization of µ leads to µ + w with some w ∈ W. Indeed we have

Λ ai,x i (µ + w) = log j∈a\i b∋j b =a w bj + Λ ai,x i (µ) def = l ai + Λ ai,x i (µ),
which can be summed up by [Λ(µ + W)] = [Λ(µ)], since l ∈ W. This means that normalization plays no role in N \ W and implies the following proposition.

Proposition 3.2. The dynamic, i.e. the value of the normalized beliefs at each step, of the BP algorithm with or without normalization is exactly the same.

We will come back to this vision in terms of quotient space in Section 4.3, and we now exhibit a broad class of normalizations for which b-convergence and m-convergence are equivalent.

Definition 3.3.

A normalization Z ai is said to be positive homogeneous when it is of the form Z ai = N ai • Θ ai , with N ai : R q + → R + a positive homogeneous function of order 1 satisfying

N ai (λm a→i ) = λN ai (m a→i ), ∀λ ≥ 0. ( 17
) N ai (m a→i ) = 0 ⇐⇒ m a→i = 0. (18)
A particular family of positive homogeneous normalizations is obtained when N ai is a norm on R q . This is the case the normalization Z mess ai [START_REF] Wainwright | Stochastic processes on graphs with cycles: geometric and variational approaches[END_REF]. It is actually not necessary to have a proper norm: the scheme used in [START_REF] Watanabe | Graph zeta function in the Bethe free energy and loopy belief propagation[END_REF] amounts to Z 1 ai (m) def = Θ ai,1 (m). Note however that Z bel ai 13 is not part positive homogeneous, and therefore the results of this section do not apply to this case. Proof. Assume that the sequences of beliefs are such that b (n) a → b a and b (n) i → b i as n → ∞. The idea of the proof is to first express the normalized messages m(n) a→i at each step in terms of these beliefs, and then to conclude by a continuity argument. Starting from a rewrite of ( 4)-( 5),

b (n) i (x i ) = φ i (x i ) Z i ( m(n) ) a∋i m(n) a→i (x i ), b (n) a (x a ) = ψ a (x a ) Z a ( m(n) ) j∈a φ j (x j ) b∋j,b =a m(n) b→j (x j ),
one obtains by recombination

j∈a m(n) a→j (x j ) = K (n) ai (x a\i ; x i ) Zai ( m) ,
where an arbitrary variable i ∈ a has been singled out and

1 Zai ( m) def = j∈a Z j ( m(n) ) Z a ( m(n) ) , K (n) ai (x a\i ; x i ) def = ψ a (x a ) j∈a b (n) j (x j ) b (n) a (x a )
. Assume now that x a\i is fixed and consider K (n) ai (x a\i ) def = K (n) ai (x a\i ; •) as a vector of R q . Normalizing each side of the equation with a positive homogeneous function

N ai yields m(n) a→i (x i ) N ai m(n) a→i = K (n) ai (x a\i ; x i ) N ai K (n) ai (x a\i )
.

Actually N ai m(n) a→i = 1, since m(n) a→i has been normalized by N ai and therefore

m(n) a→i (x i ) = K (n) ai (x a\i ; x i ) N ai K (n) ai (x a\i )
.

This concludes the proof, since m(n) a→i has been expressed as a continuous function of b (n) i and b (n) a , and therefore it converges whenever the beliefs converge.

Local stability of BP fixed points

The question of convergence of BP has been addressed in a series of works [START_REF] Tatikonda | Loopy belief propagation and Gibbs measures[END_REF][START_REF] Ihler | Loopy belief propagation: Convergence and effects of message errors[END_REF][START_REF] Mooij | Sufficient conditions for convergence of the sum-product algorithm[END_REF] which establish conditions and bounds on the MRF coefficients for having global convergence. In this section, we change the viewpoint and, instead of looking for conditions ensuring a single fixed point, we examine the local properties each fixed point.

In what follows, we are interested in the local stability of a message fixed point m with associated beliefs b. It is known that a BP fixed point is locally attractive if the Jacobian of the relevant mapping (Θ or its normalized version) at this point has all its eigenvalues of modulus strictly smaller than 1 and unstable when, at least, one eigenvalue has a modulus strictly greater than 1. The characterization of the local stability relies on two ingredients. The first one is the oriented line graph L(G) based on G, whose vertices are the elements of E, and whose oriented links relate ai to a ′ j if j ∈ a ∩ a ′ , j = i and a ′ = a. The corresponding 0-1 adjacency matrix A is defined by the coefficients

A a ′ j ai def = 1 1 {j∈a∩a ′ , j =i, a ′ =a} . ( 19
)
The second ingredient is the set of stochastic matrices B (iaj) , attached to pairs of variables (i, j) having a factor node a in common, and which coefficients at row k, column ℓ (in {1, . . . , q} 2 ) are the conditional beliefs

b (iaj) kℓ def = b a (x j = ℓ|x i = k) = x a\{i,j} b a (x a ) b i (x i ) x i =k x j =ℓ .

The unnormalized algorithm

Let us first consider briefly the unnormalized algorithm [START_REF] Furtlehner | Learning multiple belief propagation fixed points for real time inference[END_REF][START_REF] Halmos | Finite-Dimensional Vector Space[END_REF]. Using the representation [START_REF] Wainwright | Estimating the "wrong" graphical model: benefits in the computation-limited setting[END_REF], the Jacobian reads at this point:

∂Θ ai,x i (m) ∂m a ′ →j (x j ) = x a\{i,j} b a (x a ) b i (x i ) m a→i (x i ) m a ′ →j (x j ) 1 1 {j∈a\i} 1 1 {a ′ ∋j,a ′ =a} = b ij|a (x i , x j ) b i (x i ) m a→i (x i ) m a ′ →j (x j ) A a ′ j ai
Therefore, the Jacobian of the plain BP algorithm is-using a trivial change of variable-similar to the matrix J defined, for any pair (ai, k) and (a ′ j, ℓ) of E × {1, . . ., q} by the elements

J a ′ j,ℓ ai,k def = b (iaj) kℓ A a ′ j ai .
This expression is analogous to the Jacobian encountered in [START_REF] Mooij | Sufficient conditions for convergence of the sum-product algorithm[END_REF]. It is interesting to note that it only depends on the structure of the graph and on the belief corresponding to the fixed point. Since G is a singly connected graph, it is clear that A is an irreducible matrix. To simplify the discussion, we assume in the following that J is also irreducible. This will be true as long as the ψ are always positive.

It can be shown [START_REF] Martin | The Role of Normalization in the Belief Propagation Algorithm[END_REF] that the spectral radius of J is always larger than 1, except in some special cases where the number of cycles in the graph is less than 1. We will not develop this point here.

Positive homogeneous normalization

We have seen in Proposition 3.4 that all the continuous positively homogeneous normalizations make m-convergence equivalent to b-convergence. Since they all share the same properties, we look at the particular case of Z mess ai (m), which is both simple and differentiable. The coefficients of the Jacobian matrix at fixed point m with beliefs b read

∂ ∂ ma ′ →j (ℓ) Θ ai,k ( m) q x=1 Θ ai,x ( m) = J a ′ j,ℓ ai,k m a→i (k) m a ′ →j (ℓ) -m a→i (k) q x=1 J a ′ j,ℓ ai,x m a→i (x) m a ′ →j (ℓ) ,
which is similar to the matrix J of general term

J a ′ j,ℓ ai,k def = b (iaj) kℓ - q x=1 m a→i (x)b (iaj) xℓ A a ′ j ai = J a ′ j,ℓ ai,k - q x=1 m a→i (x)J a ′ j,ℓ ai,x , ( 20
)
which can be summarized by J = (I -M )J, with I the identity matrix and M :

M a ′ j,ℓ ai,k def = m a ′ →j (ℓ)1 1 {a=b,i=j} .
The presence of the messages in the Jacobian J seems to complicate the study, but in fact the spectrum of J does not depend on the messages themselves. It is known (see e.g. [START_REF] Furtlehner | Learning multiple belief propagation fixed points for real time inference[END_REF]) that it is possible to chose the functions φ and ψ as φi

(x i ) def = bi (x i ), ψa (x a ) def = ba (x a ) i∈a bi (x i ) , ( 21
)
in order to obtain a prescribed set of beliefs b at a fixed point. Indeed, BP will admit a fixed point with b a = ba and b i = bi when m a→i (x i ) ≡ 1. Since only the beliefs matter here, without loss of generality, we restrict ourselves in the remainder of this section to the functions (21). Then, from (20), the definition of J rewrites

J a ′ j,ℓ ai,k def = b (iaj) kℓ - 1 q q x=1 b (iaj) xℓ A a ′ j ai = J a ′ j,ℓ ai,k - 1 q q x=1 J a ′ j,ℓ ai,x .
For each connected pair (i, j) of variable nodes, we associate to the stochastic kernel B (iaj) a combined stochastic kernel K (iaj) def = B (iaj) B (jai) . In the following we consider b i as a vector of R q . Since b i B (iaj) = b j , b i is the invariant measure associated to K:

b i K (iaj) = b i B (iaj) B (jai) = b j B (jai) = b i , and K (iaj) is reversible, since b i (k)K (iaj) kℓ = q m=1 b (jai) mk b j (m)b (jai) mℓ = q m=1 b (jai) mk b (iaj) ℓm b i (ℓ) = b i (ℓ) K (iaj) ℓk . Let µ (iaj) 2
be the second largest eigenvalue of K (iaj) and let

µ 2 def = max (iaj) |µ (iaj) 2 |.
The combined effect of the graph and of the local correlations on the stability of the reference fixed point is stated as follows.

Theorem 4.1. Let λ 1 be the Perron eigenvalue of the matrix A (i) if λ 1 µ 2 < 1, the fixed point of BP scheme [START_REF] Tatikonda | Loopy belief propagation and Gibbs measures[END_REF][START_REF] Wainwright | Stochastic processes on graphs with cycles: geometric and variational approaches[END_REF] associated to b is stable.

(ii) If the system is homogeneous (B (iaj) = B independent of i, j and a), λ 1 µ 2 ≤ 1 is also a necessary condition.

Condition (i) combines the effects of a term (µ 2 ) which depends on the local dependence structure of the given fixed point with another one (λ 1 ) characteristic of the underlying graph. For example, in the homogeneous case, if G has uniform degrees d a and d i , the condition reads

µ 2 (d a -1)(d i -1) < 1.
In the case of binary variables µ (iaj) 2

= det(K (iaj) ), which is just the square of Pearson's correlation coefficient between x i and x j , which in general depends on the factor a. The condition (i) of Theorem 4.1 thus is an upper bound on the correlations between variables at stable fixed points.

In order to prove part (i) of the theorem, we will consider a local norm on R q attached to each variable node i,

x b i def = q k=1 x 2 k b i (k) 1 2 and x b i def = q k=1
x k b i (k), the local average of x ∈ R q w.r.t b i . For convenience, we will also consider the somewhat hybrid global norm on R q×|E|

x π,b def = (ai)∈E π ai x ai b i ,
where π is the right Perron vector of A, associated to λ 1 . We have the following useful inequality: Lemma 4.2. For any (x (i) , x (j) ) ∈ R q ×R q , such that x (i) b i = 0 and x (j)

ℓ b j (ℓ) = k x (i) k b i (k)B (iaj) kℓ , x (j) b j = 0 and x (j) 2 b j ≤ µ (iaj) 2 x (i) 2 b i .
Proof. By definition of the kernels K (iaj) , we have

x (j) 2 b j = q k=1 1 b j (k) q ℓ=1 b (iaj) ℓk b i (ℓ) x (i) ℓ 2 = ℓ,m x (i) ℓ x (i) m K (iaj) ℓm b i (ℓ). Since K (iaj) is reversible, Rayleigh's theorem implies µ (iaj) 2 def = sup x kℓ x k x ℓ K (iaj) kℓ b i (k) k x 2 k b i (k) , x b i = 0, x = 0 ,
which concludes the proof.

To deal with iterations of J, we express it as a sum over paths.

J n a ′ j,ℓ ai,k = A n a ′ j ai B (n) ai,a ′ j kℓ ,
where B (n) ai,a ′ j is an average stochastic kernel,

B (n) ai,a ′ j def = 1 |Γ (n) ai,a ′ j | γ∈Γ (n) ai,a ′ j (ck,dℓ)∈γ B (kcℓ) . (22) Γ (n)
ai,a ′ j represents the set of directed path of length n joining ai and a ′ j on L(G) and its cardinal is precisely |Γ

(n) ai,a ′ j | = A n a ′ j ai .
Lemma 4.3. For any (x (ai) , x (a ′ j) ) ∈ R 2q , such that x (ai) b i = 0 and

x (a ′ j) ℓ b j (ℓ) = k x (ai) k b i (k) B (n)
ai,a ′ j kℓ , the following inequality holds

x (a ′ j) b j ≤ µ n 2 x (ai) b i .
Proof. Let x (a ′ j) (γ) be the contribution to x (a ′ j) corresponding to the path γ ∈ Γ (n) ai,a ′ j . Using Lemma 4.2 recursively yields for each individual path

x (a ′ j) (γ) b j ≤ µ n 2 x (ai)
b i , and, owing to triangle inequality,

x (a ′ j) b j ≤ 1 |Γ (n) ai,a ′ j | γ∈Γ (n) ai,a ′ j x (a ′ j) (γ) b j ≤ µ n 2 x (ai) b i .
Proof of Theorem 4.1. Let v and v ′ two vectors with v ′ = v Jn = v(I -M )J n , since JM = 0. Recall that the effect of (I -M ) is to first project on a vector with zero local sum, k v(I -M ) ai,k = 0, ∀i ∈ V, so we assume directly v of the form

v ai,k = x ai,k b i (k), with x ai b i = 0. As a result, v ′ = vJ n is of the same form. Let x ′ a ′ j,ℓ def = v ′ a ′ j,ℓ /b j (ℓ). We have x ′ π,b ≤ (a ′ j)∈E π a ′ j (ai)∈E A n a ′ j ai y (ai) a ′ j b j , with y (ai) a ′ j,ℓ b j (ℓ) = k x ai,k b i (k) B (n) ai,a ′ j kℓ . Applying Lemma 4.3 to y (ai) a ′ j yields x ′ π,b ≤ (a ′ j)∈E π a ′ j (ai)∈E A n a ′ j ai µ n 2 x ai b i = λ n 1 µ n 2 x π,b ,
since π is the right Perron vector of A. This ends the proof of (i). For (ii), when the system is homogeneous, J is a tensor product of A with B, and its spectrum is therefore the product of their respective spectra.

The quantity µ 2 is representative of the level of mutual information between variables. It relates to the spectral gap (see e.g. [START_REF] Diaconis | Geometric bounds for eigenvalues of Markov chains[END_REF] for geometric bounds) of each elementary stochastic matrix B (iaj) , while λ 1 encodes the statistical properties of the graph connectivity. The bound λ 1 µ 2 < 1 could be refined when dealing with the statistical average of the sum over path in

Local convergence in quotient space N \ W

We make here the connexion with the notion of local stability in the quotient space N \ W of Section 3. Trivial computations yield ∇Λ = J. In terms of convergence in N \ W, the stability of a fixed point is given by the projection of J on the quotient space N \ W and we have [START_REF] Mooij | Sufficient conditions for convergence of the sum-product algorithm[END_REF]:

[J] def = [∇Λ] = ∇[Λ]
The normalization Z mess ai is in fact just a way to compute [J] by applying a projection I -M to J. Since ker(I -M ) = W, it is just a quotient map from N to N \ W. For any differentiable positively homogeneous normalization, we obtain the same result, the Jacobian of the corresponding normalized scheme is the projection of J on N \ W, through some quotient map.

Conclusion

We provided here, for the first time at our knowledge, an explicit sufficient condition for local stability of a belief propagation fixed point, instead of sufficient conditions for convergence to a unique fixed point. This condition is coherent with the usual understanding of BP convergence; when the connectivity of both G and L(G) increases, λ 1 is also increasing since A is increasing. So Theorem 4.1 imposes that the level of mutual information µ (iaj) 2 between variables i and j at a stable fixed point decreases. Reciprocally, the sparser G is, the bigger mutual information can be. This somewhat explains why BP performs better on sparse graphs: the amount of admissible mutual information between variables at a stable fixed point is larger on a sparse graph than on a dense one.

Proposition 3 . 4 .

 34 For any positive homogeneous normalization Z ai with continuous N ai , m-convergence and b-convergence are equivalent.

  (22) which allows to define µ 2 asµ 2 = lim n→∞ max (ai,a ′ j) 1 |Γ (n) ai,a ′ j | γ∈Γ (n) ai,a ′ j (x,y)∈γ µ